Comparison of Simulated Annealing and Ant Colony Optimization in Solving the Traveling Salesman Problem

The Traveling Salesman Problem (TSP) is a highly researched optimization issue in the fields of computer science and computational mathematics, as an optimal solution has yet to be found. This algorithmic issue requires finding the optimal route that visits each city in a given list exactly once while minimizing the total distance traveled. The route should also return to the starting location. This research aims to undertake a comparison study to assess and analyze the efficacy of two algorithms, namely Simulated Annealing (SA) and Ant Colony Optimization (ACO). Given that the TSP falls under the category of computing problems that are classified as NP-hard, our analysis will focus on both the time it takes to execute these algorithms and the shortest distance they compute. Based on the results obtained, it was determined that ACO is the optimal choice when optimizing for the shortest distance. In contrast, SA is preferable when considering pure execution time and complexity.

کلیدواژه ها:

Metaheuristic ، Optimization ، Combinatorial ، Traveling Salesman Problem ، TSP ، Simulated Annealing ، SA ، Ant Colony Optimization ، ACO