Evaluation of TSP for Emergency Routing
Автор: A. G. M. Zaman, Sajib Hasan, Mohammad Samawat Ullah
Журнал: International Journal of Information Technology and Computer Science @ijitcs
Статья в выпуске: 1 Vol. 13, 2021 года.
Бесплатный доступ
The paper considers the symmetric traveling salesman problem and applies it to sixty-four (64) districts of Bangladesh (with geographic coordinates) as a new instance of the problem of finding an optimized route in need of emergency. It approached three different algorithms namely Integer Linear Programming, Nearest-neighbor, and Metric TSP as exact, heuristic, or approximate methods of solving the NP-hard class of problem to model the emergency route planning. These algorithms have been implanted using computer codes, used IBM ILOG CPLEX parallel optimization, visualized using Geographic Information System tools. The performance of these algorithms also has been evaluated in terms of computational complexity, their run-time, and resulted tour distance using exact, approximate, and heuristic methods to find the best fit of route optimization in emergence thus contributing to the field of combinatorial optimization.
Integer Linear Programming, Nearest Neighbor, Metric TSP, Emergency Response Computational Tool and Models (ERT), Geographical Information System (GIS)
Короткий адрес: https://sciup.org/15017479
IDR: 15017479 | DOI: 10.5815/ijitcs.2021.01.03
Список литературы Evaluation of TSP for Emergency Routing
- Annetta Burger,Talha Oz, William G. Kennedy, and Andrew T. Crooks, Computational Social Science of Disasters: Opportunities and Challenges, IJCAI,26 April 2019.
- Huibo Bi, Erol Gelenbe, Emergency Management Systems and Algorithms: A Comprehensive Survey, arXiv®, Cornell University, 21 Jun 2019.
- World Health Organization, 2019 Novel Coronavirus (2019 nCoV): STRATEGIC PREPAREDNESS AND RESPONSE PLAN, Creative Commons Attribution-NonCommercial-ShareAlike, 3 February 2020.
- National Research Council et al, Successful Response Starts with a Map: Improving Geospatial Support for Disaster Management, Chapter: 3 Emergency Management Framework, 2007, Page 47-80.
- Hoffman K.L., Padberg M., Rinaldi G. (2013) Traveling Salesman Problem. In: Gass S.I., Fu M.C. (eds) Encyclopedia of Operations Research and Management Science. Springer, Boston, MA.
- Thomas H. Cormen, Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stein, Introduction to Algorithms, MIT Press, 2001, Page 1012-1013.
- Suzanne Ma, Understanding the Travelling Salesman Problem (TSP), Routific, January 2, 2020.
- Changshi Liu & Gang Kou & Yi Peng & Fawaz E. Alsaadi, 2019. "Location-Routing Problem for Relief Distribution in the Early Post-Earthquake Stage from the Perspective of Fairness," Sustainability, MDPI, Open Access Journal, vol. 11(12), pages 1-16, June.
- Yi Hong, Deying Li, Qiang Wu, and Hua Xu1, Dynamic Route Network Planning Problem for Emergency Evacuation in Restricted-Space Scenarios, Journal of Advanced Transportation, 27 Jun 2018
- Viana Céspedes, V. (2018.). Optimization in the planning of forest harvesting services. Master's Thesis. University of the Republic (Uruguay). Faculty of Engineering.
- M. Assaf and M. Ndiaye, "Solving an Open Path Multiple Depot Multiple Traveling Salesman Problem after transformation," 2017 7th International Conference on Modeling, Simulation, and Applied Optimization (ICMSAO), Sharjah, 2017, pp. 1-4, doi: 10.1109/ICMSAO.2017.7934866.
- Igor Averbakh & Wei Yu, 2020. "Multi-depot traveling salesmen location problems on networks with special structure," Annals of Operations Research, Springer, vol. 286(1), pages 635-648, March.
- Kusumahardhini, N., Hertono, G. F., & Handari, B. D. (2020). Implementation of K-Means and crossover ant colony optimization algorithm on multiple traveling salesman problem. Journal of Physics: Conference Series, 1442(1), [012035]. https://doi.org/10.1088/1742-6596/1442/1/012035
- Anaya Fuentes GE, Herna´ndez Gress ES, Seck Tuoh Mora JC, Medina Marı´n J (2018) Solution to travelling salesman problem by clusters and a modified multi-restart iterated local search metaheuristic. PLoS ONE 13(8): e0201868. https:// doi.org/10.1371/journal.pone.0201868
- N. Gupta, T. Gupta, S. Samaddar and S. Roy, "WebReLog: A Web-based Tool for Disaster Relief Logistics with Vehicle Route Planning," 2019 IEEE International Conference on Systems, Man and Cybernetics (SMC), Bari, Italy, 2019, pp. 1012-1017, doi: 10.1109/SMC.2019.8913925.
- P. Ganguly and S. Roy, "Post-disaster relief by vehicle route planning and service time estimation in case of Chennai floods," 2017 4th International Conference on Information and Communication Technologies for Disaster Management (ICT-DM), Münster, 2017, pp. 1-8, doi: 10.1109/ICT-DM.2017.8275694.
- Gloria Cerasela Crisan, Camelia Pintea,and PinteaVasile Palade, Emergency management using geographic information systems: application to the first Romanian traveling salesman problem instance, April 2016, Knowledge and Information Systems 50(1):1-21, DOI: 10.1007/s10115-016-0938-8.
- K. Ilavarasi and K. S. Joseph, "Variants of travelling salesman problem: A survey," International Conference on Information Communication and Embedded Systems (ICICES2014), Chennai, 2014, pp. 1-7, doi: 10.1109/ICICES.2014.7033850.
- Padberg, M., Sung, T. An analytical comparison of different formulations of the travelling salesman problem. Mathematical Programming 52, 315–357 (1991). https://doi.org/10.1007/BF01582894
- Matthew Chatting, A Comparison of Exact and Heuristic Algorithms to Solve the Travelling Salesman Problem, The Plymouth Student Scientist, 2018, 11, (2), 53-91
- Michael Hahsler, Kurt Hornik, TSP Infrastructure for the Traveling Salesperson Problem, Journal of Statistical Software, December 2007, Volume 23, Issue 2.
- Kevin M. Curtin, Gabriela Voicu Matthew T. Rice, Anthony Stefanidis, A Comparative Analysis of Traveling Salesman Solutions from Geographic Information Systems, Wiley, 09 June 2013, https://doi.org/10.1111/tgis.12045
- Chapter 9, Integer Programming and Combinatorial Optimization, MIT Open Courseware, MIT Course Number 15.083J / 6.859J
- C. E. Miller, Albert W Tucker, R A Zemlin, Integer Programming Formulation of Traveling Salesman Problems, Journal of the ACM,October 1960, https://doi.org/10.1145/321043.321046
- Graver, J.E. On the foundations of linear and integer linear programming I. Mathematical Programming 9, 207–226 (1975). https://doi.org/10.1007/BF01681344
- Andersen ED, Gondzio J, Mészáros C, Xu X (1996) Implementation of interior point methods for large scale linear programming. In: Terlaky T (ed) Interior Point Methods in Mathematical Programming.
- Rujira Visuthirattanamanee, Krung Sinapiromsaran,and Aua-aree Boonperm, Self-Regulating Artificial-Free Linear Programming Solver Using a Jump and Simplex Method, mathematics- MDPI, 5 March 2020
- J. Zhu, S. Qian and T. Shi, "Simplex Method of Computer Algorithms Practice," 2010 Second International Conference on Computer Research and Development, Kuala Lumpur, 2010, pp. 756-759, doi: 10.1109/ICCRD.2010.169.
- CPLEX Optimizer, IBM, https://www.ibm.com/analytics/cplex-optimizer
- N. Fares, M. Lebbar and N. Sbihi, "Quick response in fast fashion retail: An optimization supply chain responsiveness model," 2018 4th International Conference on Optimization and Applications (ICOA), Mohammedia, 2018, pp. 1-5, doi: 10.1109/ICOA.2018.8370565.
- E.M.L.Beale, Branch and Bound Methods for Mathematical Programming Systems, Annals of Discrete Mathematics, Volume 5, 1979, Pages 201-219
- David Applegate, Robert Bixby, Vasek Chvatal, William Cook, On the Solution of Traveling Salesman Problem, Documenta Mathematica-Extra Volume ICM 1998-III, 645-656
- Gözde Kizilateş, Fidan Nuriyeva, Chapter on the Nearest Neighbor Algorithms for the Traveling Salesman Problem, Advances in Computational Science, Engineering and Information Technology, 2013, Volume 225
- E. O. Asani, A. E. Okeyinka and A. A. Adebiyi, "A Construction Tour Technique For Solving The Travelling Salesman Problem Based On Convex Hull And Nearest Neighbour Heuristics," 2020 International Conference in Mathematics, Computer Engineering and Computer Science (ICMCECS), Ayobo, Ipaja, Lagos, Nigeria, 2020,pp.1-4,doi:10.1109/ICMCECS47690.2020.240847.
- Stefan Hougardy, Mirko Wilde, On the nearest neighbor rule for the metric traveling salesman problem, 27 March 2014, Discrete Applied Mathematics, Elsevier B.V.
- S. Dhakal and R. Chiong, "A hybrid nearest neighbour and progressive improvement approach for Travelling Salesman Problem," 2008 International Symposium on Information Technology, Kuala Lumpur, 2008, pp. 1-4, doi: 10.1109/ITSIM.2008.4631549.
- A H Ismail et al, Domino algorithm: a novel constructive heuristics for traveling salesman problem, 2019, IOP Conference Series: Materials Science and Engineering.
- Bläser M. (2008) Metric TSP. In: Kao MY. (eds) Encyclopedia of Algorithms. Springer, Boston, MA
- Chandra Chekuri, Kent Quanrud, Fast Approximations for Metric-TSP via Linear Programming, 5 Feb 2018, arXiv:1802.01242 [cs.DS]
- Vladimir Deineko, Alexander Tiskin, Fast minimum-weight double-tree shortcutting for Metric TSP: Is the best one good enough?, 1 Oct 2007, arXiv:0710.0318 [cs.DS]
- Christopher Clapham and James Nicholson, The Concise Oxford Dictionary of Mathematics (4 ed.), 2013, Oxford University Press.
- Haiming Li, Qiyang Xia, Yong Wang, Research and Improvement of Kruskal Algorithm, October 2017, Journal of Computer and Communications, Vol.5 No.12.
- Global Administrative Areas (2012). GADM database of Global Administrative Areas, version 2.0. [online] URL: www.gadm.org
- QGIS.org (2020). QGIS Geographic Information System. Open Source Geospatial Foundation Project. http://qgis.org
- ESRI 2017. ArcGIS Desktop: Release 10. Redlands, CA: Environmental Systems Research Institute.
- Jennex, Murray E., Using Social and Information Technologies for Disaster and Crisis Management, Jan 31, 2013, IGI Global.
- Sisi Zlatanova, Jonathan Li, Geospatial Information Technology for Emergency Response, Jan 24, 2008, CRC Press.
- IBM ILOG (2012) User’s manual for CPLEX. ftp://public.dhe.ibm.com/software/websphere/ilog/docs/optimization/cplex/ps_usrmancplex
- Kemball-Cook D, Stephenson R (1984) Lessons in logistics from Somalia. Disasters 8:57–66
- Kirac E et al (2015) The traveling salesman problem with imperfect information with application in disaster relief tour planning. IIE Trans 47(8):783–799
- Wex F et al (2014) Emergency response in natural disaster management: allocation and scheduling of rescue units. Eur J Oper Res 235(3):697–708
Статья научная
