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

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. Funding: This work was supported by the Fundação para a Ciência e a Tecnologia [Project UIDB/04561/2020]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.1179 .