PESSOA, Artur Alves; POSS, Michael; VANDERBECK, François; SADYKOV, Ruslan; VANDERBECK, Francois

doi:10.1287/opre.2020.2035

Métadonnées

Afficher la notice complète

Licence d’utilisation du document

PESSOA, Artur Alves
Universidade Federal Fluminense [Rio de Janeiro] [UFF]

POSS, Michael
Methods, Algorithms for Operations REsearch [MAORE]

VANDERBECK, François
Reformulations based algorithms for Combinatorial Optimization [Realopt]

Langue

Article de revue

Ce document a été publié dans

Operations Research. 2021, vol. 69, n° 3, p. 739-754

INFORMS

Résumé en anglais

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.< Réduire

Mots clés en anglais

Capacity inequalities

Branch-cut-and-price

Local search

Branch-and-cut-and-price

Robust optimization

URI

https://oskar-bordeaux.fr/handle/20.500.12278/192342

DOI

http://dx.doi.org/10.1287/opre.2020.2035

Project ANR

Ordonancement robuste avec durée incertaines pour une incertitude de type budget - ANR-16-CE40-0018

Origine

Importé de hal

Unités de recherche

Institut de Mathématiques de Bordeaux (IMB) - UMR 5251