Multi-Depot Routing with Split Deliveries: Models and a Branch-and-Cut Algorithm

Luis Gouveia (), Markus Leitner () and Mario Ruthmair ()
Additional contact information
Luis Gouveia: Centro de Matemática, Aplicaçães Fundamentais e Investigação Operacional, Departamento de Estatística e Investigação Operacional, Faculdade de Ciências, Universidade de Lisboa, 1749-016 Lisboa, Portugal
Markus Leitner: Department of Operations Analytics, Vrije Universiteit, 1081 HV Amsterdam, Netherlands
Mario Ruthmair: Department of Operations Analytics, Vrije Universiteit, 1081 HV Amsterdam, Netherlands; Department of Statistics and Operations Research, University of Vienna, 1090 Vienna, Austria; Department of Mathematics, University of Klagenfurt, 9020 Klagenfurt, Austria

Transportation Science, 2023, vol. 57, issue 2, 512-530

Abstract: We study the multi-depot split-delivery vehicle routing problem (MDSDVRP) that combines the advantages and potential cost savings of multiple depots and split deliveries and develop the first exact algorithm for this problem. We propose an integer programming formulation using a small number of decision variables and several sets of valid inequalities. These inequalities focus on ensuring the vehicles’ capacity limits and that vehicles return to their initial depot. As we show that the new constraints do not guarantee these aspects, our branch-and-cut framework also includes an efficient feasibility check for candidate solutions and explicit feasibility cuts. The algorithm that also uses a comparably simple, yet effective heuristic to compute high-quality initial solutions is tested on the MDSDVRP and two well-known special cases, the split-delivery vehicle routing problem (SDVRP) and the multi-depot traveling salesman problem (MDTSP). The results show that the new inequalities tighten the linear programming relaxation, increase the performance of the branch-and-cut algorithm, and reduce the number of required feasibility cuts. We report the first proven optimal results for the MDSDVRP and show that our algorithm significantly outperforms the state-of-the-art for the MDTSP while being competitive on the SDVRP. For the latter, 20 instances are solved for the first time, and new best primal and dual bounds are found for others.

Keywords: vehicle routing; multi-depot; split delivery; branch-and-cut; valid inequalities (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2022.1179 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:57:y:2023:i:2:p:512-530

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().