Journal of Engineering and Applied Sciences
ISSN: Online 1818-7803ISSN: Print 1816-949x
Abstract
In this study, an Ant Colony Optimization (ACO) algorithm is presented to address the Competitive Traveling Salesman Problem (CTSP). In CTSP there are a number of salesmen who aim to visit a number of cities. A salesman receives a benefit by visiting the city that has never been visited before. The overall pay off to a salesman is the aggregation of benefit earned by visiting cities minus the cost of the trip (travelled distance). The relationship between salesmen is non-cooperative as each salesman is working to increase their own benefit by visiting the largest possible number of unvisited cities. As it is difficult to find an optimal solution for CTSP an ACO algorithm is proposed. Inspired by the idea of real ant colony in which ants leave pheromone trails when looking for food in order to guide other ants to the target (food). To determine the number of ants a number of simulations on every problem is conducted. We find that 5 ants for 20 city CTSP and 125 ants for 300 city CTSP are good choices because they lead to high quality solutions. In this approach, all the cities are available for all salesmen at all the times. Each salesman will only choose its next city (according to his strategy) from the list of available cities to visit. Tests are carried out to measure the performance of the proposed algorithm and the obtained results suggest that ACO is a promising method for CTSP, since, it provide high quality solutions.
How to cite this article:
Mohannad Al-Kubaisi, Belal Al-Khateeb and Muamer N. Mohammed. An Ant Colony Algorithm with Dynamic Cities Allocation for
Solving Competitive Travelling Salesmen Problem.
DOI: https://doi.org/10.36478/jeasci.2018.1400.1406
URL: https://www.makhillpublications.co/view-article/1816-949x/jeasci.2018.1400.1406