A Comparative Study of Metaheuristics Methods for Solving Traveling Salesman Problem

By Agung Chandra, Aulia Naro

Abstract


Abstract In this study, we compare 8 (eight) metaheuristics methods:  GA, SA, TS, ACO, PSO, ABC, EFOA, and A3 for solving traveling salesman problem (tsp) in 70 cities in Java island. The result shows ABC algorithm has the best value and the best average value The results are tested by statistical methods both ANOVA and Tukey test which show the data of distances is not the same for every methods of metaheuristics and 20 pairs are different in means between each pairs

 

Keywords: Metaheuristics Methods, TSP, ANOVA, Tukey test


Full Text:

PDF

References


Olkhova, M., Roslavtsev, D., Matviichuk, O., Mykhalenko, A. “City Delivery Routes Planning Based on The Ant Colony Algorithm. Science and Technology,” Vol.19 no.4., 2020. https://doi.org/10.21122/2227-1031-2020-19-4-356-362.

Russell, S., and P. Norvig. “Artificial Intelligence: A Modern Approach,” New Jersey: Pearson Education,, Inc., 2010.

Saiyed, A.R. “The Traveling Salesman Problem.” Indiana State University, 2012.

Stidsen, T.J.K. Introduction to Optimization using Metaheuristics, 2011. http://www.imm.dtu.dk/courses/02719.

Talbi, E.G. “Metaheuristics: From Design to Implementation”. New Jersey: John Wiley & Sons., 2009.

Koopialipoor, M., Noorbakhsh, A. “Application of Artificial Intelligence Techniques in Optimizing Drilling, Emerging Trends in Mechatronics,” Intech Open, 2020. DOI:105772/intechopen.85398

Oliveira, J.F., and M.A. Carravilla. “Heuristics and Local Search”. FEUP, 2009.

Hussain, K. “Artificial Intelligence Review: Metaheuristic Research: A Comprehensive Survey,” Universiti Tun Hussein On. Malaysia, 2018.

Saud S., Kodaz H., Babaoglu I. “Solving Traveling Salesman Problem by Using Optimization Algorithm,” The 9th International Conference on Advances in Information Technology: IAIT Conference Proceedings, 2018.

Onder, E., M. Ozdemir, and B.F. Yildrim. “Combinatorial Optimization Using Artificial Bee Colony Algorithm and Particle Swarm Optimization Supported Genetic Algorithm,” KAU IIBF Dergisi 4(6): 59 – 70, 2013.

Gharib, A., Benhra, J., and Chaouqi, M. “A Performance Comparison of PSO and GA Applied to TSP,” International Journal of Computer Applications. Vol.130 no.15, 2015.

Huang, L., Wang, G.C., Bai, T., and Wang, Z. “An Improved Fruit Fly Optimization Algorithm for Solving the Traveling Salesman Problem,” Fronties of Information and Electronic Engineering, 2016.

Jayaswal, S. “A Comparative Study of Tabu Search and Simulated Annealing for Traveling Salesman Problem”. Project Report Applied Optimization MSCI 703. Department of Management Sciences. University of Waterloo, 2018.

Yildirim, A.E., and Karci, A. “Application of Traveling Salesman Problem for 81 Provinces in Turkey Using Artificial Atom Algorithm,” 7th International Conference on Advanced Technologies (ICAT 2018). April 28 – May 1, 2018: 722 – 726. Antalya, Turkey, 2018.

Yildirim, A.E., and Karci, A. “Solutions of Traveling Salesman Problem Using Genetic Algorithm and Atom Algorithm,” In proceedings of 2nd International Eurasian Conference on Mathematical Sciences and Applications (IECMSA-2013). Sarajevo, Bosnia and Herzegovina, 2013.

Yildirim, A.E., and Karci, A. “Applications of Artificial Atom Algorithm to Small scale traveling salesman problems,” Journal of Soft Computing, 2017.

Naro, A., and Chandra, A. “Optimasi Jalur Distribusi Dengan Genetic Algorithm,” Research Report, Universitas Mercu Buana., 2019.

Naro, A. and Chandra, A. “Optimasi Jalur Distribusi Dengan Tabu Search,” Research Report, Universitas Mercu Buana, 2019.

Biro Pusat Statistik Republik Indonesia. “Land Transportation Statistics 2017,” Katalog: 8302004. BPSRI, 2018.

Dukic, G., V. Cesnik, T. Opetuk. “Order Picking Methods and Technologies for Greener Warehousing,” Strojarstvo 52 (1), p.23 – 31, 2010.

Luke, S. (2015). Essential of Metaheuristics, George Mason University. On line version 2.2.

Kirk, J. (2014). Traveling Salesman Problem: Genetic Algorithm, Matlab Central File Exchange. Retrieved: January 29, 2019. http://www/mathworks.com/matlabcentral

Johnson, D.S., Aragon, C.R., McGeoch, L.A., and Schevon, C. “Optimization by Simulated Annealing: An Experimental Evaluation Part I, Graph Partitioning,” Operation Research. Vol.37 no.6, November – December, 1989.

Alkallak, I.N., and Sha’ban, R.Z. “Tabu Search Method for Solving the Traveling Salesman Problem,” Raf. Journal of Comp. & Math. Vol.5 no.2, 2015.

Dorigo, M., and Stutzle, T. “Ant Colony Optimization,” Cambridge: A Bradford Book. The MIT Press, 2004.

Bullnheimer, B., Hartl, R.F., and Strauβ, C. “A New Rank Based Version of The Ant System.” Paper presented at Vienna University of Economics and Business Administration. August 2-6, 1997.

Heris, S.M.K. “Ant Colony Optimization for TSP”. Project code: YOEA103. Yarpiz, 2015.

Monteiro, M.S.R., Fontes, D.B.M.M and Fontes, F.A.C.C. “ACO: A Literature Survey,”. University of Porto, 2012.

Clerc, M. (2000). Discrete PSO: Illustrated by the TSP. Accessed April 30, http://www.mauriceclerc.net

Clerc, M. (2012). Standard PSO From 2006 to 2011. Accessed April 30, http://www.mauriceclerc.net

Hanka, M.K.R. “Particle Swarm Optimization for TSP.” Paper presented for Metaheuristics course. Institut Teknologi Sepuluh November. April 14, 2012.

Boussaid, I., Lepagnot, J. and Siarry, P. “A Survey On Optimization Metaheuristics.,” Information Sciences 237: 82-117, 2013.

Iscan, H., and Gunduz, M. “Parameter Analysis on Fruit Fly Optimization Algorithm,” Journal of Computer and Communications, 2: 137 – 141, 2014.






International Journal of Information Science and Technology (iJIST) – ISSN: 2550-5114