Scandinavian Working Papers in Business Administration

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 (kia@asb.dk)
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 (hes@asb.dk)
Report other problems with accessing this service to Sune Karlsson (sune.karlsson@oru.se).

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