LEADERS AND FOLLOWERS ALGORITHM FOR TRAVELING SALESMAN PROBLEM
Abstract
Leaders and Followers algorithm is a metaheuristics algorithm. In solving continuous optimization, this algorithm is proved to be better than other well-known algorithms, such as Genetic Algorithm and Particle Swarm Optimization. This paper aims to apply the Leaders and Followers algorithm for the Traveling Salesman Problem (TSP), a well-known combinatorial optimization problem to minimize distance. There are some modifications in order to fit the algorithm in TSP problems. Some most-used-problems in TSP are used to test this algorithm. The result is that the Leaders and Followers algorithm performs well, stable, and guarantees the optimality of the obtained solution in TSP with fewer than 20 cities. In TSP with a bigger number of cities, the proposed algorithm is not stable and might has difficulties in finding the optimal solutions.
Downloads
References
K. Stoilova and T. Stoilov, “Transportation modelling and solving Travelling Salesman problem,” IOP Conf Ser Mater Sci Eng, vol. 878, no. 1, p. 12026, Jun. 2020, doi: 10.1088/1757-899X/878/1/012026.
M. Azizur Rahman, A. Islam, and L. Ershad Ali, “Intelligent Route Construction Algorithm for Solving Traveling Salesman Problem,” IJCSNS International Journal of Computer Science and Network Security, vol. 21, no. 4, p. 33, 2021, doi: 10.22937/IJCSNS.2021.21.4.5.
D.-Z. Du, P. Pardalos, X. Hu, and W. Wu, Introduction to Combinatorial Optimization. 2022. doi: 10.1007/978-3-031-10596-8.
G. Finke, A. Claus, and E. Gunn, “A two-commodity network flow approach to the traveling salesman problem,” Congress Num, vol. 41, Oct. 1984.
A. Hussain, Y. S. Muhammad, M. Nauman Sajid, I. Hussain, A. Mohamd Shoukry, and S. Gani, “Genetic Algorithm for Traveling Salesman Problem with Modified Cycle Crossover Operator,” Comput Intell Neurosci, vol. 2017, 2017, doi: 10.1155/2017/7430125.
S. Elza Ramadhania and S. Rani, “Implementasi Kombinasi Algoritma Genetika dan Tabu Search untuk Penyelesaian Travelling Salesman Problem.”[Online]. Available: http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/
A. MAH, S. I. Hossain, and S. Akter, “A Comparative Study of Prominent Particle Swarm Optimization Based Methods to Solve Traveling Salesman Problem,” International Journal of Swarm Intelligence and Evolutionary Computation, vol. 05, no. 03, 2016, doi: 10.4172/2090-4908.1000139.
A. R. BOTSALI and K. ALAYKIRAN, “Analysis of TSP: Simulated Annealing and Genetic Algorithm Approaches,” International Journal of Computational and Experimental Science and Engineering, vol. 6, no. 1, pp. 23–28, Mar. 2020, doi: 10.22399/ijcesen.637445.
A. H. Zhou et al., “Traveling-salesman-problem algorithm based on simulated annealing and gene-expression programming,” Information (Switzerland), vol. 10, no. 1, Dec. 2018, doi: 10.3390/info10010007.
K. Thirugnanasambandam, R. S. Raghav, D. Saravanan, U. Prabu, and M. Rajeswari, “Experimental analysis of ant system on travelling salesman problem dataset TSPLIB,” EAI Endorsed Trans Pervasive Health Technol, vol. 5, no. 19, 2019, doi: 10.4108/eai.13-7-2018.163092.
M. Isnaini, H. Umam, B. Santosa, and N. Siswanto, Prosiding Seminar Nasional Manajemen Teknologi XXIV Program Studi MMT-ITS, Surabaya 23 Januari 2016 MODIFIKASI ALGORITMA SYMBIOTIC ORGANISMS SEARCH UNTUK TRAVELING SALESMAN PROBLEM.
M. A. H. Akhand, P. C. Shill, Md. F. Hossain, A. B. M. Junaed, and K. Murase, “Producer-Scrounger Method to Solve Traveling Salesman Problem,” International Journal of Intelligent Systems and Applications, vol. 7, no. 3, pp. 29–36, Feb. 2015, doi: 10.5815/ijisa.2015.03.04.
S. Verma, J. J. Jena, C. Satapathy, and M. Rout, “Solving Travelling Salesman Problem using Discreet Social Group Optimization,” 2020. [Online]. Available: https://people.sc.fsu.edu/~jburkardt/datasets/tsp/tsp.ht
H. Garg, “A hybrid PSO-GA algorithm for constrained optimization problems,” Appl Math Comput, vol. 274, pp. 292–305, Feb. 2016, doi: 10.1016/j.amc.2015.11.001.
Y. Gonzalez-Fernandez and S. Chen, “Leaders and followers-A new metaheuristic to avoid the bias of accumulated information,” in 2015 IEEE Congress on Evolutionary Computation, CEC 2015 - Proceedings, Institute of Electrical and Electronics Engineers Inc., Sep. 2015, pp. 776–783. doi: 10.1109/CEC.2015.7256970.
H. Y. Angmalisang, S. Anam, and S. Abusini, “Leaders and followers algorithm for constrained non-linear optimization,” Indonesian Journal of Electrical Engineering and Computer Science, vol. 13, no. 1, pp. 162–169, Jan. 2019, doi: 10.11591/ijeecs.v13.i1.pp162-169.
H. Y. Angmalisang, H. Angmalisang, and S. J. A. Sumarauw, “Leaders and Followers Algorithm for Balanced Transportation Problem,” Computer Engineering and Applications, vol. 12, no. 2, 2023, Accessed: Oct. 01, 2023. [Online]. Available: https://comengapp.unsri.ac.id/index.php/comengapp/article/view/436/265
S. Aramuthakannan, “Revised Distribution Method of finding Optimal Solution for Transportation Problems,” IOSR Journal of Mathematics, vol. 4, pp. 39–42, Oct. 2013, doi: 10.9790/5728-0453942.
H. B. Kalhoro, H. Abdulrehman, M. M. Shaikh, and A. S. Soomro, “THE MAXIMUM RANGE COLUMN METHOD-GOING BEYOND THE TRADITIONAL INITIAL BASIC FEASIBLE SOLUTION METHODS FOR THE TRANSPORTATION PROBLEMS,” 2021.[Online]. Available: https://doi.org/00.00000/jmcms.2021.01.00006
“Data for the Traveling Salesperson Problem.” Accessed: Oct. 01, 2023.[Online]. Available: https://people.sc.fsu.edu/~jburkardt/datasets/tsp/tsp.html
Copyright (c) 2024 Helen Yuliana Angmalisang, Syaiful Anam
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Authors who publish with this Journal agree to the following terms:
- Author retain copyright and grant the journal right of first publication with the work simultaneously licensed under a creative commons attribution license that allow others to share the work within an acknowledgement of the work’s authorship and initial publication of this journal.
- Authors are able to enter into separate, additional contractual arrangement for the non-exclusive distribution of the journal’s published version of the work (e.g. acknowledgement of its initial publication in this journal).
- Authors are permitted and encouraged to post their work online (e.g. in institutional repositories or on their websites) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published works.
1.gif)
