← Search

Asymmetric Multidepot Vehicle Routing Problems: Valid Inequalities and a Branch-and-Cut Algorithm

Michiel A. J. uit het Broek1; Albert H. Schrotenboer1; Bolor Jargalsaikhan1; Kees Jan Roodbergen1; Leandro C. Coelho1,2,3

1 Department of Operations, Faculty of Economics and Business, University of Groningen, 9712 CP Groningen, Netherlands; · 2 CIRRELT and Université Laval, Québec, Québec G1V 0A6, Canada; · 3 Research Chair in Integrated Logistics, Université Laval, Québec, Québec G1V 0A6, Canada

Operations Research 2021

In “Asymmetric Multidepot Vehicle Routing Problems: Valid Inequalities and a Branch-and-Cut Algorithm,” Uit het Broek, Schrotenboer, Jargalsaikhan, Roodbergen, and Coelho present a generic branch-and-cut framework to solve routing problems with multiple depots on directed graphs. They present new valid inequalities that eliminate subtours, enforce tours to be linked to the same depot, and enforce bounds on the number of customers in a vehicle tour. This is embedded in a branch-and-cut scheme that also contains generalized and adapted versions of valid inequalities that are well known for related routing problems. The authors show that the new inequalities tighten root node relaxations considerably. In combination with a simple but effective upper-bound procedure, only requiring a MIP solver and a smart reduction of the problem size, the authors show that the overall framework solves instances of considerably larger size to optimality than have been reported in the literature.

DOI
10.1287/opre.2020.2033
Volume
69 (2)
Pages
380-409
Language
en
Export
BibTeX
Sources
crossref