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, 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)
Pages: 29 pages
Date: 2004-11-18
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.hha.dk/afl/wp/log/L_2004_05.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 500 Can't connect to www.hha.dk:80 (No such host is known. )

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

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hhb:aarbls:2004-005

Access Statistics for this paper

More papers in CORAL Working Papers from University of Aarhus, Aarhus School of Business, Department of Business Studies The Aarhus School of Business, Fuglesangs Allé 4, DK-8210 Aarhus V, Denmark. Contact information at EDIRC.
Bibliographic data for series maintained by Helle Vinbaek Stenholt (hes@asb.dk this e-mail address is bad, please contact repec@repec.org).