Numerical Approach of Symmetric Traveling Salesman Problem Using Simulated Annealing

  • I Iryanto Politeknik Negeri Indramayu
  • Putu Harry Gunawan
Keywords: simulated annealing, traveling salesman problem, symmetric TSP, square grid TSP

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

Download data is not yet available.

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.

Published
2021-12-30
How to Cite
Iryanto, I., & Gunawan, P. H. (2021). Numerical Approach of Symmetric Traveling Salesman Problem Using Simulated Annealing. Jurnal RESTI (Rekayasa Sistem Dan Teknologi Informasi), 5(6), 1090 - 1098. https://doi.org/10.29207/resti.v5i6.3549
Section
Artikel Teknologi Informasi