IDEAS home Printed from https://ideas.repec.org/a/eee/transa/v46y2012i5p790-800.html
   My bibliography  Save this article

Time-dependent Hyperstar algorithm for robust vehicle navigation

Author

Listed:
  • Bell, Michael G.H.
  • Trozzi, Valentina
  • Hosseinloo, Solmaz Haji
  • Gentile, Guido
  • Fonzone, Achille

Abstract

The vehicle navigation problem studied in Bell (2009) is revisited and a time-dependent reverse Hyperstar algorithm is presented. This minimises the expected time of arrival at the destination, and all intermediate nodes, where expectation is based on a pessimistic (or risk-averse) view of unknown link delays. This may also be regarded as a hyperpath version of the Chabini and Lan (2002) algorithm, which itself is a time-dependent A* algorithm. Links are assigned undelayed travel times and maximum delays, both of which are potentially functions of the time of arrival at the respective link. Probabilities for link use are sought that minimise the driver’s maximum exposure to delay on the approach to each node, leading to the determination of a pessimistic expected time of arrival at the destination and all intermediate nodes. Since the context considered is vehicle navigation, the probability of link use measures link attractiveness, so a link with a zero probability of use is unattractive while a link with a probability of use equal to one will have no attractive alternatives. A solution algorithm is presented and proven to solve the problem provided the node potentials are feasible and a FIFO condition applies to undelayed link travel times. The paper concludes with a numerical example.

Suggested Citation

  • Bell, Michael G.H. & Trozzi, Valentina & Hosseinloo, Solmaz Haji & Gentile, Guido & Fonzone, Achille, 2012. "Time-dependent Hyperstar algorithm for robust vehicle navigation," Transportation Research Part A: Policy and Practice, Elsevier, vol. 46(5), pages 790-800.
    • Handle: RePEc:eee:transa:v:46:y:2012:i:5:p:790-800
    DOI: 10.1016/j.tra.2012.02.002
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0965856412000201
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tra.2012.02.002?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. Spiess, Heinz & Florian, Michael, 1989. "Optimal strategies: A new assignment model for transit networks," Transportation Research Part B: Methodological, Elsevier, vol. 23(2), pages 83-102, April.
    2. Jan-Dirk Schmöcker & Michael G.H. Bell & Fumitaka Kurauchi & Hiroshi Shimamoto, 2009. "A Game Theoretic Approach to the Determination of Hyperpaths in Transportation Networks," Springer Books, in: William H. K. Lam & S. C. Wong & Hong K. Lo (ed.), Transportation and Traffic Theory 2009: Golden Jubilee, chapter 0, pages 1-18, Springer.
    3. Pretolani, Daniele, 2000. "A directed hypergraph model for random time dependent shortest paths," European Journal of Operational Research, Elsevier, vol. 123(2), pages 315-324, June.
    4. Nguyen, S. & Pallottino, S., 1988. "Equilibrium traffic assignment for large scale transit networks," European Journal of Operational Research, Elsevier, vol. 37(2), pages 176-186, November.
    5. 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.
    6. Bell, Michael G.H., 2009. "Hyperstar: A multi-path Astar algorithm for risk averse vehicle navigation," Transportation Research Part B: Methodological, Elsevier, vol. 43(1), pages 97-107, January.
    7. Sung, Kiseok & Bell, Michael G. H. & Seong, Myeongki & Park, Soondal, 2000. "Shortest paths in a network with time-dependent flow speeds," European Journal of Operational Research, Elsevier, vol. 121(1), pages 32-39, February.
    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. Wu, Jiaming & Kulcsár, Balázs & Ahn, Soyoung & Qu, Xiaobo, 2020. "Emergency vehicle lane pre-clearing: From microscopic cooperation to routing decision making," Transportation Research Part B: Methodological, Elsevier, vol. 141(C), pages 223-239.
    2. Maadi, Saeed & Schmöcker, Jan-Dirk, 2017. "Optimal hyperpaths with non-additive link costs," Transportation Research Part B: Methodological, Elsevier, vol. 105(C), pages 235-248.
    3. Li, Qianfei & (Will) Chen, Peng & (Marco) Nie, Yu, 2015. "Finding optimal hyperpaths in large transit networks with realistic headway distributions," European Journal of Operational Research, Elsevier, vol. 240(1), pages 98-108.

    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. Tarun Rambha & Stephen D. Boyles & S. Travis Waller, 2016. "Adaptive Transit Routing in Stochastic Time-Dependent Networks," Transportation Science, INFORMS, vol. 50(3), pages 1043-1059, August.
    2. Li, Qianfei & (Will) Chen, Peng & (Marco) Nie, Yu, 2015. "Finding optimal hyperpaths in large transit networks with realistic headway distributions," European Journal of Operational Research, Elsevier, vol. 240(1), pages 98-108.
    3. Miller-Hooks, Elise & Mahmassani, Hani, 2003. "Path comparisons for a priori and time-adaptive decisions in stochastic, time-varying networks," European Journal of Operational Research, Elsevier, vol. 146(1), pages 67-82, April.
    4. Ouassim Manout & Patrick Bonnel & François Pacull, 2020. "The impact of centroid connectors on transit assignment outcomes," Public Transport, Springer, vol. 12(3), pages 611-629, October.
    5. Feng, Tao & Lusby, Richard M. & Zhang, Yongxiang & Peng, Qiyuan, 2024. "Integrating train service route design with passenger flow allocation for an urban rail transit line," European Journal of Operational Research, Elsevier, vol. 313(1), pages 146-170.
    6. Wen, Liang & Çatay, Bülent & Eglese, Richard, 2014. "Finding a minimum cost path between a pair of nodes in a time-varying road network with a congestion charge," European Journal of Operational Research, Elsevier, vol. 236(3), pages 915-923.
    7. Maadi, Saeed & Schmöcker, Jan-Dirk, 2017. "Optimal hyperpaths with non-additive link costs," Transportation Research Part B: Methodological, Elsevier, vol. 105(C), pages 235-248.
    8. Pramesh Kumar & Alireza Khani, 2021. "Adaptive Park-and-ride Choice on Time-dependent Stochastic Multimodal Transportation Network," Networks and Spatial Economics, Springer, vol. 21(4), pages 771-800, December.
    9. Saeed Maadi & Jan-Dirk Schmöcker, 2020. "Route choice effects of changes from a zonal to a distance-based fare structure in a regional public transport network," Public Transport, Springer, vol. 12(3), pages 535-555, October.
    10. Cats, Oded & Koutsopoulos, Haris N. & Burghout, Wilco & Toledo, Tomer, 2013. "Effect of real-time transit information on dynamic path choice of passengers," Working papers in Transport Economics 2013:28, CTS - Centre for Transport Studies Stockholm (KTH and VTI).
    11. Valentina Trozzi & Guido Gentile & Ioannis Kaparias & Michael Bell, 2015. "Effects of Countdown Displays in Public Transport Route Choice Under Severe Overcrowding," Networks and Spatial Economics, Springer, vol. 15(3), pages 823-842, September.
    12. Xu, Zhandong & Xie, Jun & Liu, Xiaobo & Nie, Yu (Marco), 2020. "Hyperpath-based algorithms for the transit equilibrium assignment problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 143(C).
    13. Ding Luo & Oded Cats & Hans Lint, 2020. "Can passenger flow distribution be estimated solely based on network properties in public transport systems?," Transportation, Springer, vol. 47(6), pages 2757-2776, December.
    14. Wu, Di & Yin, Yafeng & Lawphongpanich, Siriphong, 2011. "Pareto-improving congestion pricing on multimodal transportation networks," European Journal of Operational Research, Elsevier, vol. 210(3), pages 660-669, May.
    15. Codina, Esteve & Rosell, Francisca, 2017. "A heuristic method for a congested capacitated transit assignment model with strategies," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 293-320.
    16. Younes Hamdouch & Siriphong Lawphongpanich, 2010. "Congestion Pricing for Schedule-Based Transit Networks," Transportation Science, INFORMS, vol. 44(3), pages 350-366, August.
    17. Hamdouch, Younes & Lawphongpanich, Siriphong, 2008. "Schedule-based transit assignment model with travel strategies and capacity constraints," Transportation Research Part B: Methodological, Elsevier, vol. 42(7-8), pages 663-684, August.
    18. Nair, Rahul & Miller-Hooks, Elise, 2014. "Equilibrium network design of shared-vehicle systems," European Journal of Operational Research, Elsevier, vol. 235(1), pages 47-61.
    19. Nielsen, Lars Relund & Andersen, Kim Allan & Pretolani, Daniele, 2006. "Bicriterion a priori route choice in stochastic time-dependent networks," CORAL Working Papers L-2006-10, University of Aarhus, Aarhus School of Business, Department of Business Studies.
    20. Roberto Cominetti & José Correa, 2001. "Common-Lines and Passenger Assignment in Congested Transit Networks," Transportation Science, INFORMS, vol. 35(3), pages 250-267, August.

    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:transa:v:46:y:2012:i:5:p:790-800. 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/wps/find/journaldescription.cws_home/547/description#description .

    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.