Authors : Mohannad Al-Kubaisi, Belal Al-Khateeb and Muamer N. Mohammed
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.
Mohannad Al-Kubaisi, Belal Al-Khateeb and Muamer N. Mohammed, 2018. An Ant Colony Algorithm with Dynamic Cities Allocation for Solving Competitive Travelling Salesmen Problem. Journal of Engineering and Applied Sciences, 13: 1400-1406.