An Ant Colony Algorithm with Dynamic Cities Allocation for Solving Competitive Travelling Salesmen Problem

Abstract

: In this paper, 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 payoff 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 five 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