Branch-Cut-and-Price for the Robust Capacitated Vehicle Routing Problem with Knapsack Uncertainty

Artur Alves Pessoa (), Michael Poss (), Ruslan Sadykov () and François Vanderbeck ()
Additional contact information
Artur Alves Pessoa: Production Engineering Department, Universidade Federal Fluminense, Niteroi RJ 24210-240, Brazil
Michael Poss: Laboratory of Computer Science, Robotics and Microelectronics of Montpellier, Centre National de la Recherche Scientifique, University of Montpellier, CNRS, France
Ruslan Sadykov: Bordeaux Research Center, INRIA, 33405 Talence, France
François Vanderbeck: Atoptima, SAS, Bordeaux, France, 33000

Operations Research, 2021, vol. 69, issue 3, 739-754

Abstract: We examine the robust counterpart of the classical capacitated vehicle routing problem (CVRP). We consider two types of uncertainty sets for the customer demands: the classical budget polytope and a partitioned budget polytope. We show that using the set-partitioning formulation it is possible to reformulate our problem as a deterministic heterogeneous vehicle routing problem. Thus, many state-of-the-art techniques for exactly solving deterministic VRPs can be applied to the robust counterpart, and a modern branch-cut-and-price algorithm can be adapted to our setting by keeping the number of pricing subproblems strictly polynomial. More importantly, we introduce new techniques to significantly improve the efficiency of the algorithm. We present analytical conditions under which a pricing subproblem is infeasible. This result is general and can be applied to other combinatorial optimization problems with knapsack uncertainty. We also introduce robust capacity cuts that are provably stronger than the ones known in the literature. Finally, a fast-iterated local search algorithm is proposed to obtain heuristic solutions for the problem. Using our branch-cut-and-price algorithm incorporating existing and new techniques, we solve to optimality all but one of the open instances from the literature.

Keywords: programming: integer: algorithms: branch-and-bound; programming: integer: applications; transportation: vehicle routing; Programming, Integer, Algorithms, Cutting plane; programming: robust optimization, Transportation, branch-cut-and-price, robust optimization, capacity inequalities, local search, vehicle routing (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2020.2035 (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:3:p:739-754

Access Statistics for this article

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