CORAL Working Papers,
University of Aarhus, Aarhus School of Business, Department of Business Studies

Abstract: A substantial amount of research has been devoted to the shortest path problem in networks where travel times are stochastic or (deterministic and) time-dependent. More recently, a growing interest has been attracted by networks that 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. In some particular cases, the shortest origin-destination path must nevertheless be chosen a priori, since time-adaptive choices are not allowed. Unfortunately, finding the a priori shortest path is NP-hard, while the best time-adaptive strategy can be found in polynomial time. In this paper, we propose a solution method for the a priori shortest path problem, and we show that it can be easily adapted to the ranking of the first K shortest paths. Moreover, we present a computational comparison of time-adaptive and a priori route choices, pointing out the effect of travel time and cost distributions. The reported results show that, under realistic distributions, our solution methods are effective

Keywords: Shortest paths; K shortest paths; stochastic time-dependent networks; routing; directed hypergraphs

29 pages, November 18, 2004

Full text files

L_2004_05.pdf  

Download statistics

• University of Aarhus, Aarhus School of Business, Department of Business Studies
• Home page for this series

Questions (including download problems) about the papers in this series should be directed to Helle Vinbaek Stenholt ()
Report other problems with accessing this service to Sune Karlsson ().

RePEc:hhb:aarbls:2004-005This page generated on 2024-09-13 22:18:12.