Dynamic Shortest Paths in Acyclic Networks with Markovian Arc Costs

Harilaos N. Psaraftis and John N. Tsitsiklis
Additional contact information
Harilaos N. Psaraftis: National Technical University of Athens, Athens, Greece
John N. Tsitsiklis: Massachusetts Institute of Technology, Cambridge, Massachusetts

Operations Research, 1993, vol. 41, issue 1, 91-101

Abstract: We examine shortest path problems in acyclic networks in which arc costs are known functions of certain environment variables at network nodes. Each of these variables evolves according to an independent Markov process. The vehicle can wait at a node (at a cost) in anticipation of more favorable arc costs. We first develop two recursive procedures for the individual arc case, one based on successive approximations, and the other on policy iteration. We also solve the same problem via parametric linear programming. We show that the optimal policy essentially classifies the state of the environment variable at a node into two categories: green states for which the optimal action is to immediately traverse the arc, and red states for which the optimal action is to wait. We then extend these concepts for the entire network by developing a dynamic programming procedure that solves the corresponding problem. The complexity of this method is shown to be O ( n 2 K + nK 3 ), where n is the number of network nodes and K is the number of Markov states at each node. We present examples and discuss possible research extensions.

Keywords: networks/graphs; distance algorithms: Markovian cost structure; networks/graphs; stochastic: dynamic shortest paths; transportation; models; network: dynamic and stochastic problems (search for similar items in EconPapers)
Date: 1993
References: Add references at CitEc
Citations: View citations in EconPapers (26)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.41.1.91 (application/pdf)

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:inm:oropre:v:41:y:1993:i:1:p:91-101

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().