Simulated Annealing Algorithm for Determining Travelling Salesman Problem Solution and Its Comparison with Branch and Bound Method

Bib Paruhum Silalahi; Farahdila Sahara; Farida Hanum; Hidayatul Mayyani

doi:10.31764/jtam.v6i3.8481

Simulated Annealing Algorithm for Determining Travelling Salesman Problem Solution and Its Comparison with Branch and Bound Method

Bib Paruhum Silalahi, Farahdila Sahara, Farida Hanum, Hidayatul Mayyani

Abstract

Travelling Salesman Problem (TSP) is a problem where a person must visit some places, starting from one city and then moving on to the next city with the conditions that the places visited can only be passed precisely once and then back to the starting city. TSP is an NP-hard, an important problem in operations research. TSP problems can be solved by an exact method or an approximation method, namely the metaheuristic method. This research aims to solve the TSP problem with an approximation method called the Simulated Annealing (SA), and then compare the results of this approximation method with the exact Branch and Bound method. The results indicated that the SA method could accomplish TSP problems. However, like other metaheuristic methods, SA only accomplishes it using an approach to get good results. Still, it cannot be determined that SA has the most optimal results, but the time needed by the SA method is faster than the Branch and Bound method. In case I, the percentage difference between the distance generated using the SA method with the B-and-B method is 0%, in case II it is 7% and in case III it is 8%.

Keywords

Branch and Bound; Integer Linear Programming; Simulated Annealing; Travelling Salesman Problem;

Full Text:

DOWNLOAD [PDF]

References

Alipour, M. M., Razavi, S. N., Feizi Derakhshi, M. R., & Balafar, M. A. (2018). A hybrid algorithm using a genetic algorithm and multiagent reinforcement learning heuristic to solve the traveling salesman problem. Neural Computing and Applications, 30(9). https://doi.org/10.1007/s00521-017-2880-4

Bayram, H., & Şahin, R. (2013). A new simulated annealing approach for travelling salesman problem. Mathematical and Computational Applications, 18(3), 313–322. https://doi.org/10.3390/mca18030313

Benhida, S., & Mir, A. (2018). Generating subtour elimination constraints for the Traveling Salesman Problem. IOSR Journal of Engineering, 8(7), 17–21.

Botsali, A. R., & Alaykiran, K. (2020). Analysis of TSP: Simulated Annealing and Genetic Algorithm Approaches. International Journal of Computational and Experimental Science and Engineering, 6(1). https://doi.org/10.22399/ijcesen.637445

Dorigo, M., & Gambardella, L. M. (1997). Ant colonies for the travelling salesman problem. BioSystems, 43(2). https://doi.org/10.1016/S0303-2647(97)01708-5

Ezugwu, A. E. S., Adewumi, A. O., & Frîncu, M. E. (2017). Simulated annealing based symbiotic organisms search optimization algorithm for traveling salesman problem. Expert Systems with Applications, 77. https://doi.org/10.1016/j.eswa.2017.01.053

Fournier, J. C. (2009). Graph Theory and Applications: With Exercises and Problems. In Graph Theory and Applications: With Exercises and Problems. Wiley Online Books. https://doi.org/10.1002/9780470611548

He, Q., Wu, Y. le, & Xu, T. W. (2018). Application of improved genetic simulated annealing algorithm in TSP optimization. Kongzhi Yu Juece/Control and Decision, 33(2). https://doi.org/10.13195/j.kzyjc.2016.1666

Jünger, M., Reinelt, G., & Rinaldi, G. (1995). Chapter 4 The traveling salesman problem. In Handbooks in Operations Research and Management Science (Vol. 7, Issue C). https://doi.org/10.1016/S0927-0507(05)80121-5

Lalang, D., Silalahi, B. P., & Bukhari, F. (2018). Vehicle Routing Problem Time Windows Dengan Pengemudi Sesekali. Journal of Mathematics and Its Applications, 17(2), 87–98. https://doi.org/10.29244/jmap.17.2.87-99

Liu, F., & Zeng, G. (2009). Study of genetic algorithm with reinforcement learning to solve the TSP. Expert Systems with Applications, 36(3 PART 2). https://doi.org/10.1016/j.eswa.2008.08.026

Making, S. R. M., Silalahi, B. P., & Bukhari, F. (2018). Multi Depot Vehicle Routing Problem dengan Pengemudi Sesekali. Journal of Mathematics and Its Applications, 17(1), 75–86. https://doi.org/10.29244/jmap.17.1.75-86

Othman, Z. A., Al-Dhwai, N. H., Srour, A., & Diyi, W. (2017). Water flow-like algorithm with simulated annealing for travelling salesman problems. International Journal on Advanced Science, Engineering and Information Technology, 7(2). https://doi.org/10.18517/ijaseit.7.2.1837

Qamar, M. S., Tu, S., Ali, F., Armghan, A., Munir, M. F., Alenezi, F., Muhammad, F., Ali, A., & Alnaim, N. (2021). Improvement of traveling salesman problem solution using hybrid algorithm based on best-worst ant system and particle swarm optimization. Applied Sciences (Switzerland), 11(11). https://doi.org/10.3390/app11114780

Rehab, F. (2011). Fuzzy Particle Swarm Optimization with Simulated Annealing and Neighborhood Information Communication for Solving TSP. International Journal of Advanced Computer Science and Applications, 2(5). https://doi.org/10.14569/ijacsa.2011.020503

Rere, L. M. R., Fanany, M. I., & Arymurthy, A. M. (2015). Simulated Annealing Algorithm for Deep Learning. Procedia Computer Science, 72, 137–144. https://doi.org/10.1016/j.procs.2015.12.114

Rokbani, N., Kumar, R., Abraham, A., Alimi, A. M., Long, H. V., Priyadarshini, I., & Son, L. H. (2021). Bi-heuristic ant colony optimization-based approaches for traveling salesman problem. Soft Computing, 25(5). https://doi.org/10.1007/s00500-020-05406-5

Silalahi, B. P., Fathiah, N., & Supriyo, P. T. (2019). Use of Ant Colony Optimization Algorithm for Determining Traveling Salesman Problem Routes. Jurnal Matematika “MANTIK,” 5(2), 100–111. https://doi.org/10.15642/mantik.2019.5.2.100-111

Silalahi, B. P., Fatihin, K., Supriyo, P. T., & Guritman, S. (2020). Algoritme Sweep dan Particle Swarm Optimization dalam Optimisasi Rute Kendaraan dengan Kapasitas. Jurnal Matematika Integratif, 16(1), 29. https://doi.org/10.24198/jmi.v16.n1.27474.29-40

Stodola, P., Michenka, K., Nohel, J., & Rybanský, M. (2020). Hybrid algorithm based on ant colony optimization and simulated annealing applied to the dynamic traveling salesman problem. Entropy, 22(8). https://doi.org/10.3390/E22080884

Wang, L., Cai, R., Lin, M., & Zhong, Y. (2019). Enhanced List-Based Simulated Annealing Algorithm for Large-Scale Traveling Salesman Problem. IEEE Access, 7. https://doi.org/10.1109/ACCESS.2019.2945570

Yang, L., Hu, X., Li, K., Ji, W., Hu, Q., Xu, R., & Wang, D. (2020). Nested Simulated Annealing Algorithm to Solve Large-Scale TSP Problem. Communications in Computer and Information Science, 1205 CCIS. https://doi.org/10.1007/978-981-15-5577-0_37

Yu, M. (2019). A solution of TSP based on the ant colony algorithm improved by particle swarm optimization. Discrete and Continuous Dynamical Systems - Series S, 12(4–5). https://doi.org/10.3934/dcdss.2019066

Yu, Y. Y., Chen, Y., & Li, T. Y. (2014). Improved genetic algorithm for solving TSP. Kongzhi Yu Juece/Control and Decision, 29(8). https://doi.org/10.13195/j.kzyjc.2013.0598

Zhan, S., Lin, J., Zhang, Z., & Zhong, Y. (2016). List-Based Simulated Annealing Algorithm for Traveling Salesman Problem. Computational Intelligence and Neuroscience, 2016, 1–12. https://doi.org/10.1155/2016/1712630

Zhong, W. L., Zhang, J., & Chen, W. N. (2007). A novel discrete particle swarm optimization to solve traveling salesman problem. 2007 IEEE Congress on Evolutionary Computation, CEC 2007. https://doi.org/10.1109/CEC.2007.4424894

DOI: https://doi.org/10.31764/jtam.v6i3.8481