IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v142y2020ics136655452030733x.html
   My bibliography  Save this article

On the impact of spatio-temporal granularity of traffic conditions on the quality of pickup and delivery optimal tours

Author

Listed:
  • Rifki, Omar
  • Chiabaut, Nicolas
  • Solnon, Christine

Abstract

Optimizing the duration of delivery tours is a crucial issue in urban logistics. In most cases, travel times between locations are considered as constant for the whole optimization horizon. Making these travel times time-dependent is particularly relevant in real urban traffic environments as traffic conditions and thus travel speeds vary according to the time of the day. In this paper, we review the literature on time-dependent routing problems, with a specific focus on benchmarks and performance criteria used to experimentally evaluate the interest of exploiting time-dependent data, showing the lack of studies on the impact of spatio-temporal features of the benchmark on solutions. Hence, we introduce a new benchmark produced from a realistic traffic flow micro-simulation of Lyon city, allowing us to consider different levels of spatial granularity (i.e., number of sensors used to measure traffic conditions) and temporal granularity (i.e., frequency of measures). Finally, we experimentally evaluate the impact of the spatio-temporal granularity on the quality of solutions for different classical problems, including the traveling salesman problem, the pickup and delivery problem, and the dial-a-ride problem.

Suggested Citation

  • Rifki, Omar & Chiabaut, Nicolas & Solnon, Christine, 2020. "On the impact of spatio-temporal granularity of traffic conditions on the quality of pickup and delivery optimal tours," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 142(C).
    • Handle: RePEc:eee:transe:v:142:y:2020:i:c:s136655452030733x
    DOI: 10.1016/j.tre.2020.102085
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S136655452030733X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2020.102085?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Van Woensel, T. & Kerbache, L. & Peremans, H. & Vandaele, N., 2008. "Vehicle routing with dynamic travel times: A queueing approach," European Journal of Operational Research, Elsevier, vol. 186(3), pages 990-1007, May.
    2. Ehmke, Jan Fabian & Campbell, Ann M. & Thomas, Barrett W., 2018. "Optimizing for total costs in vehicle routing in urban areas," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 116(C), pages 242-265.
    3. Bernhard Fleischmann & Martin Gietz & Stefan Gnutzmann, 2004. "Time-Varying Travel Times in Vehicle Routing," Transportation Science, INFORMS, vol. 38(2), pages 160-173, May.
    4. Chryssi Malandraki & Mark S. Daskin, 1992. "Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms," Transportation Science, INFORMS, vol. 26(3), pages 185-200, August.
    5. Andres Figliozzi, Miguel, 2012. "The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution algorithm, and solution characteristics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(3), pages 616-636.
    6. Schneider, Johannes, 2002. "The time-dependent traveling salesman problem," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 314(1), pages 151-155.
    7. Donati, Alberto V. & Montemanni, Roberto & Casagrande, Norman & Rizzoli, Andrea E. & Gambardella, Luca M., 2008. "Time dependent vehicle routing problem with a multi ant colony system," European Journal of Operational Research, Elsevier, vol. 185(3), pages 1174-1191, March.
    8. Laval, Jorge A. & Leclercq, Ludovic, 2008. "Microscopic modeling of the relaxation phenomenon using a macroscopic lane-changing model," Transportation Research Part B: Methodological, Elsevier, vol. 42(6), pages 511-522, July.
    9. Ichoua, Soumia & Gendreau, Michel & Potvin, Jean-Yves, 2003. "Vehicle dispatching with time-dependent travel times," European Journal of Operational Research, Elsevier, vol. 144(2), pages 379-396, January.
    10. Leclercq, Ludovic, 2007. "Bounded acceleration close to fixed and moving bottlenecks," Transportation Research Part B: Methodological, Elsevier, vol. 41(3), pages 309-319, March.
    11. Malandraki, Chryssi & Dial, Robert B., 1996. "A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 90(1), pages 45-55, April.
    12. Laoucine Kerbache & T. van Woensel & N. Vandaele & Herbert Peremans, 2008. "Vehicle routing with dynamic travel times: A queueing approach," Post-Print hal-00465127, HAL.
    13. Panayotis Christidis & Juan Nicolás Ibanez Rivas, 2012. "Measuring road congestion," JRC Research Reports JRC69961, Joint Research Centre.
    14. Jan Fabian Ehmke, 2012. "Routing in City Logistics," International Series in Operations Research & Management Science, in: Integration of Information and Optimization Models for Routing in City Logistics, edition 127, chapter 0, pages 119-156, Springer.
    15. Jean-François Cordeau & Gianpaolo Ghiani & Emanuela Guerriero, 2014. "Analysis and Branch-and-Cut Algorithm for the Time-Dependent Travelling Salesman Problem," Transportation Science, INFORMS, vol. 48(1), pages 46-58, February.
    16. Sun, Peng & Veelenturf, Lucas P. & Hewitt, Mike & Van Woensel, Tom, 2020. "Adaptive large neighborhood search for the time-dependent profitable pickup and delivery problem with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 138(C).
    17. Newell, G. F., 2002. "A simplified car-following theory: a lower order model," Transportation Research Part B: Methodological, Elsevier, vol. 36(3), pages 195-205, March.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    2. Touzout, Faycal A. & Ladier, Anne-Laure & Hadj-Hamou, Khaled, 2022. "An assign-and-route matheuristic for the time-dependent inventory routing problem," European Journal of Operational Research, Elsevier, vol. 300(3), pages 1081-1097.
    3. Fontaine, Romain & Dibangoye, Jilles & Solnon, Christine, 2023. "Exact and anytime approach for solving the time dependent traveling salesman problem with time windows," European Journal of Operational Research, Elsevier, vol. 311(3), pages 833-844.
    4. Dai, Zhuang & Han, Ke, 2023. "Exploring the drive-by sensing power of bus fleet through active scheduling," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 171(C).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Verbeeck, C. & Vansteenwegen, P. & Aghezzaf, E.-H., 2016. "Solving the stochastic time-dependent orienteering problem with time windows," European Journal of Operational Research, Elsevier, vol. 255(3), pages 699-718.
    2. Diego Cattaruzza & Nabil Absi & Dominique Feillet & Jesús González-Feliu, 2017. "Vehicle routing problems for city logistics," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(1), pages 51-79, March.
    3. Lu, Jiawei & Nie, Qinghui & Mahmoudi, Monirehalsadat & Ou, Jishun & Li, Chongnan & Zhou, Xuesong Simon, 2022. "Rich arc routing problem in city logistics: Models and solution algorithms using a fluid queue-based time-dependent travel time representation," Transportation Research Part B: Methodological, Elsevier, vol. 166(C), pages 143-182.
    4. Andres Figliozzi, Miguel, 2012. "The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution algorithm, and solution characteristics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(3), pages 616-636.
    5. Verbeeck, C. & Sörensen, K. & Aghezzaf, E.-H. & Vansteenwegen, P., 2014. "A fast solution method for the time-dependent orienteering problem," European Journal of Operational Research, Elsevier, vol. 236(2), pages 419-432.
    6. Said Dabia & Stefan Ropke & Tom van Woensel & Ton De Kok, 2013. "Branch and Price for the Time-Dependent Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 47(3), pages 380-396, August.
    7. Nicolas Rincon-Garcia & Ben J. Waterson & Tom J. Cherrett, 2018. "Requirements from vehicle routing software: perspectives from literature, developers and the freight industry," Transport Reviews, Taylor & Francis Journals, vol. 38(1), pages 117-138, January.
    8. Fontaine, Romain & Dibangoye, Jilles & Solnon, Christine, 2023. "Exact and anytime approach for solving the time dependent traveling salesman problem with time windows," European Journal of Operational Research, Elsevier, vol. 311(3), pages 833-844.
    9. Sun, Peng & Veelenturf, Lucas P. & Dabia, Said & Van Woensel, Tom, 2018. "The time-dependent capacitated profitable tour problem with time windows and precedence constraints," European Journal of Operational Research, Elsevier, vol. 264(3), pages 1058-1073.
    10. Rincon-Garcia, Nicolas & Waterson, Ben & Cherrett, Tom J. & Salazar-Arrieta, Fernando, 2020. "A metaheuristic for the time-dependent vehicle routing problem considering driving hours regulations – An application in city logistics," Transportation Research Part A: Policy and Practice, Elsevier, vol. 137(C), pages 429-446.
    11. Lecluyse, Christophe & Sörensen, Kenneth & Peremans, Herbert, 2013. "A network-consistent time-dependent travel time layer for routing optimization problems," European Journal of Operational Research, Elsevier, vol. 226(3), pages 395-413.
    12. Jean-François Cordeau & Gianpaolo Ghiani & Emanuela Guerriero, 2014. "Analysis and Branch-and-Cut Algorithm for the Time-Dependent Travelling Salesman Problem," Transportation Science, INFORMS, vol. 48(1), pages 46-58, February.
    13. Sun, Peng & Veelenturf, Lucas P. & Hewitt, Mike & Van Woensel, Tom, 2018. "The time-dependent pickup and delivery problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 116(C), pages 1-24.
    14. Xiao, Yiyong & Konak, Abdullah, 2016. "The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 88(C), pages 146-166.
    15. Avraham, Edison & Raviv, Tal, 2020. "The data-driven time-dependent traveling salesperson problem," Transportation Research Part B: Methodological, Elsevier, vol. 134(C), pages 25-40.
    16. Gmira, Maha & Gendreau, Michel & Lodi, Andrea & Potvin, Jean-Yves, 2021. "Tabu search for the time-dependent vehicle routing problem with time windows on a road network," European Journal of Operational Research, Elsevier, vol. 288(1), pages 129-140.
    17. Tikani, Hamid & Setak, Mostafa & Demir, Emrah, 2021. "A risk-constrained time-dependent cash-in-transit routing problem in multigraph under uncertainty," European Journal of Operational Research, Elsevier, vol. 293(2), pages 703-730.
    18. Kok, A.L. & Hans, E.W. & Schutten, J.M.J., 2011. "Optimizing departure times in vehicle routes," European Journal of Operational Research, Elsevier, vol. 210(3), pages 579-587, May.
    19. Huang, Yixiao & Zhao, Lei & Van Woensel, Tom & Gross, Jean-Philippe, 2017. "Time-dependent vehicle routing problem with path flexibility," Transportation Research Part B: Methodological, Elsevier, vol. 95(C), pages 169-195.
    20. Tao Zhang & W. Art Chaovalitwongse & Yuejie Zhang, 2014. "Integrated Ant Colony and Tabu Search approach for time dependent vehicle routing problems with simultaneous pickup and delivery," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 288-309, July.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:transe:v:142:y:2020:i:c:s136655452030733x. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.