IDEAS home Printed from https://ideas.repec.org/a/gam/jsusta/v13y2021i9p4674-d541245.html
   My bibliography  Save this article

Time-Dependent Multi-Depot Heterogeneous Vehicle Routing Problem Considering Temporal–Spatial Distance

Author

Listed:
  • Dengkai Hou

    (College of Transportation Engineering, Dalian Maritime University, Dalian 116026, China)

  • Houming Fan

    (College of Transportation Engineering, Dalian Maritime University, Dalian 116026, China)

  • Xiaoxue Ren

    (College of Transportation Engineering, Dalian Maritime University, Dalian 116026, China)

  • Panjun Tian

    (College of Transportation Engineering, Dalian Maritime University, Dalian 116026, China)

  • Yingchun Lv

    (College of Transportation Engineering, Dalian Maritime University, Dalian 116026, China)

Abstract

Aiming at the multi-depot heterogeneous vehicle routing problem under the time-dependent road network and soft time window, considering vehicle fixed cost, time window penalty cost and vehicle transportation cost, an optimization model of time-dependent multi-depot heterogeneous vehicle routing problem is established with the objective of minimizing distribution cost. According to the characteristics of the problem, a hybrid genetic algorithm with variable neighborhood search considering the temporal–spatial distance is designed. Customers are clustered according to the temporal–spatial distance to generate initial solutions, which improves the quality of the algorithm. The depth search capability of the variable neighborhood search algorithm is applied to the local search strategy of the genetic algorithm to enhance the local search capability of the algorithm. An adaptive neighborhood search number strategy and a new acceptance mechanism of simulated annealing are proposed to balance the breadth and depth required for population evolution. The validity of the model and algorithm is verified by several sets of examples of different scales. The research results not only deepen and expand the relevant research on vehicle routing problem, but also provide theoretical basis for logistics enterprises to optimize distribution scheme.

Suggested Citation

  • Dengkai Hou & Houming Fan & Xiaoxue Ren & Panjun Tian & Yingchun Lv, 2021. "Time-Dependent Multi-Depot Heterogeneous Vehicle Routing Problem Considering Temporal–Spatial Distance," Sustainability, MDPI, vol. 13(9), pages 1-16, April.
    • Handle: RePEc:gam:jsusta:v:13:y:2021:i:9:p:4674-:d:541245
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2071-1050/13/9/4674/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2071-1050/13/9/4674/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Beasley, JE, 1981. "Adapting the savings algorithm for varying inter-customer travel times," Omega, Elsevier, vol. 9(6), pages 658-659.
    2. Jian Li & Yang Li & Panos M. Pardalos, 2016. "Multi-depot vehicle routing problem with time windows under shared depot resources," Journal of Combinatorial Optimization, Springer, vol. 31(2), pages 515-532, February.
    3. 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.
    4. Nagy, Gabor & Salhi, Said, 2005. "Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries," European Journal of Operational Research, Elsevier, vol. 162(1), pages 126-141, April.
    5. 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.
    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. Hamza Ben Ticha & Nabil Absi & Dominique Feillet & Alain Quilliot & Tom Woensel, 2021. "The Time-Dependent Vehicle Routing Problem with Time Windows and Road-Network Information," SN Operations Research Forum, Springer, vol. 2(1), pages 1-25, March.
    2. 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.
    3. Thomas R. Visser & Remy Spliet, 2020. "Efficient Move Evaluations for Time-Dependent Vehicle Routing Problems," Transportation Science, INFORMS, vol. 54(4), pages 1091-1112, July.
    4. 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).
    5. 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.
    6. Zhao, Jingyi & Poon, Mark & Tan, Vincent Y.F. & Zhang, Zhenzhen, 2024. "A hybrid genetic search and dynamic programming-based split algorithm for the multi-trip time-dependent vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 317(3), pages 921-935.
    7. Visser, T.R. & Spliet, R., 2017. "Efficient Move Evaluations for Time-Dependent Vehicle Routing Problems," Econometric Institute Research Papers EI2017-23, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. 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.
    13. Mahdi Alinaghian & Komail Zamanlou & Mohammad S. Sabbagh, 2017. "A bi-objective mathematical model for two-dimensional loading time-dependent vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(11), pages 1422-1441, November.
    14. 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.
    15. 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.
    16. Jianbin Xin & Benyang Yu & Andrea D’Ariano & Heshan Wang & Meng Wang, 2022. "Time-dependent rural postman problem: time-space network formulation and genetic algorithm," Operational Research, Springer, vol. 22(3), pages 2943-2972, July.
    17. 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.
    18. 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.
    19. Niroomand, Iman & Nsakanda, Aaron Luntala, 2018. "Improving collection flows in a public postal network with contractor's obligation considerations," International Journal of Production Economics, Elsevier, vol. 198(C), pages 79-92.
    20. Wohlgemuth, Sascha & Oloruntoba, Richard & Clausen, Uwe, 2012. "Dynamic vehicle routing with anticipation in disaster relief," Socio-Economic Planning Sciences, Elsevier, vol. 46(4), pages 261-271.

    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:gam:jsusta:v:13:y:2021:i:9:p:4674-:d:541245. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.