Skip to Main content Skip to Navigation
Journal articles

A Bucket Graph Based Labelling Algorithm for Vehicle Routing

Ruslan Sadykov 1 Artur 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 : We consider the Shortest Path Problem with Resource Constraints (SPPRC) arising as a subproblem in state-of-the-art Branch-Cut-and-Price algorithms for vehicle routing problems. We propose a variant of the bi-directional label correcting algorithm in which the labels are stored and extended according to the so-called bucket graph. Such organization of labels helps to decrease significantly the number of dominance checks and the running time of the algorithm. We also show how the forward/backward route symmetry can be exploited and how to eliminate arcs from the bucket graph using reduced costs. The proposed algorithm can be especially beneficial for vehicle routing instances with large vehicle capacity and/or with time window constraints. Computational experiments were performed on instances from the distance constrained vehicle routing problem, including multi-depot and site-dependent variants, on the vehicle routing problem with time windows, and on the "nightmare" instances of the heterogeneous fleet vehicle routing problem. Significant improvements over the best algorithms in the literature were achieved and many instances could be solved for the first time.
Document type :
Journal articles
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-02378624
Contributor : Ruslan Sadykov <>
Submitted on : Tuesday, November 3, 2020 - 5:35:54 PM
Last modification on : Thursday, November 5, 2020 - 3:34:00 AM

File

BucketGraph-final-clear.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Ruslan Sadykov, Artur Pessoa, Eduardo Uchoa. A Bucket Graph Based Labelling Algorithm for Vehicle Routing. Transportation Science, INFORMS, 2020, Ahead of Print, ⟨10.1287/trsc.2020.0985⟩. ⟨hal-02378624v2⟩

Share

Metrics

Record views

31

Files downloads

69