An Effective Ant Colony Algorithm for the Traveling Salesman Problem

Journal of Advances in Computer Research

شناسنامه علمی شماره، دوره 7، شماره 3 - شماره پیاپی 25، آبان 2016، صفحه 77-91   

نویسندگان

Majid Yousefikhoshbakht^{* 1}؛ Azam Dolatnejad²

¹Young Researchers & Elite Club, Hamedan Branch, Islamic Azad University,Hamedan, Iran

²Young Researchers & Elite Club, Tehran North Branch, Islamic Azad University, Tehran, Iran

چکیده

The traveling salesman problem (TSP) is a well-known combinatorial optimization problem and holds a central place in logistics management. The TSP has received much attention because of its practical applications in industrial problems. Many exact, heuristic and metaheuristic approaches have been proposed to solve TSP in recent years. In this paper, a modified ant colony optimization (MACO) is presented which possesses a new strategy to update the increased pheromone, a candidate list and a mutation operation to solve the TSP. In addition, some local search algorithms are utilized as an effective criterion and only a global updating is used in order to increase pheromone on the edges of the best route. The proposed metaheuristic algorithm is tested on the well-known TSP instances involving 14 benchmark problems from 48 to 200 nodes. The computational results show that our algorithm is better than other meta-heuristic algorithms in terms of solution quality. Furthermore, the gap of the proposed algorithm stays on average almost 1% of the execution time and also the most best known solutions of the benchmark problems are found.

کلیدواژه‌ها

Traveling Salesman Problem؛ Ant Colony Optimization؛ Global Updating؛ NP-hard Problems