Simulated Annealing – 2 Opt Algorithm for Solving Traveling Salesman Problem
DOI:
https://doi.org/10.47839/ijc.22.1.2878Keywords:
simulated annealing, 2 opt algorithm, traveling salesman problem, hybrid simulated annealing – 2 opt algorithmAbstract
The purpose of this article is to elaborate performance of the hybrid model of Simulated Annealing (SA) and 2 Opt algorithm for solving the traveling salesman problem (TSP). The SA algorithm used in this article is based on the outer and inner loop SA algorithm. The hybrid algorithm has promising results in solving small and medium-scale symmetric traveling salesman problem benchmark tests taken from the TSPLIB reference. Results of the optimal solution and standard deviation indicate that the hybrid algorithm shows good performance in terms of reliability and stability in finding the optimal solution from the TSP benchmark case. Values of average error and standard deviation for all simulations in the medium scale are 0.0267 and 644.12, respectively. Moreover, in some cases namely KroB100, Pr107, and Pr144, the hybrid algorithm finds a better solution compared with the best-known solution mentioned in the reference. Further, the hybrid algorithm is 1.207 – 5.692 times faster than the pure outer and inner loop-based SA algorithm. Additionally, the results show that the hybrid algorithm outperforms other hybrid algorithms such as SA – nearest neighbor (NN) and NN – 2 Opt.
References
S. Obadan, Z. Wang, “A hybrid optimization approach for complex nonlinear objective functions,” International Journal of Computing, vol. 17, no. 2, pp.102-112, 2018. https://doi.org/10.47839/ijc.17.2.996
K. Karagul, Aydemir, E. and S. Tokat, “Using 2-Opt based evolution strategy for travelling salesman problem,” An International Journal of Optimization and Control: Theories & Applications (IJOCTA), vol. 6, issue 2, pp. 103-113, 2016. https://doi.org/10.11121/ijocta.01.2016.00268
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, vol. 71, pp. 277-290, 2018. https://doi.org/10.1016/j.asoc.2018.06.047
I. Iryanto, and P. H. Gunawan, “Numerical approach of symmetric traveling salesman problem using simulated annealing,” Jurnal RESTI (Rekayasa Sistem Dan Teknologi Informasi), vol. 5, issue 6, pp.1090-1098, 2021. https://doi.org/10.29207/resti.v5i6.3549
Y. Wang, D. Tian, and Y. H. Li, “An improved simulated annealing algorithm for traveling salesman problem,” Proceedings of the 2012 International Conference on Information Technology and Software Engineering, 2013, pp. 525-532, Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34522-7_56
L. Wang, R. Cai, M. Lin and Y. Zhong, “Enhanced list-based simulated annealing algorithm for large-scale traveling salesman problem,” IEEE Access, vol. 7, pp. 144366-144380, 2019. https://doi.org/10.1109/ACCESS.2019.2945570
N. Azizi, and S. Zolfaghari, “Adaptive temperature control for simulated annealing: a comparative study,” Computers & Operations Research, vol. 31, issue 14, pp. 2439-2451, 2004. https://doi.org/10.1016/S0305-0548(03)00197-7
Z. A. Othman, N. H. Al-Dhwai, A. Srour, and W. Yi, “Water flow-like algorithm with simulated annealing for travelling salesman problems,” International Journal on Advanced Science, Engineering and Information Technology, vol. 7, issue 2, pp. 669-675, 2017. https://doi.org/10.18517/ijaseit.7.2.1837
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. https://doi.org/10.1016/j.eswa.2017.01.053
P. Stodola, K. Michenka, J. Nohel, and M. Rybanský, “Hybrid algorithm based on ant colony optimization and simulated annealing applied to the dynamic traveling salesman problem,” Entropy, vol. 22, issue 8, p. 884, 2020. https://doi.org/10.3390/e22080884
K. Katayama and H. Narihisa, “An efficient hybrid genetic algorithm for the traveling salesman problem,” Electronics and Communications in Japan (Part III: Fundamental Electronic Science), vol. 84, issue 2, pp. 76-83, 2021. https://doi.org/10.1002/1520-6440(200102)84:2<76::AID-ECJC9>3.0.CO;2-O
M. Xu, S. Li, and J. Guo, “Optimization of multiple traveling salesman problem based on simulated annealing genetic algorithm,” In Matec Web of Conferences, EDP Sciences, vol. 100, p. 02025, 2017. https://doi.org/10.1051/matecconf/201710002025
A. H. Zhou, L. P. Zhu, B. Hu, S. Deng, Y. Song, H. Qiu, and S. Pan, “Traveling-salesman-problem algorithm based on simulated annealing and gene-expression programming,” Information, vol. 10, issue 1, p. 7, 2019. https://doi.org/10.3390/info10010007
G. Cabrera, S. Roncagliolo, J. P. Riquelme, C. Cubillos, and R. Soto, “A hybrid particle swarm optimization-simulated annealing algorithm for the probabilistic travelling salesman problem,” Studies in Informatics and Control, vol. 21, issue 1, pp. 49-58, 2012. https://doi.org/10.24846/v21i1y201206
Y. Lin, Z. Bian, and X. Liu, “Developing a dynamic neighborhood structure for an adaptive hybrid simulated annealing–tabu search algorithm to solve the symmetrical traveling salesman problem,” Applied Soft Computing, vol. 49, pp. 937-952, 2016. https://doi.org/10.1016/j.asoc.2016.08.036
İ. Küçükoğlu, R. Dewil, and D. Cattrysse, “Hybrid simulated annealing and tabu search method for the electric travelling salesman problem with time windows and mixed charging rates,” Expert Systems with Applications, vol. 134, pp. 279-303, 2019. https://doi.org/10.1016/j.eswa.2019.05.037
X. Geng, Z. Chen, W. Yang, D. Shi, and K. Zhao, “Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search,” Applied Soft Computing, vol. 11, issue 4, pp. 3680-3689, 2011. https://doi.org/10.1016/j.eswa.2019.05.037
G. Reinelt, “TSPLIB”, 19 February 1997. [Online]. Available at: http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html
S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, issue 4598, pp. 671-680, 1983. https://doi.org/10.1126/science.220.4598.671
D. Delahaye, S. Chaimatanan, and M. Mongeau, “Simulated annealing: From basics to applications,” In Handbook of Metaheuristics, 2019, pp. 1-35, Springer, Cham. https://doi.org/10.1007/978-3-319-91086-4_1
E. K. Burke, and G. Kendall, “Search methodologies: introductory tutorials in optimization and decision support techniques, 2014, pp. 265-285, Springer. https://doi.org/10.1007/978-1-4614-6940-7
M. El Alaoui, and M. Ettaouil, “An adaptive hybrid approach: Combining neural networks and simulated annealing to calculate the equilibrium point in max-stable problem,” IAENG International Journal of Computer Science, vol. 48, issue 4, pp. 893-8982021.
G. A. Croes, “A method for solving travelling salesman problems,” Operations Research, vol. 6, no. 6, pp. 791-812, 1958. https://doi.org/10.1287/opre.6.6.791
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.
A. Hatamlou, “Solving travelling salesman problem using black hole algorithm,” Soft Computing, vol. 22, no. 24, pp. 8167-8175, 2018. https://doi.org/10.1007/s00500-017-2760-y
Downloads
Published
How to Cite
Issue
Section
License
International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:• Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
• Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an 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 website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
