Application of ant colony optimization to solving multiple travelling salesman problem without depot

O. Tymchuk, Y. Protsenko, A. Paramonov

The paper presents the algorithm for solving the NP-complete problem of multiple travelling salesman problem without depot, which is a generalization of the “standard” traveling salesman problem and consists in finding disjoint closed routes on the graph, with each vertex belonging to exactly one route, and the cost of the longest path should be minimal. The proposed algorithm is based on metaheuristics of an ant colony - ants, using various types of pheromones, try to optimally split the graph into clusters using a pheromone of the first type, and optimize the route inside each cluster using a pheromone of the second type. Dividing the ant route into clusters is ensured by introducing two types of ant movement between the vertices of the graph: “foot transitions” and “jumps”. Being at a certain vertex of the graph, the ant can continue its path using the “foot transition”, or close it into a loop and proceed to the formation of a new cluster using the “jump”. The balance between the two types of phero-mones is used as a heuristic choice of which type of movement the ant uses. The description of the proposed algorithm in the paper is performed using pseudocode. The algorithm is tested on the data of locations of most populous cities of Ukraine. Tests show that the algorithm is able to find quite good suboptimal solutions for problems of small sizes (n ≤ 12). The algorithm dem-onstrates a way how to generalize ant colony optimization approach while keeping spirit of classic algorithm. It may be the basis for further systematization of ant colony optimization approach and even for development of generic algorithm of generation ACO algorithm for given combinatorial optimization problem.

Keywords: the traveling salesmen problem, the multiple traveling salesmen problem without depot, ant colony optimization algorithm, ant colony optimization metaheuristic.