A Comparative Analysis of Four Path Optimization Algorithms


A Comparative Analysis of Four Path Optimization Algorithms


Charles OKONJI *; Olawale J. OMOTOSHO; OGBONNA, A. C.

Department of Computer Science, Babcock University


Path / route optimization for promptly moving equipment and personnel from base to disaster location has remained a nagging challenges for effective emergency response particularly within the context of developing countries. Bad road networks, poor and outdated navigation systems, faulty transportation vehicles, and traffic congestion remain among the top challenges militating against effective emergency response, and this has resulted in mounting statistics of losses for lives and properties within such jurisdictions. The pressing question has been: how can emergency response itinerary be planned and scheduled most optimally and reliably in the face of these challenges? This research paper compares four of the more popular path / route optimization algorithms (the Ant Colony Optimization Algorithm, Dijkstra’s Algorithm, Bellman Ford’s Algorithm, and Suurballe’s Algorithm), in order to determine the trade-offs and advantages that they present with respect to each other, and propose actionable recommendations for implementation. The findings of this research would prove useful for emergency response planning, particularly within the context of developing countries where these challenges are commonplace.


Keywords: Emergency response; Emergency planning; Path optimization; Route optimization; Emergency Management.


Free Full-text PDF


How to cite this article:
Charles OKONJI; Olawale J. OMOTOSHO; OGBONNA, A. C..A Comparative Analysis of Four Path Optimization Algorithms.International Journal of Communications and Networks, 2020, 3:8. DOI: 10.28933/ijcn-2020-03-1505


References:

1. Baugh, S., Calinescu, G., Rincon-Cruz, D., & Qiao, K. (2016). Improved Algorithms for Two Energy-Optimal Routing Problems in Ad-Hoc Wireless Networks. 2016 IEEE International Conferences on Big Data and Cloud Computing (BDCloud), Social Computing and Networking (SocialCom), Sustainable Computing and Communications (SustainCom)(BDCloud-SocialCom-SustainCom) (pp. 509-516). Atlanta, GA, USA: IEEE. doi:https://doi.org/10.1109/BDCloud-SocialCom-SustainCom.2016.80
2. Becerra-Fernandez, I., & Prietula, M. (2006). Project Ensayo: Integrating simulation, training, discovery, and support. North American Association for Computational Social and Organizational Science (NAACSOS). Notre Dame, Indiana.
3. Becerra-Fernandez, I., Prietula, M., Madey, G., Rodriguez, D., Gudi, A., & Rocha, J. (2007). Project Ensayo: A Virtual Emergency Operations Center. 16th International Conference on Management of Technology. Miami Beach, Florida.
4. Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16, 87–90. doi:https://doi.org/10.1090/qam/102435
5. Bhandari, R. (1999). Suurballe’s disjoint pair algorithms. In Survivable Networks: Algorithms for Diverse Routing (pp. 86–91). Springer-Verlag.
6. Blum, C. (2005). Ant colony optimization: Introduction and recent trends. Physics of Life Reviews, 2(4), 353-373. doi:https://doi.org/10.1016/j.plrev.2005.10.001
7. Broumi, S., Bakal, A., Talea, M., Smarandache, F., & Vladareanu, L. (2016). Applying Dijkstra algorithm for solving neutrosophic shortest path problem. 2016 International Conference on Advanced Mechatronic Systems (ICAMechS) (pp. 412-416). Melbourne, VIC, Australia: IEEE. doi:https://doi.org/10.1109/ICAMechS.2016.7813483
8. Broumi, S., Nagarajan, D., Lathamaheswari, M., Talea, M., Bakali, A., & Smarandache, F. (2019). Bellman-Ford Algorithm Under Trapezoidal Interval Valued Neutrosophic Environment. International Conference on Computing (pp. 174-184). https://doi.org/10.1007/978-3-030-36368-0_15.
9. Ciesielski, K. C., Falcão, A. X., & Miranda, P. A. (2018). Path-value functions for which Dijkstra’s algorithm returns optimal mapping. Journal of Mathematical Imaging and Vision, 60(7), 1025-1036. doi:https://doi.org/10.1007/s10851-018-0793-1
10. Corne, D., Dorigo, M., & Glover, F. (1999). New Ideas in Optimization. New York, NY: McGraw-Hill.
11. Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269–271. doi:https://doi.org/10.1007/BF01386390
12. Dinitz, Y., & Itzhak, R. (2017). Hybrid Bellman–Ford–Dijkstra algorithm. Journal of Discrete Algorithms, 42, 35-44. doi:https://doi.org/10.1016/j.jda.2017.01.001
13. Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 26(1), 29-41. doi:https://doi.org/10.1109/3477.484436
14. Doshi, M., & Kamdar, A. (2018). Multi-constraint QoS disjoint multipath routing in SDN. 2018 Moscow Workshop on Electronic and Networking Technologies (MWENT) (pp. 1-5). Moscow, Russia: IEEE. doi:https://doi.org/10.1109/MWENT.2018.8337305
15. Fiedrich, F., Gehbauer, F., & Rickers, U. (2000). Optimized resource allocation for emergency response after earthquake disasters. Safety Science, 35(1-3), 41-57. doi:https://doi.org/10.1016/S0925-7535(00)00021-7
16. Fingler, H., Cáceres, E. N., Mongelli, H., & Song, S. W. (2014). A CUDA based Solution to the Multidimensional Knapsack Problem Using the Ant Colony Optimization. Procedia Computer Science, 29, 84–94. doi:https://doi.org/10.1016/j.procs.2014.05.008
17. Ford Jr, L. R. (1956). Network Flow Theory. Santa Monica, California: RAND Corporation.
18. Government Accountability Office (GAO). (2006, March 08). Hurricane Katrina: GAO’s preliminary observations regarding preparedness, response, and recovery. Retrieved January 31, 2020, from US Government Accountability Office: https://www.gao.gov/new.items/d06442t.pdf
19. Helfert, F., Niedermayer, H., & Carle, G. (2018). Evaluation of algorithms for multipath route selection over the Internet. 21st Conference on Innovation in Clouds, Internet and Networks and Workshops (ICIN) (pp. 1-8). Paris, France: IEEE. doi:https://doi.org/10.1109/ICIN.2018.8401640
20. Ismkhan, H. (2017). Effective heuristics for ant colony optimization to handle large-scale problems. Swarm and Evolutionary Computation, 32, 140-149. doi:https://doi.org/10.1016/j.swevo.2016.06.006
21. Kalpana, M. A., & Tyagi, M. A. (2017). Bellman ford shortest path algorithm using global positioning system. International Research Journal of Engineering and Technology (IRJET), 4(04), 2503-2507. Retrieved February 01, 2020, from https://67.209.122.217/archives/V4/i4/IRJET-V4I4624.pdf
22. Kapoor, M. (2009). Disaster Management. New Delhi, India: Motilal Banaisidasi Publishers Pvt. Ltd.
23. Krishna, K. S., & Kumar, P. R. (2015). On the amenability and suitability of ant colony algorithms for convoy movement problem. Procedia-Social and Behavioral Sciences, 189, 3-16. doi:https://doi.org/10.1016/j.sbspro.2015.03.187
24. Kucukkoc, I., & Zhang, D. Z. (2015). Type-E parallel two-sided assembly line balancing problem: Mathematical model and ant colony optimisation based approach with optimised parameters. Computers & Industrial Engineering, 84, 56-69. doi:https://doi.org/10.1016/j.cie.2014.12.037
25. Lazarowska, A. (2014). Ant colony optimization based navigational decision support system. Procedia Computer Science, 35, 1013-1022. doi:https://doi.org/10.1016/j.procs.2014.08.187
26. Magzhan, K., & Jani, H. M. (2013). A review and evaluations of shortest path algorithms. International Journal of Scientific and Technology Research, 2(6), 99 -104.
27. Mushkatel, A. H., & Weschler, L. F. (1985). Emergency management and the intergovernmental system. Public Administration Review, 45, 49-56. doi:https://doi.org/10.2307/3134997
28. Pašić, A., Babarczi, P., Tapolcai, J., Bérczi-Kovács, E. R., Király, Z., & Rónyai, L. (2020). Minimum Cost Survivable Routing Algorithms for Generalized Diversity Coding. IEEE/ACM Transactions on Networking, Online First, 1-12. doi:https://doi.org/10.1109/TNET.2019.2963574
29. Prakasam, A., & Savarimuthu, N. (2015). Metaheuristic algorithms and polynomial Turing reductions: A case study based on ant colony optimization. Procedia Computer Science, 46, 388-395. doi:https://doi.org/10.1016/j.procs.2015.02.035
30. Schambers, A., Eavis-O’Quinn, M., Roberge, V., & Tarbouchi, M. (2018). Route planning for electric vehicle efficiency using the Bellman-Ford algorithm on an embedded GPU. 4th International Conference on Optimization and Applications (ICOA) (pp. 1-6). Mohammedia, Morocco: IEEE. doi:https://doi.org/%2010.1109/ICOA.2018.8370584
31. Shimbel, A. (1955). Structure in communication nets. Proceedings of the Symposium on Information Networks (pp. 199–203). New York, NY: Polytechnic Press of the Polytechnic Institute of Brooklyn.
32. Shtovba, S. D. (2005). Ant algorithms: Theory and applications. Programming and Computer Software, 31(4), 167-178.
33. Stanton, T. H. (2007, January 12). Delivery of benefits in an Emergency: Lessons from hurricane. Retrieved January 31, 2020, from IBM Center for the Business of Government: http://www.businessofgovernment.org/sites/default/files/StantonKatrinaReport.pdf
34. Suurballe, J. W. (1974). Disjoint paths in a network. Networks, 4(2), 125–145. doi:https://doi.org/10.1002%2Fnet.3230040204
35. Suurballe, J. W., & Tarjan, R. E. (1984). A quick method for finding shortest pairs of disjoint paths. Networks, 14(2), 325-336. doi:https://doi.org/10.1002/net.3230140209
36. Swathika, O. V., Hemamalini, S., Mishra, S., Pophali, S. M., & Barve, N. A. (2016). Shortest Path Identification in Reconfigurable Microgrid Using Hybrid Bellman Ford-Dijkstra’s Algorithm. Advanced Science Letters, 22(10), 2932-2935.
37. Talbi, E. G. (2009). Metaheuristics: From design to implementation (volume 74). New Jersey, NJ: John Wiley & Sons.
38. Waleed, S., Faizan, M., Iqbal, M., & Anis, M. I. (2017). Demonstration of single link failure recovery using Bellman Ford and Dijikstra algorithm in SDN. International Conference on Innovations in Electrical Engineering and Computational Technologies (ICIEECT) (pp. 1-4). Karachi, Pakistan: IEEE. doi:https://doi.org/10.1109/ICIEECT.2017.7916533
39. Walle, B. V., & Turoff, M. (2007, March). Introduction. Communications of the ACM (Emergency response information systems: Emerging trends and technologies), 50(3), 29-31. Retrieved from http://doi.org/10.1145/1226736.1226760
40. Weber, A., Kreuzer, M., & Knoll, A. (2020). A generalized Bellman-Ford Algorithm for Application in Symbolic Optimal Control. arXiv preprint, arXiv:2001.06231, 1-8. Retrieved February 09, 2020, from https://arxiv.org/pdf/2001.06231.pdf
41. Zlatanova, S., & Fabbri, A. G. (2009). Geo-ICT for risk and disaster management. In H. J. Scholten, R. van de Velde, & N. van Manen (Eds.), Geospatial Technology and the Role of location in Science (Vols. 96, GeoJournal Library, pp. 239-266). Springer, Dordrecht. doi:https://doi.org/10.1007/978-90-481-2620-0_13