IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v41y1993i1p91-101.html
   My bibliography  Save this article

Dynamic Shortest Paths in Acyclic Networks with Markovian Arc Costs

Author

Listed:
  • Harilaos N. Psaraftis

    (National Technical University of Athens, Athens, Greece)

  • John N. Tsitsiklis

    (Massachusetts Institute of Technology, Cambridge, Massachusetts)

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.

Suggested Citation

  • Harilaos N. Psaraftis & John N. Tsitsiklis, 1993. "Dynamic Shortest Paths in Acyclic Networks with Markovian Arc Costs," Operations Research, INFORMS, vol. 41(1), pages 91-101, February.
    • Handle: RePEc:inm:oropre:v:41:y:1993:i:1:p:91-101
    DOI: 10.1287/opre.41.1.91
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.41.1.91
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.41.1.91?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:41:y:1993:i:1:p:91-101. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.