IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v127y2005i3d10.1007_s10957-005-7498-5.html
   My bibliography  Save this article

Arriving on Time

Author

Listed:
  • Y. Y. Fan

    (University of California)

  • R. E. Kalaba

    (University of Southern California)

  • J. E. Moore

    (University of Southern California)

Abstract

This research proposes a procedure for identifying dynamic routing policies in stochastic transportation networks. It addresses the problem of maximizing the probability of arriving on time. Given a current location (node), the goal is to identify the next node to visit so that the probability of arriving at the destination by time t or sooner is maximized, given the probability density functions for the link travel times. The Bellman principle of optimality is applied to formulate the mathematical model of this problem. The unknown functions describing the maximum probability of arriving on time are estimated accurately for a few sample networks by using the Picard method of successive approximations. The maximum probabilities can be evaluated without enumerating the network paths. The Laplace transform and its numerical inversion are introduced to reduce the computational cost of evaluating the convolution integrals that result from the successive approximation procedure.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:joptap:v:127:y:2005:i:3:d:10.1007_s10957-005-7498-5
    DOI: 10.1007/s10957-005-7498-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-005-7498-5
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10957-005-7498-5?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.

    Citations

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


    Cited by:

    1. Manseur, Farida & Farhi, Nadir & Nguyen Van Phu, Cyril & Haj-Salem, Habib & Lebacque, Jean-Patrick, 2020. "Robust routing, its price, and the tradeoff between routing robustness and travel time reliability in road networks," European Journal of Operational Research, Elsevier, vol. 285(1), pages 159-171.
    2. Matthias Ruß & Gunther Gust & Dirk Neumann, 2021. "The Constrained Reliable Shortest Path Problem in Stochastic Time-Dependent Networks," Operations Research, INFORMS, vol. 69(3), pages 709-726, May.
    3. Xing, Tao & Zhou, Xuesong, 2011. "Finding the most reliable path with and without link travel time correlation: A Lagrangian substitution based approach," Transportation Research Part B: Methodological, Elsevier, vol. 45(10), pages 1660-1679.
    4. Zhang, Yufeng & Khani, Alireza, 2019. "An algorithm for reliable shortest path problem with travel time correlations," Transportation Research Part B: Methodological, Elsevier, vol. 121(C), pages 92-113.
    5. 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.
    6. Li, Wenjie & Yang, Lixing & Wang, Li & Zhou, Xuesong & Liu, Ronghui & Gao, Ziyou, 2017. "Eco-reliable path finding in time-variant and stochastic networks," Energy, Elsevier, vol. 121(C), pages 372-387.
    7. 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.
    8. Yang, Lixing & Zhou, Xuesong, 2017. "Optimizing on-time arrival probability and percentile travel time for elementary path finding in time-dependent transportation networks: Linear mixed integer programming reformulations," Transportation Research Part B: Methodological, Elsevier, vol. 96(C), pages 68-91.
    9. Huang, Kuancheng & Wu, Kun-Feng & Ardiansyah, Muhammad Nashir, 2019. "A stochastic dairy transportation problem considering collection and delivery phases," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 129(C), pages 325-338.
    10. 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.
    11. Häme, Lauri & Hakula, Harri, 2013. "Dynamic journeying under uncertainty," European Journal of Operational Research, Elsevier, vol. 225(3), pages 455-471.
    12. Leilei Zhang & Tito Homem-de-Mello, 2017. "An Optimal Path Model for the Risk-Averse Traveler," Transportation Science, INFORMS, vol. 51(2), pages 518-535, May.
    13. Khani, Alireza & Boyles, Stephen D., 2015. "An exact algorithm for the mean–standard deviation shortest path problem," Transportation Research Part B: Methodological, Elsevier, vol. 81(P1), pages 252-266.
    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. Liu, Yang & Blandin, Sebastien & Samaranayake, Samitha, 2019. "Stochastic on-time arrival problem in transit networks," Transportation Research Part B: Methodological, Elsevier, vol. 119(C), pages 122-138.
    16. Correa, José & Hoeksma, Ruben & Schröder, Marc, 2019. "Network congestion games are robust to variable demand," Transportation Research Part B: Methodological, Elsevier, vol. 119(C), pages 69-78.
    17. Arthur Flajolet & Sébastien Blandin & Patrick Jaillet, 2018. "Robust Adaptive Routing Under Uncertainty," Operations Research, INFORMS, vol. 66(1), pages 210-229, January.
    18. 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.
    19. Qi, Jin & Sim, Melvyn & Sun, Defeng & Yuan, Xiaoming, 2016. "Preferences for travel time under risk and ambiguity: Implications in path selection and network equilibrium," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 264-284.
    20. Verbeeck, C. & Vansteenwegen, P. & Aghezzaf, E.-H., 2016. "Solving the stochastic time-dependent orienteering problem with time windows," European Journal of Operational Research, Elsevier, vol. 255(3), pages 699-718.
    21. 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.

    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:spr:joptap:v:127:y:2005:i:3:d:10.1007_s10957-005-7498-5. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.