Numerical Approach of Symmetric Traveling Salesman Problem Using Simulated Annealing
Abstract
The aim of this paper is to elaborate the performance of Simulated Annealing (SA) algorithm for solving traveling salesmen problems. In this paper, SA algorithm is modified by using the interaction between outer and inner loop of algorithm. This algorithm produces low standard deviation and fast computational time compared with benchmark algorithms from several research papers. Here SA uses a certain probability as indicator for finding the best and worse solution. Moreover, the strategy of SA as cooling to temperature ratio is still given. Thirteen benchmark cases and thirteen square grid symmetric TSP are used to see the performance of the SA algorithm. It is shown that the SA algorithm has promising results in finding the best solution of the benchmark cases and the squared grid TSP with relative error 0 - 7.06% and 0 – 3.31%, respectively. Further, the SA algorithm also has good performance compared with the well-known metaheuristic algorithms in references.
Downloads
References
A. C. Cinar, S. Korkmaz, and M. S. Kiran. “A discrete tree-seed algorithm for solving symmetric traveling salesman problem.” Engineering Science and Technology, an International Journal, vol. 23, no. 4, pp. 879-890, 2020.
A. Hatamlou. “Solving travelling salesman problem using black hole algorithm.” Soft Computing, vol. 22, no. 24, pp. 8167-8175, 2018.
Z. Daoqing and J. Mingyan. “Parallel discrete lion swarm optimization algorithm for solving traveling salesman problem.” Journal of Systems Engineering and Electronics, vol. 31, no. 4 pp. 751-760, 2020.
R. Dong, S. Wang, G. Wang, and X. Wang. “Hybrid optimization algorithm based on wolf pack search and local search for solving traveling salesman problem.” Journal of Shanghai Jiaotong University (Science), vol. 24, no. 1, pp. 41-47, 2019.
S. A. Bakar and M. Ibrahim. “Optimal solution for travelling salesman problem using heuristic shortest path algorithm with imprecise arc length.” In AIP Conference Proceedings, AIP Publishing LLC, vol. 1870, no. 1, pp. 040061, 2017.
Panda, Madhumita. “Performance Comparison of Genetic Algorithm, Particle Swarm Optimization and Simulated Annealing Applied to TSP.” International Journal of Applied Engineering Research, vol. 13, no. 9, pp. 6808-6816, 2018.
S. Saud, H. Kodaz, and I. Babaoğlu, “Solving Travelling Salesman Problem by Using Optimization Algorithms” in The 9th International Conference on Advances in Information Technology, KnE Life Sciences, pp 17-32, 2017.
X. Wang, A. Mu, and S. Zhu. “ISPO: A new way to solve traveling salesman problem.” Intelligent Control and Automation, vol. 4, no. 2, 2013.
Zhou, Ai-Hua, Li-Peng Zhu, Bin Hu, Song Deng, Yan Song, Hongbin Qiu, and Sen Pan. “Traveling-salesman-problem algorithm based on simulated annealing and gene-expression programming.” Information, vol. 10, no. 1, 2019.
A. E. S. Ezugwu, A. O. Adewumi, and M. E. Frîncu. “Simulated annealing based symbiotic organisms search optimization algorithm for traveling salesman problem.” Expert Systems with Applications, vol. 77, pp. 189-210, 2017.
Zhan, Shi-hua, Juan Lin, Ze-jun Zhang, and Yi-wen Zhong. “List-based simulated annealing algorithm for traveling salesman problem.” Computational intelligence and neuroscience, 2016.
A. Khumaidi, R. Raafi’udin, and I. P. Solihin. (2020) “Simulation Of Traveling Salesman Problem For Distribution Of Fruits In Bogor City With Simulated Annealing Method.” Jurnal Mantik, vol. 3, no. 4, pp. 611-618, 2020.
C. Wang, M. Lin, Y. Zhong, and H. Zhang. “Swarm simulated annealing algorithm with knowledge-based sampling for travelling salesman problem.” International Journal of Intelligent Systems Technologies and Applications, vol. 15, no. 1, pp. 74-94, 2016.
M. Makuchowski. “Effective algorithm of simulated annealing for the symmetric traveling salesman problem.” In International Conference on Dependability and Complex Systems (pp. 348-359). Springer, Cham, July. 2018.
X. Han, Y. Dong, L. Yue, and Q. Xu. “State transition simulated annealing algorithm for discrete-continuous optimization problems.” IEEE Access, 7, 44391-44403, 2019.
L. Xiong and S. Li. “Solving TSP Based on the Improved Simulated Annealing Algorithm with Sequential Access Restrictions.” In 2016 6th International Conference on Mechatronics, Computer and Education Informationization (MCEI 2016), Atlantis Press, pp. 610-616, 2016.
M. Rahbari and A. Jahed. “A Hybrid Simulated Annealing Algorithm for Travelling Salesman Problem with Three Neighbor Generation Structures”. In 10th International Conference of Iranian Operations Research Society (ICIORS 2017), Babolsar, Iran, May. 2017.
L. Wang, R. Cai, M. Lin, and Y. Zhong. “Enhanced list-based simulated annealing algorithm for large-scale traveling salesman problem.” IEEE Access, 7, 144366-144380, 2019.
Y. Chunhua, T. Xiaolin, Z. Xiaojun, and G. Weihua. “State transition algorithm for traveling salesman problem.” In Proceedings of the 31st Chinese Control Conference, IEEE, pp. 2481-2485, 2012.
E. Osaba, J. Del Ser, A. Sadollah, M. N. Bilbao, and D. Camacho. “A discrete water cycle algorithm for solving the symmetric and asymmetric traveling salesman problem.” Applied Soft Computing, 71, 277-290, 2018.
G. Reinelt, “TSPLIB”, 19 February 1997. Available: http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html [Accessed on 18 January 2021]
P. H. Siqueira, S. Scheer, and M. T. A. Steiner. “A recurrent neural network to traveling salesman problem.” Travelling Salesman Problem, I-Tech Veinna, pp. 135-156, 2008.
Copyright (c) 2021 Jurnal RESTI (Rekayasa Sistem dan Teknologi Informasi)
This work is licensed under a Creative Commons Attribution 4.0 International License.
Copyright in each article belongs to the author
- The author acknowledges that the RESTI Journal (System Engineering and Information Technology) is the first publisher to publish with a license Creative Commons Attribution 4.0 International License.
- Authors can enter writing separately, arrange the non-exclusive distribution of manuscripts that have been published in this journal into other versions (eg sent to the author's institutional repository, publication in a book, etc.), by acknowledging that the manuscript has been published for the first time in the RESTI (Rekayasa Sistem dan Teknologi Informasi) journal ;
