Branch-and-cut-and-price for the robust capacitated vehicle routing problem with knapsack uncertainty

Artur Alves Pessoa 1 Michael Poss 2 Ruslan Sadykov 3 François Vanderbeck 3
2 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
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 introduced by Bertsimas and Sim (2003), and a partitioned budget polytope proposed by Gounaris et al. (2013). 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 for the robust counterpart, and a modern branch-and-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 which 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-and-cut-and-price algorithm incorporating existing and new techniques, we are able to solve to optimality all but one open instances from the literature.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/hal-01958184
Contributor : Michael Poss <>
Submitted on : Friday, April 26, 2019 - 10:01:10 AM
Last modification on : Saturday, April 27, 2019 - 1:42:58 AM

File

main_v4 (1).pdf
Files produced by the author(s)

Identifiers

Citation

Artur Alves Pessoa, Michael Poss, Ruslan Sadykov, François Vanderbeck. Branch-and-cut-and-price for the robust capacitated vehicle routing problem with knapsack uncertainty. [Research Report] Cadernos do LOGIS 2018-1, Universidade Federal Fluminense. 2018. ⟨hal-01958184v2⟩

Share

Metrics

Record views

101

Files downloads

207