IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v32y1998i1p65-73.html
   My bibliography  Save this article

Shortest Path Algorithms: An Evaluation Using Real Road Networks

Author

Listed:
  • F. Benjamin Zhan

    (Department of Geography and Planning, Southwest Texas State University, San Marcos, Texas 78666)

  • Charles E. Noon

    (Management Science Program, The University of Tennessee, Knoxville, Tennessee 37996)

Abstract

The classic problem of finding the shortest path over a network has been the target of many research efforts over the years. These research efforts have resulted in a number of different algorithms and a considerable amount of empirical findings with respect to performance. Unfortunately, prior research does not provide a clear direction for choosing an algorithm when one faces the problem of computing shortest paths on real road networks. Most of the computational testing on shortest path algorithms has been based on randomly generated networks, which may not have the characteristics of real road networks. In this paper, we provide an objective evaluation of 15 shortest path algorithms using a variety of real road networks. Based on the evaluation, a set of recommended algorithms for computing shortest paths on real road networks is identified. This evaluation should be particularly useful to researchers and practitioners in operations research, management science, transportation, and Geographic Information Systems.

Suggested Citation

  • F. Benjamin Zhan & Charles E. Noon, 1998. "Shortest Path Algorithms: An Evaluation Using Real Road Networks," Transportation Science, INFORMS, vol. 32(1), pages 65-73, February.
    • Handle: RePEc:inm:ortrsc:v:32:y:1998:i:1:p:65-73
    DOI: 10.1287/trsc.32.1.65
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.32.1.65
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.32.1.65?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
    ---><---

    Citations

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


    Cited by:

    1. Song, Ruidian & Zhao, Lei & Van Woensel, Tom & Fransoo, Jan C., 2019. "Coordinated delivery in urban retail," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 126(C), pages 122-148.
    2. Duff, Thomas J. & Chong, Derek M. & Tolhurst, Kevin G., 2015. "Using discrete event simulation cellular automata models to determine multi-mode travel times and routes of terrestrial suppression resources to wildland fires," European Journal of Operational Research, Elsevier, vol. 241(3), pages 763-770.
    3. Demirel, Hande & Kompil, Mert & Nemry, Françoise, 2015. "A framework to analyze the vulnerability of European road networks due to Sea-Level Rise (SLR) and sea storm surges," Transportation Research Part A: Policy and Practice, Elsevier, vol. 81(C), pages 62-76.
    4. Elías Escobar-Gómez & J.L. Camas-Anzueto & Sabino Velázquez-Trujillo & Héctor Hernández-de-León & Rubén Grajales-Coutiño & Eduardo Chandomí-Castellanos & Héctor Guerra-Crespo, 2019. "A Linear Programming Model with Fuzzy Arc for Route Optimization in the Urban Road Network," Sustainability, MDPI, vol. 11(23), pages 1-18, November.
    5. Jenelius, Erik & Petersen, Tom & Mattsson, Lars-Göran, 2006. "Importance and exposure in road network vulnerability analysis," Transportation Research Part A: Policy and Practice, Elsevier, vol. 40(7), pages 537-560, August.
    6. Chen, Chialin & Achtari, Guyves & Majkut, Kevin & Sheu, Jiuh-Biing, 2017. "Balancing equity and cost in rural transportation management with multi-objective utility analysis and data envelopment analysis: A case of Quinte West," Transportation Research Part A: Policy and Practice, Elsevier, vol. 95(C), pages 148-165.
    7. Changyong Zhang, 2017. "An origin-based model for unique shortest path routing," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(8), pages 935-951, August.
    8. Kenneth Carling & Mengjie Han & Johan Håkansson, 2012. "Does Euclidean distance work well when the p-median model is applied in rural areas?," Annals of Operations Research, Springer, vol. 201(1), pages 83-97, December.
    9. Mansuy, Nicolas & Thiffault, Evelyne & Lemieux, Sébastien & Manka, Francis & Paré, David & Lebel, Luc, 2015. "Sustainable biomass supply chains from salvage logging of fire-killed stands: A case study for wood pellet production in eastern Canada," Applied Energy, Elsevier, vol. 154(C), pages 62-73.
    10. Abdullah Alshehri & Mahmoud Owais & Jayadev Gyani & Mishal H. Aljarbou & Saleh Alsulamy, 2023. "Residual Neural Networks for Origin–Destination Trip Matrix Estimation from Traffic Sensor Information," Sustainability, MDPI, vol. 15(13), pages 1-21, June.
    11. Poss, Michael, 2014. "Robust combinatorial optimization with variable cost uncertainty," European Journal of Operational Research, Elsevier, vol. 237(3), pages 836-845.
    12. Jotshi, Arun & Gong, Qiang & Batta, Rajan, 2009. "Dispatching and routing of emergency vehicles in disaster mitigation using data fusion," Socio-Economic Planning Sciences, Elsevier, vol. 43(1), pages 1-24, March.
    13. Carling, Kenneth & Han, Mengjie & Håkansson, Johan & Meng, Xiangli & Rudholm, Niklas, 2014. "Measuring CO2 Emissions Induced by Online and Brick-and-mortar Retailing," HUI Working Papers 106, HUI Research.
    14. Eliécer Gutiérrez & Andrés Medaglia, 2008. "Labeling algorithm for the shortest path problem with turn prohibitions with application to large-scale road networks," Annals of Operations Research, Springer, vol. 157(1), pages 169-182, January.
    15. Slavomir Vukmirovic & Zvonko Capko & Antonia Dzido, 2023. "Transport Network Optimization Based On Finding Optimal And Suboptimal Solutions On The Example Of The Rijeka Urban Agglomeration," Business Logistics in Modern Management, Josip Juraj Strossmayer University of Osijek, Faculty of Economics, Croatia, vol. 23, pages 297-316.
    16. Preethi Issac & Ann Melissa Campbell, 2017. "Shortest path problem with arc failure scenarios," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(2), pages 139-163, June.
    17. Hughes, Michael S. & Lunday, Brian J. & Weir, Jeffrey D. & Hopkinson, Kenneth M., 2021. "The multiple shortest path problem with path deconfliction," European Journal of Operational Research, Elsevier, vol. 292(3), pages 818-829.
    18. A. Parsakhoo & M. Mostafa, 2015. "Road network analysis for timber transportation from a harvesting site to mills (Case study: Gorgan county - Iran)," Journal of Forest Science, Czech Academy of Agricultural Sciences, vol. 61(12), pages 520-525.
    19. Declan Mungovan & Enda Howley & Jim Duggan, 2011. "The influence of random interactions and decision heuristics on norm evolution in social networks," Computational and Mathematical Organization Theory, Springer, vol. 17(2), pages 152-178, May.
    20. Almobaideen, Wesam & Krayshan, Rand & Allan, Mamoon & Saadeh, Maha, 2017. "Internet of Things: Geographical Routing based on healthcare centers vicinity for mobile smart tourism destination," Technological Forecasting and Social Change, Elsevier, vol. 123(C), pages 342-350.
    21. Mohsen Alawi & Dongzhu Chu & Seba Hammad, 2023. "Resilience of Public Open Spaces to Earthquakes: A Case Study of Chongqing, China," Sustainability, MDPI, vol. 15(2), pages 1-20, January.
    22. Xin Feng & Shaohua Wang & Alan T Murray & Yuanpei Cao & Song Gao, 2021. "Multi-objective trajectory optimization in planning for sequential activities across space and through time," Environment and Planning B, , vol. 48(4), pages 945-963, May.
    23. repec:jss:jstsof:40:i10 is not listed on IDEAS
    24. Hsueh-Sheng Chang & Chin-Hsien Liao, 2015. "Planning emergency shelter locations based on evacuation behavior," Natural Hazards: Journal of the International Society for the Prevention and Mitigation of Natural Hazards, Springer;International Society for the Prevention and Mitigation of Natural Hazards, vol. 76(3), pages 1551-1571, April.
    25. A. Parsakhoo & M. Jajouzadeh, 2016. "Determining an optimal path for forest road construction using Dijkstra's algorithm," Journal of Forest Science, Czech Academy of Agricultural Sciences, vol. 62(6), pages 264-268.

    More about this item

    Statistics

    Access and download statistics

    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:inm:ortrsc:v:32:y:1998:i:1:p:65-73. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.