Optimization Online


Multi-depot routing with split deliveries: Models and a branch-and-cut algorithm

Luis Gouveia(legouveia***at***fc.ul.pt)
Markus Leitner(m.leitner***at***vu.nl)
Mario Ruthmair(mario.ruthmair***at***univie.ac.at)

Abstract: We study the split-delivery multi-depot vehicle routing problem (MDSDVRP) which 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 comparably 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 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

Category 1: Applications -- OR and Management Sciences


Download: [PDF]

Entry Submitted: 10/27/2021
Entry Accepted: 10/27/2021
Entry Last Modified: 10/27/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society