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

Authors

  • Bib Paruhum Silalahi Department of Mathematics, Faculty of Mathematics and Natural Sciences, IPB University, Bogor
  • Farahdila Sahara Department of Mathematics, Faculty of Mathematics and Natural Sciences, IPB University, Bogor
  • Farida Hanum Department of Mathematics, Faculty of Mathematics and Natural Sciences, IPB University, Bogor
  • Hidayatul Mayyani Department of Mathematics, Faculty of Mathematics and Natural Sciences, IPB University, Bogor

DOI:

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

Keywords:

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

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%.

 

 

Author Biography

Bib Paruhum Silalahi, Department of Mathematics, Faculty of Mathematics and Natural Sciences, IPB University, Bogor

Secretary of Applied Mathematics Master's Program, Department of Mathematics, IPB University

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

Downloads

Published

2022-07-16

Issue

Vol. 6 No. 3 (2022): July

Section

Articles

License

Authors who publish articles in JTAM (Jurnal Teori dan Aplikasi Matematika) agree to the following terms:

  1. Authors retain copyright of the article and grant the journal right of first publication with the work simultaneously licensed under a CC-BY-SA or The Creative Commons Attribution–ShareAlike License.
  2. 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 acknowledgment of its initial publication in this journal.
  3. 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 (See The Effect of Open Access).