IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v43y2009i1p97-107.html
   My bibliography  Save this article

Hyperstar: A multi-path Astar algorithm for risk averse vehicle navigation

Author

Listed:
  • Bell, Michael G.H.

Abstract

The Astar algorithm, which forms the backbone of vehicle navigation systems, is capable of producing only one path. Given uncertainty about link travel times, there is interest in algorithms that can deliver all the paths that may be optimal, termed collectively a hyperpath, to improve travel time reliability. The actual path taken within the hyperpath will typically be determined by on-trip events, like incidences of congestion leading to delay. In this paper, the Spiess and Florian algorithm for generating hyperpaths in transit networks is adapted to road networks by assuming that drivers follow a risk averse strategy whenever a choice of path arises. To improve the efficiency of the resulting algorithm for vehicle navigation applications, the Astar approach to link selection is incorporated, leading to the Hyperstar algorithm. Proof of the optimality of the algorithm is provided, followed by numerical examples.

Suggested Citation

  • 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.
  • Handle: RePEc:eee:transb:v:43:y:2009:i:1:p:97-107
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191-2615(08)00071-4
    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

    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. van der Zijpp, N.J. & Fiorenzo Catalano, S., 2005. "Path enumeration by finding the constrained K-shortest paths," Transportation Research Part B: Methodological, Elsevier, vol. 39(6), pages 545-563, July.
    3. Azevedo, JoseAugusto & Santos Costa, Maria Emilia O. & Silvestre Madeira, Joaquim Joao E. R. & Vieira Martins, Ernesto Q., 1993. "An algorithm for the ranking of shortest paths," European Journal of Operational Research, Elsevier, vol. 69(1), pages 97-106, August.
    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. Akgun, Vedat & Erkut, Erhan & Batta, Rajan, 2000. "On finding dissimilar paths," European Journal of Operational Research, Elsevier, vol. 121(2), pages 232-246, March.
    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. Oyama, Yuki & Hato, Eiji, 2019. "Prism-based path set restriction for solving Markovian traffic assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 122(C), pages 528-546.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. Liu, Siyuan & Qu, Qiang, 2016. "Dynamic collective routing using crowdsourcing data," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 450-469.

    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. Li, Guoyuan & Chen, Anthony, 2023. "Strategy-based transit stochastic user equilibrium model with capacity and number-of-transfers constraints," European Journal of Operational Research, Elsevier, vol. 305(1), pages 164-183.
    2. Rasmussen, Thomas Kjær & Watling, David Paul & Prato, Carlo Giacomo & Nielsen, Otto Anker, 2015. "Stochastic user equilibrium with equilibrated choice sets: Part II – Solving the restricted SUE for the logit family," Transportation Research Part B: Methodological, Elsevier, vol. 77(C), pages 146-165.
    3. Carlo Prato & Shlomo Bekhor & Cristina Pronello, 2012. "Latent variables and route choice behavior," Transportation, Springer, vol. 39(2), pages 299-319, March.
    4. Bekhor, Shlomo & Prato, Carlo Giacomo, 2009. "Methodological transferability in route choice modeling," Transportation Research Part B: Methodological, Elsevier, vol. 43(4), pages 422-437, May.
    5. 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).
    6. 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.
    7. 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.
    8. 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.
    9. Younes Hamdouch & Siriphong Lawphongpanich, 2010. "Congestion Pricing for Schedule-Based Transit Networks," Transportation Science, INFORMS, vol. 44(3), pages 350-366, August.
    10. 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.
    11. 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.
    12. 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.
    13. Wei Zhu & Wei-li Fan & Amr M. Wahaballa & Jin Wei, 2020. "Calibrating travel time thresholds with cluster analysis and AFC data for passenger reasonable route generation on an urban rail transit network," Transportation, Springer, vol. 47(6), pages 3069-3090, December.
    14. Roberto Cominetti & José Correa, 2001. "Common-Lines and Passenger Assignment in Congested Transit Networks," Transportation Science, INFORMS, vol. 35(3), pages 250-267, August.
    15. Belgacem Bouzaïene-Ayari & Michel Gendreau & Sang Nguyen, 2001. "Modeling Bus Stops in Transit Networks: A Survey and New Formulations," Transportation Science, INFORMS, vol. 35(3), pages 304-321, August.
    16. Bell, Michael G.H. & Liu, Xin & Rioult, Jeremy & Angeloudis, Panagiotis, 2013. "A cost-based maritime container assignment model," Transportation Research Part B: Methodological, Elsevier, vol. 58(C), pages 58-70.
    17. Li, Guoyuan & Chen, Anthony, 2022. "Frequency-based path flow estimator for transit origin-destination trip matrices incorporating automatic passenger count and automatic fare collection data," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 163(C).
    18. Binder, Stefan & Maknoon, Yousef & Bierlaire, Michel, 2017. "Exogenous priority rules for the capacitated passenger assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 105(C), pages 19-42.
    19. Canca, David & Barrena, Eva & De-Los-Santos, Alicia & Andrade-Pineda, José Luis, 2016. "Setting lines frequency and capacity in dense railway rapid transit networks with simultaneous passenger assignment," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 251-267.
    20. Sang Nguyen & Stefano Pallottino & Federico Malucelli, 2001. "A Modeling Framework for Passenger Assignment on a Transport Network with Timetables," Transportation Science, INFORMS, vol. 35(3), pages 238-249, 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:transb:v:43:y:2009:i:1:p:97-107. 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/548/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.