K shortest paths in stochastic time-dependent networks
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
|Date of creation:||18 Nov 2004|
|Date of revision:|
|Contact details of provider:|| Postal: |
Fax: + 45 86 15 19 43
Web page: http://www.asb.dk/about/departments/bs.aspx
More information through EDIRC
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Pretolani, Daniele, 2000. "A directed hypergraph model for random time dependent shortest paths," European Journal of Operational Research, Elsevier, vol. 123(2), pages 315-324, June.
When requesting a correction, please mention this item's handle: RePEc:hhb:aarbls:2004-005. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Helle Vinbaek Stenholt)
If references are entirely missing, you can add them using this form.