To search, Click below search items. |
| All Published Papers Search Service |
|
|
|
Title |
Solving the Travelling Salesman Problem Using an Ant Colony System Algorithm |
|
Author |
Zakir Hussain Ahmed, Majid Yousefikhoshbakht, Abdul Khader Jilani Saudagar, and Shakir Khan |
| Citation |
Vol. 23 No. 2 pp. 55-64 |
|
Abstract |
The travelling salesman problem (TSP) is an important combinatorial optimization problem that is used in several engineering science branches and has drawn interest to several researchers and scientists. In this problem, a salesman from an arbitrary node, called the warehouse, starts moving and returns to the warehouse after visiting n clients, given that each client is visited only once. The objective in this problem is to find the route with the least cost to the salesman. In this study, a meta-based ant colony system algorithm (ACSA) is suggested to find solution to the TSP that does not use local pheromone update. This algorithm uses the global pheromone update and new heuristic information. Further, pheromone evaporation coefficients are used in search space of the problem as diversification. This modification allows the algorithm to escape local optimization points as much as possible. In addition, 3-opt local search is used as an intensification mechanism for more quality. The effectiveness of the suggested algorithm is assessed on a several standard problem instances. The results show the power of the suggested algorithm which could find quality solutions with a small gap, between obtained solution and optimal solution, of 1%. Additionally, the results in contrast with other algorithms show the appropriate quality of competitiveness of our proposed ACSA. |
|
Keywords |
Travelling Salesman Problem; Ant Colony System Algorithm; Global Updating; NP-hard Problems |
|
URL |
