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, http://www.asb.dk/staff/bs/kia.aspx?page=%7B803EFF10-69F7-4C0F-AEE3-F7F410E4B6F2%7D

No L-2004-05, CORAL Working Papers from 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 (search for similar items in EconPapers)
Date: Written 2004-11-18
View list of references View citations in EconPapers

Downloads: (external link)
http://www.hha.dk/afl/wp/log/L_2004_05.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Access Statistics for this paper

More papers in CORAL Working Papers from University of Aarhus, Aarhus School of Business, Department of Business Studies
Address: The Aarhus School of Business, Fuglesangs Allé 4, DK-8210 Aarhus V, Denmark
Contact information at EDIRC.
Series data maintained by Helle Vinbaek Stenholt ().