A Bucket Graph–Based Labeling Algorithm with Application to Vehicle Routing

Ruslan Sadykov (), Eduardo Uchoa () and Artur Pessoa ()
Additional contact information
Ruslan Sadykov: INRIA Bordeaux Sud-Ouest, 33405 Talence, France; Institute of Mathematics, University of Bordeaux, 3340 Talence, France;
Eduardo Uchoa: Engenharia de Produção, Universidade Federal Fluminense, Niterói, Brasil, 24210-240
Artur Pessoa: Engenharia de Produção, Universidade Federal Fluminense, Niterói, Brasil, 24210-240

Transportation Science, 2021, vol. 55, issue 1, 4-28

Abstract: We consider the shortest path problem with resource constraints arising as a subproblem in state-of-the-art branch-cut-and-price algorithms for vehicle routing problems. We propose a variant of the bidirectional label-correcting algorithm in which the labels are stored and extended according to the so-called bucket graph. This organization of labels helps to significantly decrease 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 multidepot 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.

Keywords: labeling algorithm; shortest path with resource constraints; routing (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
https://doi.org/10.1287/trsc.2020.0985 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:55:y:2021:i:1:p:4-28

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().