Department of Economics and Business Economics

Ranking paths in stochastic time-dependent networks

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

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.
Original languageEnglish
JournalEuropean Journal of Operational Research
Pages (from-to)903-914
Number of pages12
Publication statusPublished - 1 Aug 2014

    Research areas

  • Ranking, Routing, Shortest paths, Stochastic time-dependent networks

See relations at Aarhus University Citationformats

ID: 75022548