© 2021 Elsevier LtdIn this paper we study a property of time-dependent graphs, dubbed “path ranking invariance”. Broadly speaking, a time-dependent graph is “path ranking invariant” if the ordering of its paths (w.r.t. travel time) is independent of the start time. In this paper we show that, if a graph is path ranking invariant, the solution of a large class of time-dependent vehicle routing problems can be obtained by solving suitably defined (and simpler) time-independent routing problems. We also show how this property can be checked by solving a linear program. If the check fails, the solution of the linear program can be used to determine a tight lower bound. In order to assess the value of these insights, the lower bounds have been embedded into an enumerative scheme. Computational results on the time-dependent versions of the Travelling Salesman Problem and the Rural Postman Problem show that the new findings enable to outperform state-of-the-art algorithms.
https://doi.org/10.1016/j.cor.2021.105446Cite as:
@article{Adamo_2021,
doi = {10.1016/j.cor.2021.105446},
url = {https://doi.org/10.1016%2Fj.cor.2021.105446},
year = 2021,
month = {nov},
publisher = {Elsevier {BV}},
volume = {135},
pages = {105446},
author = {Tommaso Adamo and Gianpaolo Ghiani and Emanuela Guerriero},
title = {On path ranking in time-dependent graphs},
journal = {Computers {&}amp$mathsemicolon$ Operations Research}
}