A branch-cut-and-price algorithm for the distance constrained multi-depot vehicle routing problem

Ruslan Sadykov 1 Artur Alves Pessoa 2 Eduardo Uchoa 2
1 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 work we propose a new Branch-Cut-and-Price algorithm for the distance constrained multi-depot vehicle routing problem. The algorithm combines many state-of-the-art techniques known to be efficient for routing problems : bi-directional ng-path based labelling algorithm to solve the pricing problem, generation of limited memory rank-1 cuts with up to 5 rows, reduced cost fixing of arcs, enumeration of elementary routes, and multi-phase strong branching with pseudo-costs. The main contribution of this work is an improvement of the labelling algorithm for the resource constrained shortest path problem with two resources. The labels with similar resource consumption are stored in buckets which are organised in so-called bucket graph. This organisation allows one to significantly reduce the number of dominance checks, exploit route symmetry, and perform reduced cost fixing of bucket arcs. Experiments showed that our algorithm is able to solve to optimality several open instances of the problem with up to 216 customers within the 2 hours time limit. The improvement of the solution time over the recent state-of-the-art algorithm by Contardo and Martinelli (2014) is up to two-three orders of magnitude.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-01676023
Contributor : Ruslan Sadykov <>
Submitted on : Friday, January 5, 2018 - 9:18:56 AM
Last modification on : Friday, February 1, 2019 - 3:24:03 PM

Identifiers

  • HAL Id : hal-01676023, version 1

Citation

Ruslan Sadykov, Artur Alves Pessoa, Eduardo Uchoa. A branch-cut-and-price algorithm for the distance constrained multi-depot vehicle routing problem. IFORS 2017 - 21st Conference of the International Federation of Operational Research Societies, Jul 2017, Quebec City, Canada. ⟨hal-01676023⟩

Share

Metrics

Record views

113