Reliable a Priori Shortest Path Problem with Limited Spatial and Temporal Dependencies

Yu Marco Nie and Xing Wu
Additional contact information
Yu Marco Nie: Northwestern University
Xing Wu: Northwestern University

Chapter Chapter 9 in Transportation and Traffic Theory 2009: Golden Jubilee, 2009, pp 169-195 from Springer

Abstract: Abstract This paper studies the problem of finding most reliable a priori shortest paths (RASP) in a stochastic and time-dependent network. Correlations are modeled by assuming the probability density functions of link traversal times to be conditional on both the time of day and link states. Such correlations are spatially limited by the Markovian property of the link states, which may be such defined to reflect congestion levels or the intensity of random disruptions. We formulate the RASP problem with the above correlation structure as a general dynamic programming problem, and show that the optimal solution is a set of non-dominated paths under the first-order stochastic dominance. Conditions are proposed to regulate the transition probabilities of link states such that Bellman’s principle of optimality can be utilized. We prove that a non-dominated path should contain no cycles if random link travel times are consistent with the stochastic first-in-first-out principle. The RASP problem is solved using a non-deterministic polynomial label correcting algorithm. Approximation algorithms with polynomial complexity may be achieved when further assumptions are made to the correlation structure and to the applicability of dynamic programming. Numerical results are provided.

Keywords: Pareto Frontier; Short Path Problem; Link State; Outgoing Link; Traversal Time (search for similar items in EconPapers)
Date: 2009
References: Add references at CitEc
Citations: View citations in EconPapers (7)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spr:sprchp:978-1-4419-0820-9_9

Ordering information: This item can be ordered from
http://www.springer.com/9781441908209

DOI: 10.1007/978-1-4419-0820-9_9

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().