Journal
TRANSPORTATION SCIENCE
Volume 55, Issue 1, Pages 4-28Publisher
INFORMS
DOI: 10.1287/trsc.2020.0985
Keywords
labeling algorithm; shortest path with resource constraints; routing
Categories
Funding
- Fundacao Carlos Chagas Filho de Amparo 'a Pesquisa do Estado do Rio de Janeiro, FAPERJ [E26/110.075/2014]
Ask authors/readers for more resources
In this study, a new variant of bidirectional label-correcting algorithm is proposed for the vehicle routing problem, which uses bucket graph to store and extend labels, reducing dominance checks and algorithm running time significantly, especially beneficial for large vehicle capacity and time window constraints. Experiments showed significant improvements over the best algorithms in literature on instances such as distance-constrained vehicle routing and heterogeneous fleet vehicle routing, with many instances being solved for the first time.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available