Abstract
Finding effective routes is critical to support the decision-making of first responders to save lives in emergency and accident situations. Effective routing planning requires accurate traffic information including railroad blockage that could lead to significant delays. This study aims to improve the decision-making efficiency of emergency responding by integrating railroad crossing blockage and dynamic traffic information into routing planning process. Specifically, we propose a data-driven algorithm that considers real-time train blockage time windows in the route planning process. Through a series of first responder vehicle dispatching scenarios in Columbia, South Carolina, we demonstrate that the framework can assist first responders in finding the best route with the minimum response time in an emergency. Results from the scenarios show that the method can save as much as 61.6% of response time compared with the time calculated based on existing practices. This study demonstrates the benefit and necessity of integrating train operation information into emergency responding vehicle route planning to save lives.
Get full access to this article
View all available purchase options and get full access to this article.
Data Availability Statement
Some or all data, models, or code that support the findings of this study are available from the corresponding author upon reasonable request.
Acknowledgments
This research is partially funded by the Federal Railroad Administration (FRA), Contract no. 693JJ621C000015. Francesco Bedini, Dr. Shala Blue, Michael Jones, and Dr. Starr Kidda from FRA provided important guidance and insight. The City of Columbia, especially the Columbia Fire Department, Department of Transportation, and 911 Dispatching Center, and CSX provided tremendous help. The opinions expressed in this paper are solely those of the authors and do not represent the opinions of the funding agencies.
References
Arble, E., A. M. Daugherty, and B. B. Arnetz. 2018. “Models of first responder coping: Police officers as a unique population.” Stress Health 34 (5): 612–621. https://doi.org/10.1002/smi.2821.
Awerbuch, B., A. Bar-Noy, and M. Gopal. 1994. “Approximate distributed Bellman-Ford algorithms.” IEEE Trans. Commun. 42 (8): 2515–2517. https://doi.org/10.1109/26.310604.
Bertsekas, D. P. 1993. “A simple and fast label correcting algorithm for shortest paths.” Networks 23 (8): 703–709. https://doi.org/10.1002/net.3230230808.
Brown, A., and B. D. Taylor. 2018. “Bridging the gap between mobility haves and have-nots.” In Three revolutions: Steering automated, shared, and electric vehicles to a better future, by D. Sperling, 131–150. Washington, DC: Island. https://doi.org/10.5822/978-1-61091-906-7_6.
Carrabs, F., C. D’Ambrosio, D. Ferone, P. Festa, and F. Laureana. 2020. “The constrained forward shortest path tour problem: Mathematical modeling and GRASP approximate solutions.” Networks 78 (1): 17–31. https://doi.org/10.1002/net.22010.
Chassein, A., T. Dokka, and M. Goerigk. 2019. “Algorithms and uncertainty sets for data-driven robust shortest path problems.” Eur. J. Oper. Res. 274 (2): 671–686. https://doi.org/10.1016/j.ejor.2018.10.006.
Colton, K. W. 1980. “Police and computer technology: The case of the San Diego computer-aided dispatch system.” Public Prod. Rev. 4 (1): 21–42. https://doi.org/10.2307/3380055.
Dawe, P., and J. Pagotto. 2014. “Analysis of integrating computer-aided dispatch information with the multi-agency situational awareness system.” Accessed May 15, 2023. https://apps.dtic.mil/sti/citations/AD1017599.
Desaulniers, G., O. B. G. Madsen, and S. Ropke. 2014. “The vehicle routing problem with time windows.” Chap. 5 in Vehicle routing MOS-SIAM series on optimization, 119–159. Philadelphia: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611973594.ch5.
Dijkstra, E. W. 1959. “A note on two problems in connexion with graphs.” Numer. Math. 1 (1): 269–271. https://doi.org/10.1007/BF01386390.
Di Puglia Pugliese, L., D. Ferone, P. Festa, and F. Guerriero. 2020. “Shortest path tour problem with time windows.” Eur. J. Oper. Res. 282 (1): 334–344. https://doi.org/10.1016/j.ejor.2019.08.052.
Dreyfus, S. E. 1969. “An appraisal of some shortest-path algorithms.” Oper. Res. 17 (3): 395–412. https://doi.org/10.1287/opre.17.3.395.
El-Sherbeny, N. A. 2014. “The algorithm of the time-dependent shortest path problem with time windows.” Appl. Math. 5 (17): 2764. https://doi.org/10.4236/am.2014.517264.
Ferone, D., P. Festa, and F. Guerriero. 2020. “An efficient exact approach for the constrained shortest path tour problem.” Optim. Methods Software 35 (1): 1–20. https://doi.org/10.1080/10556788.2018.1548015.
Ferone, D., P. Festa, F. Guerriero, and D. Laganà. 2016. “The constrained shortest path tour problem.” Comput. Oper. Res. 74 (Oct): 64–77. https://doi.org/10.1016/j.cor.2016.04.002.
Festa, P. 2009. “The shortest path tour problem: Problem definition, modeling, and optimization.” In Vol. 217 of Proc., INOC, 1–7. New York: Internet Network Operations Center.
FRA (Federal Railroad Administration). 2006. “Impact of blocked highway/rail grade crossings on emergency response services.” Accessed October 31, 2022. https://www.hsdl.org/?view&did=779166#:∼:text=In%20addition%2C%20a%20grade%20crossing,laws%20or%20pedestrians%20to%20trespass.
FRA (Federal Railroad Administration). 2022. “Highway-rail grade crossing and trespassing research.” Accessed December 21, 2022. https://railroads.dot.gov/research-development/program-areas/highway-rail-grade-crossing/highway-rail-grade-crossing-and.
Golden, B. 1976. “Technical note—Shortest-path algorithms: A comparison.” Oper. Res. 24 (6): 1164–1168. https://doi.org/10.1287/opre.24.6.1164.
Güner, A. R., A. Murat, and R. B. Chinnam. 2012. “Dynamic routing under recurrent and non-recurrent congestion using real-time ITS information.” Comput. Oper. Res. 39 (2): 358–373. https://doi.org/10.1016/j.cor.2011.04.012.
Hiermann, G., J. Puchinger, S. Ropke, and R. F. Hartl. 2016. “The electric fleet size and mix vehicle routing problem with time windows and recharging stations.” Eur. J. Oper. Res. 252 (3): 995–1018. https://doi.org/10.1016/j.ejor.2016.01.038.
Hilleary, T. N. 2012. “A radar vehicle detection system for four-quadrant gate warning systems and blocked crossing detection.” Accessed October 31, 2022. https://rosap.ntl.bts.gov/view/dot/26255.
Jafari, M., I. Bakhadyrov, and A. Maher. 2003. “Technological advances in evacuation planning and emergency management: Current state of the art.” Accessed June 22, 2022. https://rosap.ntl.bts.gov/view/dot/18368.
Johnson, D. B. 1973. “A note on Dijkstra’s shortest path algorithm.” J. ACM 20 (3): 385–388. https://doi.org/10.1145/321765.321768.
Karczmarz, A., and J. Łącki. 2019. “Simple label-correcting algorithms for partially dynamic approximate shortest paths in directed graphs.” In Proc., Symp. on Simplicity in Algorithms (SOSA), 106–120. Philadelphia: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611976014.15.
Kergosien, Y., A. Giret, E. Néron, and G. Sauvanet. 2022. “An efficient label-correcting algorithm for the multiobjective shortest path problem.” INFORMS J. Comput. 34 (1): 76–92. https://doi.org/10.1287/ijoc.2021.1081.
Kevany, M. J. 2007. “Improving geospatial information in disaster management through action on lessons learned from major events.” In Geospatial information technology for emergency response. London: CRC Press.
Lawson, G., S. Allen, G. Rose, D. Nguyen, and M. Ng. 2013. “Parallel label-correcting algorithms for large-scale static and dynamic transportation networks on laptop personal computers.” Accessed May 22, 2023. https://trid.trb.org/view/1241328.
Neuvel, J., and S. Zlatanova. 2006. “The void between risk prevention and crisis response.” In Proc., UDMS’06. Stuttgart, Germany: Urban Data Management Society.
Njus, E. 2016. “How long can trains block railroad crossings? (Commuting Q&A).” Accessed November 3, 2016. https://www.oregonlive.com/commuting/2016/11/how_long_can_trains_block_rail.html.
Park, P. Y., W. R. Jung, G. Yeboah, G. Rempel, D. Paulsen, and D. Rumpel. 2016. “First responders’ response area and response time analysis with/without grade crossing monitoring system.” Fire Saf. J. 79 (Jan): 100–110. https://doi.org/10.1016/j.firesaf.2015.11.003.
Poe, M. G. 2018. “Trains blocking roadway creates dangerous situations, first responders say.” Accessed March 8, 2018. https://kutv.com/news/get-gephardt/trains.
Rodriguez, A. 2018. “Energy consumption and routing model for first responder vehicles.” Pegasus Rev. UCF Undergrad. Res. J. 10 (1): 1.
Rozas, H., D. Muñoz-Carpintero, D. Saéz, and M. E. Orchard. 2021. “Solving in real-time the dynamic and stochastic shortest path problem for electric vehicles by a prognostic decision making strategy.” Expert Syst. Appl. 184 (Dec): 115489. https://doi.org/10.1016/j.eswa.2021.115489.
Sancho, N. G. F. 1994. “Shortest path problems with time windows on nodes and arcs.” J. Math. Anal. Appl. 186 (3): 643–648. https://doi.org/10.1006/jmaa.1994.1324.
Saraiva, R. D., and R. Castro de Andrade. 2021. “Constrained shortest path tour problem: Models, valid inequalities, and Lagrangian heuristics.” Int. Tran. Oper. Res. 28 (1): 222–261. https://doi.org/10.1111/itor.12782.
Schambers, A., M. Eavis-O’Quinn, V. Roberge, and M. Tarbouchi. 2018. “Route planning for electric vehicle efficiency using the Bellman-Ford algorithm on an embedded GPU.” In Proc., 2018 4th Int. Conf. on Optimization and Applications (ICOA), 1–6. New York: IEEE. https://doi.org/10.1109/ICOA.2018.8370584.
Sedeño-Noda, A., and C. González-Martín. 2012. “An efficient label setting/correcting shortest path algorithm.” Comput. Optim. Appl. 51 (1): 437–455. https://doi.org/10.1007/s10589-010-9323-9.
Shahabi, M., A. Unnikrishnan, and S. D. Boyles. 2015. “Robust optimization strategy for the shortest path problem under uncertain link travel cost distribution.” Comput.-Aided Civ. Infrastruct. Eng. 30 (6): 433–448. https://doi.org/10.1111/mice.12103.
Shahrah, A. Y., M. A. Al-Mashari, and M. Anwar Hossain. 2017. “Developing and implementing next-generation computer-aided dispatch: Challenges and opportunities.” J. Homeland Secur. Emerg. Manage. 14 (4): 20160080. https://doi.org/10.1515/jhsem-2016-0080.
Shiri, D., and F. S. Salman. 2020. “Online optimization of first-responder routes in disaster response logistics.” IBM J. Res. Dev. 64 (1–2): 1–13. https://doi.org/10.1147/JRD.2019.2947002.
Tofighi, M., A. Asgary, G. Tofighi, B. Podloski, F. Cronemberger, A. Mukherjee, and X. Liu. 2021. “Applying machine learning models to first responder collisions beside roads: Insights from ‘two vehicles hit a parked motor vehicle’ data.” Appl. Sci. 11 (23): 11198. https://doi.org/10.3390/app112311198.
US Census Bureau. 2019. “TIGER/Line Shapefile, 2019, Nation, U.S., rails national shapefile.” Accessed May 24, 2023. https://catalog.data.gov/dataset/tiger-line-shapefile-2019-nation-u-s-rails-national-shapefile.
Wang, Z., and S. Zlatanova. 2016. “Multi-agent based path planning for first responders among moving obstacles.” Comput. Environ. Urban Syst. 56 (Mar): 48–58. https://doi.org/10.1016/j.compenvurbsys.2015.11.001.
Wu, X., Y. Zhang, and Y. Chen. 2023. “A dynamic programming model for joint optimization of electric drayage truck operations and charging stations planning at ports.” IEEE Trans. Intell. Transp. Syst. 24 (11): 11710–11719. https://doi.org/10.1109/TITS.2023.3285668.
Yu, G., and J. Yang. 1998. “On the robust shortest path problem.” Comput. Oper. Res. 25 (6): 457–468. https://doi.org/10.1016/S0305-0548(97)00085-3.
Zhang, Z., X. Liu, and K. Holt. 2020. “Prevention of end-of-track collisions in passenger terminals via positive train control: Benefit-cost analysis and operational impact assessment.” Transp. Res. Rec. 2674 (7): 16–28. https://doi.org/10.1177/0361198120920628.
Zhao, L., and J. Zhao. 2017. “Comparison study of three shortest path algorithm.” In Proc., 2017 Int. Conf. on Computer Technology, Electronics and Communication (ICCTEC), 748–751. New York: IEEE. https://doi.org/10.1109/ICCTEC.2017.00165.
Zhen, L., C. Ma, K. Wang, L. Xiao, and W. Zhang. 2020. “Multi-depot multi-trip vehicle routing problem with time windows and release dates.” Transp. Res. Part E: Logist. Transp. Rev. 135 (Mar): 101866. https://doi.org/10.1016/j.tre.2020.101866.
Zlatanova, S., S. Kamal, and K. Baharin. 2008. “Optimal navigation of first responders using DBMS.” In Proc., 3rd Int. Conf. on Information Systems for Crisis Response and Management 4th Int. Symp. on Geo-Information for Disaster Management, 541–554. Kensington, Australia: UNSW Research.
Information & Authors
Information
Published In
Journal of Transportation Engineering, Part A: Systems
Volume 150 • Issue 4 • April 2024
Copyright
© 2024 American Society of Civil Engineers.
History
Received: Jan 27, 2023
Accepted: Nov 16, 2023
Published online: Jan 31, 2024
Published in print: Apr 1, 2024
Discussion open until: Jun 30, 2024
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.
Cited by
- Yu Qian, Intelligent railroad inspection and monitoring, Frontiers in Built Environment, 10.3389/fbuil.2024.1389092, 10, (2024).