IDEAS home Printed from https://ideas.repec.org/a/spr/operea/v23y2023i1d10.1007_s12351-023-00751-3.html
   My bibliography  Save this article

Time-dependent vehicle routing problem of perishable product delivery considering the differences among paths on the congested road

Author

Listed:
  • Fang Zhao

    (Beijing Jiaotong University)

  • Bingfeng Si

    (Beijing Jiaotong University)

  • Zhenlin Wei

    (Beijing Jiaotong University)

  • Tianwei Lu

    (Beijing Jiaotong University)

Abstract

Many companies that conduct a perishable product delivery face a practical problem when an increasingly congested road setting exists. An inappropriate routing scheme not only leads to higher delivery costs but also results in customers' dissatisfaction. The previous literature paid limited attention to the time-dependent difference among paths (between distribution centres and customers or between customers and customers). We developed a time-dependent vehicle routing model considering the differences among paths on the congested road (TDVRP-DP) for perishable product delivery. Given the availability of road setting-related data, we proposed a method to obtain the time-dependent travel time based on the historical traffic index. We built a TDVRP-DP model to minimize the total cost and minimize the dissatisfaction of customers. Solution algorithms with a dichotomy strategy for DP and new evolutionary operators based on several multiobjective evolutionary algorithms (MOEA) were proposed. The computational results of different sizes of problems show that the dichotomy strategy for DP saves about 50% of the computation time and the new evolutionary operators improve the performance of the algorithm slightly in most cases; the NSGA-III-DN performs well for small size (with 20 customers) problems, and the RVEA-DN exhibited better performance for larger (with 50, and 100 customers) ones.

Suggested Citation

  • Fang Zhao & Bingfeng Si & Zhenlin Wei & Tianwei Lu, 2023. "Time-dependent vehicle routing problem of perishable product delivery considering the differences among paths on the congested road," Operational Research, Springer, vol. 23(1), pages 1-23, March.
    • Handle: RePEc:spr:operea:v:23:y:2023:i:1:d:10.1007_s12351-023-00751-3
    DOI: 10.1007/s12351-023-00751-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s12351-023-00751-3
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s12351-023-00751-3?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. Bochra Rabbouch & Foued Saâdaoui & Rafaa Mraihi, 2021. "Efficient implementation of the genetic algorithm to solve rich vehicle routing problems," Operational Research, Springer, vol. 21(3), pages 1763-1791, September.
    2. 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.
    3. 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).
    4. 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.
    5. G. B. Dantzig & J. H. Ramser, 1959. "The Truck Dispatching Problem," Management Science, INFORMS, vol. 6(1), pages 80-91, October.
    6. Moonam, Hasan M. & Qin, Xiao & Zhang, Jun, 2019. "Utilizing data mining techniques to predict expected freeway travel time from experienced travel time," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 155(C), pages 154-167.
    7. 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.
    8. Hualong Yang & Liang Zhao & Di Ye & Jiangshan Ma, 2020. "Disturbance management for vehicle routing with time window changes," Operational Research, Springer, vol. 20(2), pages 1093-1112, June.
    Full references (including those not matched with items on IDEAS)

    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. 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.
    2. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    3. Wang, Jiawei & Guo, Qinglai & Sun, Hongbin & Chen, Min, 2023. "Collaborative optimization of logistics and electricity for the mobile charging service system," Applied Energy, Elsevier, vol. 336(C).
    4. 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.
    5. 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.
    6. Schmidt, Carise E. & Silva, Arinei C.L. & Darvish, Maryam & Coelho, Leandro C., 2023. "Time-dependent fleet size and mix multi-depot vehicle routing problem," International Journal of Production Economics, Elsevier, vol. 255(C).
    7. Daqing Wu & Jiyu Li & Jiye Cui & Dong Hu, 2023. "Research on the Time-Dependent Vehicle Routing Problem for Fresh Agricultural Products Based on Customer Value," Agriculture, MDPI, vol. 13(3), pages 1-23, March.
    8. 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.
    9. Loske, Dominic & Klumpp, Matthias, 2021. "Human-AI collaboration in route planning: An empirical efficiency-based analysis in retail logistics," International Journal of Production Economics, Elsevier, vol. 241(C).
    10. 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).
    11. 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.
    12. 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.
    13. M. Alinaghian & M. Ghazanfari & N. Norouzi & H. Nouralizadeh, 2017. "A Novel Model for the Time Dependent Competitive Vehicle Routing Problem: Modified Random Topology Particle Swarm Optimization," Networks and Spatial Economics, Springer, vol. 17(4), pages 1185-1211, December.
    14. Pan, Binbin & Zhang, Zhenzhen & Lim, Andrew, 2021. "Multi-trip time-dependent vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 291(1), pages 218-231.
    15. Stanisław Majer & Alicja Sołowczuk, 2023. "Traffic Calming Measures and Their Slowing Effect on the Pedestrian Refuge Approach Sections," Sustainability, MDPI, vol. 15(21), pages 1-27, October.
    16. Tomáš Režnar & Jan Martinovič & Kateřina Slaninová & Ekaterina Grakova & Vít Vondrák, 2017. "Probabilistic time-dependent vehicle routing problem," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 25(3), pages 545-560, September.
    17. 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.
    18. Anke Stieber & Armin Fügenschuh, 2022. "Dealing with time in the multiple traveling salespersons problem with moving targets," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 30(3), pages 991-1017, September.
    19. 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.
    20. 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.

    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:spr:operea:v:23:y:2023:i:1:d:10.1007_s12351-023-00751-3. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.