IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v317y2024i2p500-514.html
   My bibliography  Save this article

An accelerated benders decomposition algorithm for the solution of the multi-trip time-dependent vehicle routing problem with time windows

Author

Listed:
  • Fragkogios, Antonios
  • Qiu, Yuzhuo
  • Saharidis, Georgios K.D.
  • Pardalos, Panos M.

Abstract

The logistics companies executing the last mile delivery of goods in urban areas deal every day with the problem of routing their vehicles, while taking into account multiple trips per vehicle, time-dependent travel time, customers’ time windows and loading time at the depot simultaneously. This paper addresses this problem, known as Multi-Trip Time-Dependent Vehicle Routing Problem with Time Windows, aiming at its exact solution, minimizing the total travelled distance of a company's fleet. Based on a literature model, a new reformulation with reduced size is suggested. This reformulation is decomposed by applying the Benders method in an effective way, resulting in a subproblem with no duality gap. By exploiting the special features of the problem and the particular structure of the decomposition made, several novel valid inequalities are introduced, in order to both tighten the non-decomposed formulations and warm start the relaxed master problem to achieve less infeasible solutions and higher lower bounds. For the solution of the problem, an innovative algorithm is proposed, including suboptimal master solutions and a multi-cut generation procedure, which is based on the careful observation of the values of the Benders dual subproblem variables. The impact of the valid inequalities as well as two variants of the suggested algorithm are tested on benchmark data and they are compared with the non-decomposed models and a heuristic introduced in the literature. The computational results indicate improved efficiency and stronger bounds for the proposed algorithm.

Suggested Citation

  • Fragkogios, Antonios & Qiu, Yuzhuo & Saharidis, Georgios K.D. & Pardalos, Panos M., 2024. "An accelerated benders decomposition algorithm for the solution of the multi-trip time-dependent vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 317(2), pages 500-514.
    • Handle: RePEc:eee:ejores:v:317:y:2024:i:2:p:500-514
    DOI: 10.1016/j.ejor.2024.04.013
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221724002947
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2024.04.013?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. 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.
    2. Grigorios D. Konstantakopoulos & Sotiris P. Gayialis & Evripidis P. Kechagias, 2022. "Vehicle routing problem and related algorithms for logistics distribution: a literature review and classification," Operational Research, Springer, vol. 22(3), pages 2033-2062, July.
    3. Halit Üster & Gopalakrishnan Easwaran & Elif Akçali & Sila Çetinkaya, 2007. "Benders decomposition with alternative multiple cuts for a multi‐product closed‐loop supply chain network design model," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(8), pages 890-907, December.
    4. Fengqi You & Ignacio Grossmann, 2013. "Multicut Benders decomposition algorithm for process supply chain planning under uncertainty," Annals of Operations Research, Springer, vol. 210(1), pages 191-211, November.
    5. G. Dantzig & R. Fulkerson & S. Johnson, 1954. "Solution of a Large-Scale Traveling-Salesman Problem," Operations Research, INFORMS, vol. 2(4), pages 393-410, November.
    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. 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.
    8. Ashkan Fakhri & Antonios Fragkogios & Georgios K. D. Saharidis, 2021. "An Accelerated Benders Decomposition Algorithm for Solving a Double-Type Double-Standard Maximal Covering Location Problem," SN Operations Research Forum, Springer, vol. 2(1), pages 1-24, March.
    9. A. M. Geoffrion & G. W. Graves, 1974. "Multicommodity Distribution System Design by Benders Decomposition," Management Science, INFORMS, vol. 20(5), pages 822-844, January.
    10. Ampol Karoonsoontawong & Puntipa Punyim & Wanvara Nueangnitnaraporn & Vatanavongs Ratanavaraha, 2020. "Multi-Trip Time-Dependent Vehicle Routing Problem with Soft Time Windows and Overtime Constraints," Networks and Spatial Economics, Springer, vol. 20(2), pages 549-598, June.
    11. Jie Zhang & Yifan Zhu & Xiaobo Li & Mengjun Ming & Weiping Wang & Tao Wang, 2022. "Multi-Trip Time-Dependent Vehicle Routing Problem with Split Delivery," Mathematics, MDPI, vol. 10(19), pages 1-24, September.
    12. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    13. 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.
    14. Ceyhan, Gökhan & Köksalan, Murat & Lokman, Banu, 2022. "Extensions for Benders cuts and new valid inequalities for solving the European day-ahead electricity market clearing problem efficiently," European Journal of Operational Research, Elsevier, vol. 300(2), pages 713-726.
    15. 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.
    16. N. Beheshti Asl & S. A. MirHassani, 2019. "Accelerating benders decomposition: multiple cuts via multiple solutions," Journal of Combinatorial Optimization, Springer, vol. 37(3), pages 806-826, April.
    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. Liu, Yiming & Roberto, Baldacci & Zhou, Jianwen & Yu, Yang & Zhang, Yu & Sun, Wei, 2023. "Efficient feasibility checks and an adaptive large neighborhood search algorithm for the time-dependent green vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 310(1), pages 133-155.
    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. Weninger, Dieter & Wolsey, Laurence A., 2023. "Benders-type branch-and-cut algorithms for capacitated facility location with single-sourcing," European Journal of Operational Research, Elsevier, vol. 310(1), pages 84-99.
    4. Luciano Costa & Claudio Contardo & Guy Desaulniers, 2019. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing," Transportation Science, INFORMS, vol. 53(4), pages 946-985, July.
    5. Zhixing Luo & Hu Qin & Wenbin Zhu & Andrew Lim, 2017. "Branch and Price and Cut for the Split-Delivery Vehicle Routing Problem with Time Windows and Linear Weight-Related Cost," Transportation Science, INFORMS, vol. 51(2), pages 668-687, May.
    6. Aarabi, Fatemeh & Batta, Rajan, 2020. "Scheduling spatially distributed jobs with degradation: Application to pothole repair," Socio-Economic Planning Sciences, Elsevier, vol. 72(C).
    7. 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.
    8. Denise D. Tönissen & Joachim J. Arts & Zuo-Jun Max Shen, 2021. "A column-and-constraint generation algorithm for two-stage stochastic programming problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(3), pages 781-798, October.
    9. 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.
    10. 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).
    11. Nader Ghaffarinasab & Bahar Y. Kara, 2019. "Benders Decomposition Algorithms for Two Variants of the Single Allocation Hub Location Problem," Networks and Spatial Economics, Springer, vol. 19(1), pages 83-108, March.
    12. Jie Zhang & Yifan Zhu & Xiaobo Li & Mengjun Ming & Weiping Wang & Tao Wang, 2022. "Multi-Trip Time-Dependent Vehicle Routing Problem with Split Delivery," Mathematics, MDPI, vol. 10(19), pages 1-24, September.
    13. Attari, Mahdi Yousefi Nejad & Torkayesh, Ali Ebadi, 2018. "Developing benders decomposition algorithm for a green supply chain network of mine industry: Case of Iranian mine industry," Operations Research Perspectives, Elsevier, vol. 5(C), pages 371-382.
    14. Gendreau, Michel & Nossack, Jenny & Pesch, Erwin, 2015. "Mathematical formulations for a 1-full-truckload pickup-and-delivery problem," European Journal of Operational Research, Elsevier, vol. 242(3), pages 1008-1016.
    15. 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.
    16. Koç, Çağrı & Bektaş, Tolga & Jabali, Ola & Laporte, Gilbert, 2016. "The fleet size and mix location-routing problem with time windows: Formulations and a heuristic algorithm," European Journal of Operational Research, Elsevier, vol. 248(1), pages 33-51.
    17. 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.
    18. Özgün Elçi & John Hooker, 2022. "Stochastic Planning and Scheduling with Logic-Based Benders Decomposition," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2428-2442, September.
    19. 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.
    20. Rey, David & Almi’ani, Khaled & Nair, Divya J., 2018. "Exact and heuristic algorithms for finding envy-free allocations in food rescue pickup and delivery logistics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 112(C), pages 19-46.

    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:ejores:v:317:y:2024:i:2:p:500-514. 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/locate/eor .

    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.