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

Michiel A. J. uit het Broek (), Albert H. Schrotenboer (), Bolor Jargalsaikhan (), Kees Jan Roodbergen () and Leandro C. Coelho ()
Additional contact information
Michiel A. J. uit het Broek: Department of Operations, Faculty of Economics and Business, University of Groningen, 9712 CP Groningen, Netherlands;
Albert H. Schrotenboer: Department of Operations, Faculty of Economics and Business, University of Groningen, 9712 CP Groningen, Netherlands;
Bolor Jargalsaikhan: Department of Operations, Faculty of Economics and Business, University of Groningen, 9712 CP Groningen, Netherlands;
Kees Jan Roodbergen: Department of Operations, Faculty of Economics and Business, University of Groningen, 9712 CP Groningen, Netherlands;
Leandro C. Coelho: Department of Operations, Faculty of Economics and Business, University of Groningen, 9712 CP Groningen, Netherlands; CIRRELT and Université Laval, Québec, Québec G1V 0A6, Canada; Research Chair in Integrated Logistics, Université Laval, Québec, Québec G1V 0A6, Canada

Operations Research, 2021, vol. 69, issue 2, 380-409

Abstract: We present a generic branch-and-cut framework for solving routing problems with multiple depots and asymmetric cost structures, which determines a set of cost-minimizing (capacitated) vehicle tours that fulfill a set of customer demands. The backbone of the framework is a series of valid inequalities with corresponding separation algorithms that exploit the asymmetric cost structure in directed graphs. We derive three new classes of so-called D k inequalities that eliminate subtours, enforce tours to be linked to a single depot, and impose bounds on the number of customers in a tour. In addition, other well-known valid inequalities for solving vehicle routing problems are generalized and adapted to be valid for routing problems with multiple depots and asymmetric cost structures. The framework is tested on four specific problem variants, for which we develop a new set of large-scale benchmark instances. The results show that the new inequalities can reduce root-node optimality gaps by up to 67.2% compared with existing approaches. Moreover, the complete framework is very effective and can solve instances of considerably larger size than reported in the literature. For instance, it solves asymmetric multidepot traveling-salesman-problem instances containing up to 400 customers and 50 depots, whereas to date only solutions of instances containing up to 300 customer nodes and 60 depots have been reported.

Keywords: branch-and-cut; valid inequalities; asymmetric; multidepot; vehicle routing; upper-bound procedure (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/opre.2020.2033 (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:oropre:v:69:y:2021:i:2:p:380-409

Access Statistics for this article

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