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

Multi-depot multi-trip vehicle routing problem with time windows and release dates

Author

Listed:
  • Zhen, Lu
  • Ma, Chengle
  • Wang, Kai
  • Xiao, Liyang
  • Zhang, Wei

Abstract

This study investigates a multi-depot multi-trip vehicle routing problem with time windows and release dates, which is a practical problem in the last mile distribution operations. This problem aims to design a set of trips for the fleet of vehicles supplied by different depots for minimizing total traveling time. It addresses some realistic considerations, such as the customers’ time windows and the release date of customers’ packages. The problem is formulated as a mixed integer programming model. A hybrid particle swarm optimization algorithm and a hybrid genetic algorithm are developed to solve this problem. Extensive numerical experiments are conducted to validate the effectiveness of the proposed model and the efficiency of the proposed solution methods. The experimental results show that our proposed algorithms can obtain near-optimal solutions for small-scale problem instances, and solve some large-scale instances with up to 200 customers, 20 depots and 40 vehicles in reasonable computation time.

Suggested Citation

  • Zhen, Lu & Ma, Chengle & Wang, Kai & Xiao, Liyang & Zhang, Wei, 2020. "Multi-depot multi-trip vehicle routing problem with time windows and release dates," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 135(C).
    • Handle: RePEc:eee:transe:v:135:y:2020:i:c:s1366554519301486
    DOI: 10.1016/j.tre.2020.101866
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554519301486
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2020.101866?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. G. B. Dantzig & J. H. Ramser, 1959. "The Truck Dispatching Problem," Management Science, INFORMS, vol. 6(1), pages 80-91, October.
    2. Reyes, Damián & Erera, Alan L. & Savelsbergh, Martin W.P., 2018. "Complexity of routing problems with release dates and deadlines," European Journal of Operational Research, Elsevier, vol. 266(1), pages 29-34.
    3. Thibaut Vidal & Teodor Gabriel Crainic & Michel Gendreau & Nadia Lahrichi & Walter Rei, 2012. "A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems," Operations Research, INFORMS, vol. 60(3), pages 611-624, June.
    4. Martin Desrochers & Jacques Desrosiers & Marius Solomon, 1992. "A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows," Operations Research, INFORMS, vol. 40(2), pages 342-354, April.
    5. Diego Cattaruzza & Nabil Absi & Dominique Feillet, 2016. "The Multi-Trip Vehicle Routing Problem with Time Windows and Release Dates," Transportation Science, INFORMS, vol. 50(2), pages 676-693, May.
    6. Nguyen, Phuong Khanh & Crainic, Teodor Gabriel & Toulouse, Michel, 2013. "A tabu search for Time-dependent Multi-zone Multi-trip Vehicle Routing Problem with Time Windows," European Journal of Operational Research, Elsevier, vol. 231(1), pages 43-56.
    7. Jean-Yves Potvin, 2009. "State-of-the Art Review ---Evolutionary Algorithms for Vehicle Routing," INFORMS Journal on Computing, INFORMS, vol. 21(4), pages 518-548, November.
    8. Benjamin C. Shelbourne & Maria Battarra & Chris N. Potts, 2017. "The Vehicle Routing Problem with Release and Due Dates," INFORMS Journal on Computing, INFORMS, vol. 29(4), pages 705-723, November.
    9. Marius M. Solomon, 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, INFORMS, vol. 35(2), pages 254-265, April.
    10. Archetti, Claudia & Feillet, Dominique & Speranza, M. Grazia, 2015. "Complexity of routing problems with release dates," European Journal of Operational Research, Elsevier, vol. 247(3), pages 797-803.
    11. Russell Bent & Pascal Van Hentenryck, 2004. "A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 38(4), pages 515-530, November.
    12. Tang, Jiafu & Yu, Yang & Li, Jia, 2015. "An exact algorithm for the multi-trip vehicle routing and scheduling problem of pickup and delivery of customers to the airport," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 73(C), pages 114-132.
    13. Desaulniers, Guy & Lavigne, June & Soumis, Francois, 1998. "Multi-depot vehicle scheduling problems with time windows and waiting costs," European Journal of Operational Research, Elsevier, vol. 111(3), pages 479-494, December.
    14. Gilbert Laporte, 2009. "Fifty Years of Vehicle Routing," Transportation Science, INFORMS, vol. 43(4), pages 408-416, November.
    15. Gábor Nagy & Niaz A. Wassan & M. Grazia Speranza & Claudia Archetti, 2015. "The Vehicle Routing Problem with Divisible Deliveries and Pickups," Transportation Science, INFORMS, vol. 49(2), pages 271-294, May.
    16. Hernandez, Florent & Feillet, Dominique & Giroudeau, Rodolphe & Naud, Olivier, 2016. "Branch-and-price algorithms for the solution of the multi-trip vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 249(2), pages 551-559.
    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. Wadi Khalid Anuar & Lai Soon Lee & Hsin-Vonn Seow & Stefan Pickl, 2021. "A Multi-Depot Vehicle Routing Problem with Stochastic Road Capacity and Reduced Two-Stage Stochastic Integer Linear Programming Models for Rollout Algorithm," Mathematics, MDPI, vol. 9(13), pages 1-44, July.
    2. Yu, Vincent F. & Jodiawan, Panca & Hou, Ming-Lu & Gunawan, Aldy, 2021. "Design of a two-echelon freight distribution system in last-mile logistics considering covering locations and occasional drivers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 154(C).
    3. Baek, Jieun & Choi, Yosoon, 2023. "Optimal installation and operation planning of parking spaces for solar-powered electric vehicles using hemispherical images," Renewable Energy, Elsevier, vol. 219(P1).
    4. Ostermeier, Manuel & Heimfarth, Andreas & Hübner, Alexander, 2023. "The multi-vehicle truck-and-robot routing problem for last-mile delivery," European Journal of Operational Research, Elsevier, vol. 310(2), pages 680-697.
    5. Yu Feng & Xiaochun Lu, 2021. "Construction Planning and Operation of Battery Swapping Stations for Electric Vehicles: A Literature Review," Energies, MDPI, vol. 14(24), pages 1-19, December.
    6. Mehrnaz Bathaee & Hamed Nozari & Agnieszka Szmelter-Jarosz, 2023. "Designing a New Location-Allocation and Routing Model with Simultaneous Pick-Up and Delivery in a Closed-Loop Supply Chain Network under Uncertainty," Logistics, MDPI, vol. 7(1), pages 1-33, January.
    7. Saldanha-da-Gama, Francisco, 2022. "Facility Location in Logistics and Transportation: An enduring relationship," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 166(C).
    8. Pina-Pardo, Juan C. & Silva, Daniel F. & Smith, Alice E. & Gatica, Ricardo A., 2024. "Fleet resupply by drones for last-mile delivery," European Journal of Operational Research, Elsevier, vol. 316(1), pages 168-182.
    9. Eskandarzadeh, Saman & Fahimnia, Behnam, 2022. "Rest break policy comparison for heavy vehicle drivers in Australia," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 159(C).
    10. Wang, Yong & Luo, Siyu & Fan, Jianxin & Zhen, Lu, 2024. "The multidepot vehicle routing problem with intelligent recycling prices and transportation resource sharing," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 185(C).
    11. Md Saiful Islam & Md Sarowar Morshed & Md. Noor-E-Alam, 2022. "A Computational Framework for Solving Nonlinear Binary Optimization Problems in Robust Causal Inference," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 3023-3041, November.
    12. Zhang, Zhenzhen & Che, Yuxin & Liang, Zhe, 2024. "Split-demand multi-trip vehicle routing problem with simultaneous pickup and delivery in airport baggage transit," European Journal of Operational Research, Elsevier, vol. 312(3), pages 996-1010.
    13. Asadi, Amin & Nurre Pinkley, Sarah, 2021. "A stochastic scheduling, allocation, and inventory replenishment problem for battery swap stations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 146(C).
    14. Cui, Weiwei & Yang, Yiran & Di, Lei, 2023. "Modeling and optimization for static-dynamic routing of a vehicle with additive manufacturing equipment," International Journal of Production Economics, Elsevier, vol. 257(C).
    15. Meng, Lingpeng & Wang, Xudong & He, Junliang & Han, Chuanfeng & Hu, Shaolong, 2023. "A two-stage chance constrained stochastic programming model for emergency supply distribution considering dynamic uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 179(C).
    16. Sadati, Mir Ehsan Hesam & Çatay, Bülent, 2021. "A hybrid variable neighborhood search approach for the multi-depot green vehicle routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 149(C).
    17. Liu, Dan & Yan, Pengyu & Pu, Ziyuan & Wang, Yinhai & Kaisar, Evangelos I., 2021. "Hybrid artificial immune algorithm for optimizing a Van-Robot E-grocery delivery system," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 154(C).
    18. He, Dongdong & Ceder, Avishai (Avi) & Zhang, Wenyi & Guan, Wei & Qi, Geqi, 2023. "Optimization of a rural bus service integrated with e-commerce deliveries guided by a new sustainable policy in China," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 172(C).
    19. A. Mor & M. G. Speranza, 2022. "Vehicle routing problems over time: a survey," Annals of Operations Research, Springer, vol. 314(1), pages 255-275, July.
    20. Yang, Weibo & Ke, Liangjun & Wang, David Z.W. & Lam, Jasmine Siu Lee, 2021. "A branch-price-and-cut algorithm for the vehicle routing problem with release and due dates," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 145(C).
    21. Yong Wang & Jiayi Zhe & Xiuwen Wang & Yaoyao Sun & Haizhong Wang, 2022. "Collaborative Multidepot Vehicle Routing Problem with Dynamic Customer Demands and Time Windows," Sustainability, MDPI, vol. 14(11), pages 1-37, May.
    22. Yang, Fei & Dai, Ying & Ma, Zu-Jun, 2020. "A cooperative rich vehicle routing problem in the last-mile logistics industry in rural areas," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 141(C).
    23. Li, Hongqi & Wang, Feilong & Zhan, Zhuopeng, 2024. "Drone routing problem with swarm synchronization," European Journal of Operational Research, Elsevier, vol. 314(2), pages 477-495.
    24. Meng, Shanshan & Chen, Yanru & Li, Dong, 2024. "The multi-visit drone-assisted pickup and delivery problem with time windows," European Journal of Operational Research, Elsevier, vol. 314(2), pages 685-702.

    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. Babagolzadeh, Mahla & Zhang, Yahua & Abbasi, Babak & Shrestha, Anup & Zhang, Anming, 2022. "Promoting Australian regional airports with subsidy schemes: Optimised downstream logistics using vehicle routing problem," Transport Policy, Elsevier, vol. 128(C), pages 38-51.
    2. A. Mor & M. G. Speranza, 2022. "Vehicle routing problems over time: a survey," Annals of Operations Research, Springer, vol. 314(1), pages 255-275, July.
    3. Campelo, Pedro & Neves-Moreira, Fábio & Amorim, Pedro & Almada-Lobo, Bernardo, 2019. "Consistent vehicle routing problem with service level agreements: A case study in the pharmaceutical distribution sector," European Journal of Operational Research, Elsevier, vol. 273(1), pages 131-145.
    4. Benjamin C. Shelbourne & Maria Battarra & Chris N. Potts, 2017. "The Vehicle Routing Problem with Release and Due Dates," INFORMS Journal on Computing, INFORMS, vol. 29(4), pages 705-723, November.
    5. Pina-Pardo, Juan C. & Silva, Daniel F. & Smith, Alice E. & Gatica, Ricardo A., 2024. "Fleet resupply by drones for last-mile delivery," European Journal of Operational Research, Elsevier, vol. 316(1), pages 168-182.
    6. A. Mor & M. G. Speranza, 2020. "Vehicle routing problems over time: a survey," 4OR, Springer, vol. 18(2), pages 129-149, June.
    7. Baals, Julian & Emde, Simon & Turkensteen, Marcel, 2023. "Minimizing earliness-tardiness costs in supplier networks—A just-in-time truck routing problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 707-741.
    8. Diego Cattaruzza & Nabil Absi & Dominique Feillet, 2018. "Vehicle routing problems with multiple trips," Annals of Operations Research, Springer, vol. 271(1), pages 127-159, December.
    9. Diego Cattaruzza & Nabil Absi & Dominique Feillet, 2016. "Vehicle routing problems with multiple trips," 4OR, Springer, vol. 14(3), pages 223-259, September.
    10. Wang, Zheng, 2018. "Delivering meals for multiple suppliers: Exclusive or sharing logistics service," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 118(C), pages 496-512.
    11. 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.
    12. Ines Sbai & Saoussen Krichen & Olfa Limam, 2022. "Two meta-heuristics for solving the capacitated vehicle routing problem: the case of the Tunisian Post Office," Operational Research, Springer, vol. 22(1), pages 507-549, March.
    13. Huang, Nan & Li, Jiliu & Zhu, Wenbin & Qin, Hu, 2021. "The multi-trip vehicle routing problem with time windows and unloading queue at depot," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    14. Marlin W. Ulmer & Barrett W. Thomas & Ann Melissa Campbell & Nicholas Woyak, 2021. "The Restaurant Meal Delivery Problem: Dynamic Pickup and Delivery with Deadlines and Random Ready Times," Transportation Science, INFORMS, vol. 55(1), pages 75-100, 1-2.
    15. Martin Wölck & Stephan Meisel, 2022. "Branch-and-Price Approaches for Real-Time Vehicle Routing with Picking, Loading, and Soft Time Windows," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 2192-2211, July.
    16. Yang, Weibo & Ke, Liangjun & Wang, David Z.W. & Lam, Jasmine Siu Lee, 2021. "A branch-price-and-cut algorithm for the vehicle routing problem with release and due dates," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 145(C).
    17. Yu Zhang & Zhenzhen Zhang & Andrew Lim & Melvyn Sim, 2021. "Robust Data-Driven Vehicle Routing with Time Windows," Operations Research, INFORMS, vol. 69(2), pages 469-485, March.
    18. Liu, Shixin & Qin, Shujin & Zhang, Ruiyou, 2018. "A branch-and-price algorithm for the multi-trip multi-repairman problem with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 116(C), pages 25-41.
    19. Cheng, Chun & Adulyasak, Yossiri & Rousseau, Louis-Martin, 2020. "Drone routing with energy function: Formulation and exact algorithm," Transportation Research Part B: Methodological, Elsevier, vol. 139(C), pages 364-387.
    20. Zhiping Zuo & Yanhui Li & Jing Fu & Jianlin Wu, 2019. "Human Resource Scheduling Model and Algorithm with Time Windows and Multi-Skill Constraints," Mathematics, MDPI, vol. 7(7), pages 1-18, 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:135:y:2020:i:c:s1366554519301486. 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.