IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v225y2013i3p455-471.html
   My bibliography  Save this article

Dynamic journeying under uncertainty

Author

Listed:
  • Häme, Lauri
  • Hakula, Harri

Abstract

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
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221712007734
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2012.10.027?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
    ---><---

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

    References listed on IDEAS

    as
    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. Lam, Terence C. & Small, Kenneth A., 0. "The value of time and reliability: measurement from a value pricing experiment," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 37(2-3), pages 231-251, April.
    3. Y. Y. Fan & R. E. Kalaba & J. E. Moore, 2005. "Arriving on Time," Journal of Optimization Theory and Applications, Springer, vol. 127(3), pages 497-513, December.
    4. 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.
    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. Horn, Mark E. T., 2003. "An extended model and procedural framework for planning multi-modal passenger journeys," Transportation Research Part B: Methodological, Elsevier, vol. 37(7), pages 641-660, August.
    7. Dimitris J. Bertsimas & Patrick Jaillet & Amedeo R. Odoni, 1990. "A Priori Optimization," Operations Research, INFORMS, vol. 38(6), pages 1019-1033, December.
    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. Raymond K. Cheung & B. Muralidharan, 2000. "Dynamic Routing for Priority Shipments in LTL Service Networks," Transportation Science, INFORMS, vol. 34(1), pages 86-98, February.
    11. 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.
    12. Small, Kenneth A., 2001. "The Value of Pricing," University of California Transportation Center, Working Papers qt0rm449sx, University of California Transportation Center.
    13. Elise D. Miller-Hooks & Hani S. Mahmassani, 2000. "Least Expected Time Paths in Stochastic, Time-Varying Transportation Networks," Transportation Science, INFORMS, vol. 34(2), pages 198-215, May.
    14. Fosgerau, Mogens & Karlström, Anders, 2010. "The value of reliability," Transportation Research Part B: Methodological, Elsevier, vol. 44(1), pages 38-49, January.
    15. 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.
    16. 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.
    17. 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.
    18. Astrid S. Kenyon & David P. Morton, 2003. "Stochastic Vehicle Routing with Random Travel Times," Transportation Science, INFORMS, vol. 37(1), pages 69-82, February.
    19. Randolph W. Hall, 1986. "The Fastest Path through a Network with Random Time-Dependent Travel Times," Transportation Science, INFORMS, vol. 20(3), pages 182-188, August.
    20. Edward P. C. Kao, 1978. "A Preference Order Dynamic Program for a Stochastic Traveling Salesman Problem," Operations Research, INFORMS, vol. 26(6), pages 1033-1045, December.
    21. 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.
    22. 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.
    23. 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.
    24. James L. Bander & Chelsea C. White, 2002. "A Heuristic Search Approach for a Nonstationary Stochastic Shortest Path Problem with Terminal Cost," Transportation Science, INFORMS, vol. 36(2), pages 218-230, May.
    25. 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.
    26. 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.
    27. 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

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


    Cited by:

    1. Zweers, Bernard G. & van der Mei, Rob D., 2022. "Minimum costs paths in intermodal transportation networks with stochastic travel times and overbookings," European Journal of Operational Research, Elsevier, vol. 300(1), pages 178-188.
    2. Redmond, Michael & Campbell, Ann Melissa & Ehmke, Jan Fabian, 2022. "Reliability in public transit networks considering backup itineraries," European Journal of Operational Research, Elsevier, vol. 300(3), pages 852-864.
    3. López, David & Lozano, Angélica, 2020. "Shortest hyperpaths in a multimodal hypergraph with real-time information on some transit lines," Transportation Research Part A: Policy and Practice, Elsevier, vol. 137(C), pages 541-559.
    4. Zhang, Yu & Tang, Jiafu, 2018. "Itinerary planning with time budget for risk-averse travelers," European Journal of Operational Research, Elsevier, vol. 267(1), pages 288-303.
    5. Ji, Chenlu & Mandania, Rupal & Liu, Jiyin & Liret, Anne, 2022. "Scheduling on-site service deliveries to minimise the risk of missing appointment times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    6. Roberto Tadei & Guido Perboli & Francesca Perfetti, 2017. "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. 6(1), pages 3-23, March.
    7. Patrick Jaillet & Jin Qi & Melvyn Sim, 2016. "Routing Optimization Under Uncertainty," Operations Research, INFORMS, vol. 64(1), pages 186-200, February.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Azadian, Farshid & Murat, Alper E. & Chinnam, Ratna Babu, 2012. "Dynamic routing of time-sensitive air cargo using real-time information," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 355-372.
    2. 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.
    3. Levering, Nikki & Boon, Marko & Mandjes, Michel & Núñez-Queija, Rudesindo, 2022. "A framework for efficient dynamic routing under stochastically varying conditions," Transportation Research Part B: Methodological, Elsevier, vol. 160(C), pages 97-124.
    4. Zhaoqi Zang & Xiangdong Xu & Kai Qu & Ruiya Chen & Anthony Chen, 2022. "Travel time reliability in transportation networks: A review of methodological developments," Papers 2206.12696, arXiv.org, revised Jul 2022.
    5. Wu, Xing & (Marco) Nie, Yu, 2011. "Modeling heterogeneous risk-taking behavior in route choice: A stochastic dominance approach," Transportation Research Part A: Policy and Practice, Elsevier, vol. 45(9), pages 896-915, November.
    6. Shahabi, Mehrdad & Unnikrishnan, Avinash & Boyles, Stephen D., 2013. "An outer approximation algorithm for the robust shortest path problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 58(C), pages 52-66.
    7. Zweers, Bernard G. & van der Mei, Rob D., 2022. "Minimum costs paths in intermodal transportation networks with stochastic travel times and overbookings," European Journal of Operational Research, Elsevier, vol. 300(1), pages 178-188.
    8. 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.
    9. Tan, Zhijia & Yang, Hai & Guo, Renyong, 2014. "Pareto efficiency of reliability-based traffic equilibria and risk-taking behavior of travelers," Transportation Research Part B: Methodological, Elsevier, vol. 66(C), pages 16-31.
    10. Paul Koster & Hans Koster, 2013. "Analysing Heterogeneity in the Value of Travel Time and Reliability: A Semiparametric Estimation Approach," ERSA conference papers ersa13p1032, European Regional Science Association.
    11. Gao, Song & Chabini, Ismail, 2006. "Optimal routing policy problems in stochastic time-dependent networks," Transportation Research Part B: Methodological, Elsevier, vol. 40(2), pages 93-122, February.
    12. Nie, Yu (Marco) & Wu, Xing & Dillenburg, John F. & Nelson, Peter C., 2012. "Reliable route guidance: A case study from Chicago," Transportation Research Part A: Policy and Practice, Elsevier, vol. 46(2), pages 403-419.
    13. N Shi & R K Cheung & H Xu & K K Lai, 2011. "An adaptive routing strategy for freight transportation networks," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(4), pages 799-805, April.
    14. Wu, Xing, 2015. "Study on mean-standard deviation shortest path problem in stochastic and time-dependent networks: A stochastic dominance based approach," Transportation Research Part B: Methodological, Elsevier, vol. 80(C), pages 275-290.
    15. Bhat, Chandra R. & Sardesai, Rupali, 2006. "The impact of stop-making and travel time reliability on commute mode choice," Transportation Research Part B: Methodological, Elsevier, vol. 40(9), pages 709-730, November.
    16. Wu, Wen-Xiang & Huang, Hai-Jun, 2014. "Finding anonymous tolls to realize target flow pattern in networks with continuously distributed value of time," Transportation Research Part B: Methodological, Elsevier, vol. 65(C), pages 31-46.
    17. Stephane Hess & Andrew Daly & Maria Börjesson, 2020. "A critical appraisal of the use of simple time-money trade-offs for appraisal value of travel time measures," Transportation, Springer, vol. 47(3), pages 1541-1570, June.
    18. Zhaoqi Zang & Richard Batley & Xiangdong Xu & David Z. W. Wang, 2022. "On the value of distribution tail in the valuation of travel time variability," Papers 2207.06293, arXiv.org, revised Dec 2023.
    19. Huang, He & Gao, Song, 2012. "Optimal paths in dynamic networks with dependent random link travel times," Transportation Research Part B: Methodological, Elsevier, vol. 46(5), pages 579-598.
    20. Fosgerau, Mogens & Fukuda, Daisuke, 2010. "Valuing travel time variability: Characteristics of the travel time distribution on an urban road," MPRA Paper 24330, University Library of Munich, Germany.

    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:eee:ejores:v:225:y:2013:i:3:p:455-471. 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.

    If CitEc recognized a bibliographic 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.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.