IDEAS home Printed from
   My bibliography  Save this article

Dynamic journeying under uncertainty


  • Häme, Lauri
  • Hakula, Harri


We introduce a journey planning problem in multi-modal transportation networks under uncertainty. The goal is to find a journey, possibly involving transfers between different transport services, from a given origin to a given destination within a specified time horizon. Due to uncertainty in travel times, the arrival times of transport services at public transport stops are modeled as random variables. If a transfer between two services is rendered unsuccessful, the commuter has to reconsider the remaining path to the destination. The problem is modeled as a Markov decision process in which states are defined as paths in the transport network. The main contribution is a backward induction method that generates an optimal policy for traversing the public transport network in terms of maximizing the probability of reaching the destination in time. By assuming history independence and independence of successful transfers between services we obtain approximate methods for the same problem. Analysis and numerical experiments suggest that while solving the path dependent model requires the enumeration of all paths from the origin to the destination, the proposed approximations may be useful for practical purposes due to their computational simplicity. In addition to on-time arrival probability, we show how travel and overdue costs can be taken into account, making the model applicable to freight transportation problems.

Suggested Citation

  • Häme, Lauri & Hakula, Harri, 2013. "Dynamic journeying under uncertainty," European Journal of Operational Research, Elsevier, vol. 225(3), pages 455-471.
  • Handle: RePEc:eee:ejores:v:225:y:2013:i:3:p:455-471
    DOI: 10.1016/j.ejor.2012.10.027

    Download full text from publisher

    File URL:
    Download Restriction: Full text for ScienceDirect subscribers only

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    1. Thomas, Barrett W. & White III, Chelsea C., 2007. "The dynamic shortest path problem with anticipation," European Journal of Operational Research, Elsevier, vol. 176(2), pages 836-854, January.
    2. Fosgerau, Mogens & Karlström, Anders, 2010. "The value of reliability," Transportation Research Part B: Methodological, Elsevier, vol. 44(1), pages 38-49, January.
    3. Brownstone, David & Small, Kenneth A., 2005. "Valuing time and reliability: assessing the evidence from road pricing demonstrations," Transportation Research Part A: Policy and Practice, Elsevier, vol. 39(4), pages 279-293, May.
    4. Kenneth A. Small & Clifford Winston & Jia Yan, 2005. "Uncovering the Distribution of Motorists' Preferences for Travel Time and Reliability," Econometrica, Econometric Society, vol. 73(4), pages 1367-1382, July.
    5. Androutsopoulos, Konstantinos N. & Zografos, Konstantinos G., 2009. "Solving the multi-criteria time-dependent routing and scheduling problem in a multimodal fixed scheduled network," European Journal of Operational Research, Elsevier, vol. 192(1), pages 18-28, January.
    6. Ziliaskopoulos, Athanasios & Wardell, Whitney, 2000. "An intermodal optimum path algorithm for multimodal networks with dynamic arc travel times and switching delays," European Journal of Operational Research, Elsevier, vol. 125(3), pages 486-502, September.
    7. Murthy, Ishwar & Sarkar, Sumit, 1997. "Exact algorithms for the stochastic shortest path problem with a decreasing deadline utility function," European Journal of Operational Research, Elsevier, vol. 103(1), pages 209-229, November.
    8. Fu, Liping & Rilett, L. R., 1998. "Expected shortest paths in dynamic and stochastic traffic networks," Transportation Research Part B: Methodological, Elsevier, vol. 32(7), pages 499-516, September.
    9. Azaron, Amir & Kianfar, Farhad, 2003. "Dynamic shortest path in stochastic dynamic networks: Ship routing problem," European Journal of Operational Research, Elsevier, vol. 144(1), pages 138-156, January.
    10. Davies, Cedric & Lingras, Pawan, 2003. "Genetic algorithms for rerouting shortest paths in dynamic and stochastic networks," European Journal of Operational Research, Elsevier, vol. 144(1), pages 27-38, January.
    11. Modesti, Paola & Sciomachen, Anna, 1998. "A utility measure for finding multiobjective shortest paths in urban multimodal transportation networks," European Journal of Operational Research, Elsevier, vol. 111(3), pages 495-508, December.
    12. Wong, S. C. & Tong, C. O., 1998. "Estimation of time-dependent origin-destination matrices for transit networks," Transportation Research Part B: Methodological, Elsevier, vol. 32(1), pages 35-48, January.
    13. Chiang, Yu-Sheng & O. Roberts, Paul, 1980. "A note on transit time and reliability for regular-route trucking," Transportation Research Part B: Methodological, Elsevier, vol. 14(1-2), pages 59-65.
    14. Jonathan F. Bard & James E. Bennett, 1991. "Arc Reduction and Path Preference in Stochastic Acyclic Networks," Management Science, INFORMS, vol. 37(2), pages 198-215, February.
    15. Nie, Yu (Marco) & Wu, Xing, 2009. "Shortest path problem considering on-time arrival probability," Transportation Research Part B: Methodological, Elsevier, vol. 43(6), pages 597-613, July.
    Full references (including those not matched with items on IDEAS)


    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.

    Cited by:

    1. repec:spr:eurjtl:v:6:y:2017:i:1:d:10.1007_s13676-014-0056-2 is not listed on IDEAS
    2. Roberto Tadei & Guido Perboli & Francesca Perfetti, 0. "The multi-path Traveling Salesman Problem with stochastic travel costs," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 0, pages 1-21.


    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:eee:ejores:v:225:y:2013:i:3:p:455-471. 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: (Dana Niculescu). General contact details of provider: .

    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.

    If CitEc recognized a reference but did not link an item in RePEc to it, you can help with 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.

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.