Multi-depot routing with split deliveries (paper accepted in Transportation Science)

The paper Multi-depot routing with split deliveries: Models and a branch-and-cut algorithm co-authored with Luis Gouveia (University of Lisbon) and Mario Ruthmair (Gurobi Optimization) has been accepted for publication in the journal Transportation Science (a preprint can be found on optimization online). In this work, we study the multi-depot split-delivery vehicle routing problem (MDSDVRP) which has been introduced by D. Gulczynski, B. Golden, and E. Wasil in 2011. The MDSDVRP offers a potential to increase the efficiency of (last-mile) delivery and additional cost-savings by combining deliveries from multiple origins (depots) with the opportunity to satisfy individual customer demands by more than one vehicle (split-delivery).

In our paper we propose a new mathematical (mixed-integer) programming formulation for the MDSDVRP and several new families of inequalities. We also study theoretical properties of the newly introduced inequalities and use the obtained results to design and implement the first exact solution algorithm for the MDSDVRP. In addition to the first proven optimal solutions to MDSDVRP instances, the results of our extensive computational study also show that our algorithm is competitive to state-of-the-art algorithms for a problem variant with a single depot (the well-known split-delivery vehicle routing problem) and significantly outperforms the previous state-of-the-art method in case demands of individual customers must be satisfied by single vehicles (the multi-depot traveling salesperson problem).