European Business Schools Librarian's Group

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

No L-2004-05: K shortest paths in stochastic time-dependent networks

Lars Relund Nielsen, Daniele Pretolani and Kim Allan Andersen ()
Additional contact information
Lars Relund Nielsen: Biometry Research Unit, Postal: Danish Institute of Agricultural Sciences, Research Centre Foulum, P.O.Box 50, DK-8830 Tjele
Daniele Pretolani: Dipartimento de Matematica e Informatica, Postal: Universita di Camerino, Via Madonna delle Carcera, I-62032 Camerino (MC), Italy,
Kim Allan Andersen: Department of Business Studies, Postal: The Aarhus School of Business, Fuglesangs Allé 4, 8210 Aarhus V, Denmark

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 PDF-file 

Download statistics

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 ().

This page generated on 2024-02-12 04:36:14.