Theoretical and Natural Science
- The Open Access Proceedings Series for Conferences
Theoretical and Natural Science
Vol. 18, 08 December 2023
Open
Access | Article
A comparative study between SA and GA in solving MTSP
* Author to whom correspondence should be addressed.
Abstract
The multiple traveling salesmen problems (MTSP) is a combinatorial optimization and np-hard problem. In practice, the computational resource required to solve such problems is usually prohibitive, and, in most cases, using heuristic algorithms is the only practical option. This paper implements genetic algorithms (GA) and simulated annealing (SA) to solve the MTSP and does an experimental study based on a benchmark from the TSPLIB instance to compare the performance of two algorithms in reality. The results show that GA can achieve an acceptable solution in a shorter time for any of the MTSP cases and is more accurate when the data size is small. Meanwhile, SA is more robust and achieves a better solution than GA for complex MTSP cases, but it takes more time to converge. Therefore, the result indicates that it is hard to identify which algorithm is comprehensively superior to the other one. However, It also provides an essential reference to developers who want to choose algorithms to solve MTSP in real life, facilitating them to balance the algorithm’s performance on different metrics they value.
Keywords
multiple travelling salesmen problem (MTSP), NP-hard, optimization, Simulated Annealing (SA), genetic algorithms (GAs), Algorithm comparison, algorithm selection
References
1. Estévez-Fernández, A., Borm, P., Hamers, H. (2006) On the core of multiple longest traveling salesman games. European journal of operational research, 174(3): 1816-1827.
2. Xu, M., Li, S., Guo, J. (2017) Optimization of multiple traveling salesman problem based on simulated annealing genetic algorithm. Matec web of conferences, 100: 02025.
3. Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., Teller, E. (1953) Equation of state calculations by fast computing machines. The journal of chemical physics, 21(6): 1087-1092.
4. Binder K (1978) Monte Carlo methods in statistical physics. Springer, Berlin
5. Burke, E. K., Burke, E. K., Kendall, G., Kendall, G. (2014) Search methodologies: introductory tutorials in optimization and decision support techniques. Springer, Scotland.
6. Bao, Z., Yu, J., Yang, S. (2016) Intelligent optimization algorithm and its MATLAB example. Publishing House of Electronics Industry, Beijing.
7. Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Reading, MA: Addison Wesley
8. Tang, L., Liu, J., Rong, A., Yang, Z. (2000) A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron & Steel Complex. European Journal of Operational Research, 124(2), 267-282.
9. Al-Omeer, M. A., Ahmed, Z. H. (2019, April) Comparative study of crossover operators for the MTSP. In 2019 International Conference on Computer and Information Sciences (ICCIS) (pp. 1-6). IEEE
10. Yuan, S., Skinner, B., Huang, S., Liu, D. (2013) A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms. European journal of operational research, 228(1), 72-82.
11. Necula, R., Breaban, M., Raschip, M. (2015, June) Performance evaluation of ant colony systems for the single-depot multiple traveling salesman problem. In International Conference on Hybrid Artificial Intelligence Systems (pp. 257-268). Springer, Cham.smns
12. Liang, G., Zhang, S., Huang, F., He, S. (2007) A Kind of Renewed Simulated Annealing Algorithm Solves 0-1 Knapsack Problem. JOURNAL OF GUANGXI UNIVERSITY FOR NATIONALITIES(Natural Science Edition), 13(3): 91-93.
Data Availability
The datasets used and/or analyzed during the current study will be available from the authors upon reasonable request.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License. Authors who publish this series agree to the following terms:
1. Authors retain copyright and grant the series right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this series.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the series'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 series.
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 Open Access Instruction).
- Volume Title
- Proceedings of the 2nd International Conference on Computing Innovation and Applied Physics
- ISBN (Print)
- 978-1-83558-201-5
- ISBN (Online)
- 978-1-83558-202-2
- Published Date
- 08 December 2023
- Series
- Theoretical and Natural Science
- ISSN (Print)
- 2753-8818
- ISSN (Online)
- 2753-8826
- DOI
- 10.54254/2753-8818/18/20230321
- Copyright
- 08 December 2023
- Open Access
- This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited