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