On the shortest path calculation time in the large-scale dynamic post-disaster environment

Document Type : Original Article

Authors

Department of Industrial Engineering, Eastern Mediterranean University, Famagusta, Turkey

Abstract

There are many metropolitan cities where serious disasters are expected. The disaster, especially if it is an earthquake, damages the roads structure. Thus, the shortest path between two points can be changed. Emergency vehicles, including ambulance, fire-engine, police car, and technical aid, must get the temporary shortest path in real time to work effectively. The shortest path algorithm available in MATLAB, Dijkstra, is tested on two metropolitan cities of San Francisco and Tehran. The road systems of both cities are represented by high number of nodes and connecting arcs. The conclusion is that the algorithm is suitable for finding shortest path for emergency vehicles. However, it is too slow for being a subroutine of a solver for vehicle routing problem.

Keywords

References

B. Vizvári, (2017). On the Economic Aspects of the Design of a Relief System in a Metropolitan City -- A Top-Down Approach, EURO HOpe mini-conference (European Working Group in Humanitarian Operations, IFORS).
Nedjati, A., Vizvari, B., & Izbirak, G. (2016). Post-earthquake response by small UAV helicopters. Natural Hazards, 80(3), 1669-1688.‏
Dijkstra, E.W, (1959). A note on two problems in connexion with graphs. Numer. https://doi.org/10.1007/BF01386390
Leyzorek, M.; Gray, R. S.; Johnson, A. A.; Ladew, W. C.; Meaker, Jr., S. R.; Petry, R. M.; Seitz, R. N. (1957).— A Study of Model Techniques for Communication Systems. Cleveland, Ohio: Case Institute of Technology. Investigation of Model Techniques — First Annual Report — 6 June 1956 — 1 July 1957.
Bellman, R. (1958). On a routing problem. Quarterly of applied mathematics, 16(1), 87-90.‏
Bellman, R.E. (1957). Dynamic Programming. Princeton University Press, Princeton, NJ. Republished 2003: Dover, ISBN 0-486-42809-5.
Ahuja, R. K., Magnanti, T. L., & Flows, J. O. N. (1993). Theory, algorithms, and applications. In Network flows.‏
B. Vizvári, (2006). Integer programming, (in Hungarian), Typotex, , Budapest
Thorup, M. (2004). Integer priority queues with decrease key in constant time and the single source shortest paths problem. Journal of Computer and System Sciences, 69(3), 330-353.‏
Johannes Baum, (2020). 5 Ways to Find the Shortest Path in a Graph, Medium.com, Better Programming, https://medium.com/better-programming/5-ways-to-find-the-shortest-path-in-a-graph-88cfefd0030f.
Zhu Wang, X. (2018). The Comparison of Three Algorithms in Shortest Path Issue. JPhCS, 1087(2), 022011.‏
Annals of Optimization Theory and Practice
Volume 3, Issue 2
November 2020
Pages 65-80

Files

Share

How to cite

Statistics