Solving the robust CVRP under demand uncertainty

Artur 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 : In this paper, we propose a Branch-Cut-and-price algorithm for the robust counterpart of the classical Capacitated Vehicle Routing Problem (CVRP). The deterministic version of this problem consists of finding a set of vehicle routes to serve a given set of customers with associated demands such that the sum of demands served by each vehicle does not exceed its capacity, and each customer is served exactly once. The total travel cost, given by the sum of distances traversed by all vehicles must be minimized. Here, only customer demands are assumed to be uncertain. We consider two types of uncertainty sets for the vector of customer demands: the classical budget polytope introduced by Bertsimas and Sim (2003), and a partitioned budget polytope, proposed by Gounaris et al (2013) for the CVRP with uncertain demands. The method proposed in this paper uses a set partitioning formulation to solve the problem, where each binary variable determines whether a given route is included or not in the solution. It considers only the routes that satisfy the capacity constraints for all possible demand vectors allowed by the uncertainty polytope. The linear relaxation for this formulation is solved by column generation, where the pricing subproblem is decomposed into a small number of deterministic subproblems with modified demand vectors. This reformulation allows the use of state-of-the-art techniques such as ng-routes, rank-1 cuts, specialized labeling algorithms, fixing by reduced costs and route enumeration. As a result, we were able to solve all 47 open instances proposed by Gounaris et al (2013), the largest one having 150 customers.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-01703181
Contributor : François Vanderbeck <>
Submitted on : Monday, December 17, 2018 - 3:42:07 PM
Last modification on : Thursday, February 7, 2019 - 5:25:17 PM
Long-term archiving on : Monday, March 18, 2019 - 3:01:09 PM

File

robustCVRPodysseus-2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01703181, version 1

Citation

Artur Pessoa, Michael Poss, Ruslan Sadykov, François Vanderbeck. Solving the robust CVRP under demand uncertainty. ODYSSEUS, Jun 2018, Calgliari, Italy. ⟨hal-01703181⟩

Share

Metrics

Record views

574

Files downloads

81