The Traveling Salesman Problem (TSP) is a classic combinatorial optimization problem that has significant implications in various fields, including logistics, routing, and scheduling. However, the problem becomes increasingly difficult as the number of cities increases, leading to the need for efficient and scalable solution approaches. This paper presents a novel hybrid metaheuristic algorithm designed to solve large-scale TSPs. The proposed algorithm combines the strengths of two distinct metaheuristic techniques—Genetic Algorithms (GAs) and Simulated Annealing (SA)—to exploit their complementary advantages in search space exploration and exploitation. The Genetic Algorithm is responsible for the initialization and mutation stages, while the Simulated Annealing is applied to refine the solutions through local search and global optimization. The hybrid metaheuristic is tested on a variety of benchmark instances with up to 1000 cities and demonstrates superior performance compared to the individual algorithms. The computational experiments demonstrate that the proposed hybrid algorithm can effectively reduce the running time and improve solution quality for large-scale TSPs, which is crucial for practical applications.
Anderson, S. Hybrid Metaheuristic Algorithms for Solving Large-Scale Traveling Salesman Problems. Transactions on Applied Soft Computing, 2022, 4, 30. https://doi.org/10.69610/j.tasc.20220616
AMA Style
Anderson S. Hybrid Metaheuristic Algorithms for Solving Large-Scale Traveling Salesman Problems. Transactions on Applied Soft Computing; 2022, 4(2):30. https://doi.org/10.69610/j.tasc.20220616
Chicago/Turabian Style
Anderson, Sophia 2022. "Hybrid Metaheuristic Algorithms for Solving Large-Scale Traveling Salesman Problems" Transactions on Applied Soft Computing 4, no.2:30. https://doi.org/10.69610/j.tasc.20220616
APA style
Anderson, S. (2022). Hybrid Metaheuristic Algorithms for Solving Large-Scale Traveling Salesman Problems. Transactions on Applied Soft Computing, 4(2), 30. https://doi.org/10.69610/j.tasc.20220616
Article Metrics
Article Access Statistics
References
Burbules, N. C., & Callister, T. A. (2000). Watch IT: The Risks and Promises of Information Technologies for Education. Westview Press.
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. University of Michigan Press.
Eiben, A. E., & Smith, J. E. (2003). Evolutionary Computation: A New Combinatorial Optimization Technique. Kluwer Academic Publishers.
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671-680.
Das, S., & Bhattacharyya, D. (2006). Solving the Traveling Salesman Problem Using Simulated Annealing. In International Conference on Soft Computing and Intelligent Systems (pp. 1-5). Springer.
Merkle, D., & Middendorf, M. (2001). A Genetic Simulated Annealing Algorithm for the Traveling Salesman Problem. Journal of Heuristics, 7(1), 1-20.
Li, Y., & Zhang, J. (2007). A Hybrid Genetic Simulated Annealing with Ant Colony Optimization for solving the Traveling Salesman Problem. In International Conference on Artificial Intelligence (pp. 1-4). IEEE.
Yen, G. G., Chen, S. C., & Liu, C. H. (2007). A hybrid Genetic Algorithm and Tabu Search approach for solving the large-scale traveling salesman problem. Expert Systems with Applications, 32(4), 1105-1113.
Li, Y., & Zhang, J. (2008). A Hybrid Simulated Annealing Algorithm for solving the large-scale traveling salesman problem. In International Conference on Artificial Intelligence and Computational Intelligence (pp. 540-543). IEEE.