In this paper we address optimal routing problems in networks where travel times are both stochastic and time-dependent. In these networks, the best route choice is not necessarily a path, but rather a time-adaptive strategy that assigns successors to nodes as a function of time. Nevertheless, in some particular cases an origin-destination path must be chosen a priori, since time-adaptive choices are not allowed. Unfortunately, finding the a priori shortest path is an NP-hard problem. In this paper, we propose a solution method for the a priori shortest path problem, and we show that it can be easily extended to the ranking of the first K shortest paths. Our method exploits the solution of the time-adaptive routing problem as a relaxation of the a priori problem. Computational results are presented showing that, under realistic distributions of travel times and costs, our solution methods are effective and robust. © 2013 Elsevier B.V. All rights reserved.
https://doi.org/10.1016/j.ejor.2013.10.022Cite as:
@article{Nielsen_2014,
doi = {10.1016/j.ejor.2013.10.022},
url = {https://doi.org/10.1016%2Fj.ejor.2013.10.022},
year = 2014,
month = {aug},
publisher = {Elsevier {BV}},
volume = {236},
number = {3},
pages = {903--914},
author = {Lars Relund Nielsen and Kim Allan Andersen and Daniele Pretolani},
title = {Ranking paths in stochastic time-dependent networks},
journal = {European Journal of Operational Research}
}