A Population Based ACO Algorithm for the Combined Tours TSP Problem

In this paper we apply a Population based Ant Colony Optimization(PACO) algorithm for solving the following new version of the Traveling Salesperson problem that is called the Combined Tours TSP (CT-TSP). Given are a set of cities, for each pair of cities a cost function and an integer k. The aim is to find a set of k (cyclic) tours, i.e., each city is contained exactly once in each tour and each tour returns to its origin city, which have minimum total costs. In this paper the case of finding two tours is studied where the costs of one tour depends on the other tour. Each pair of cities has a distance and a weight which influence the costs of the tours. The weight is used to define if it is advantageous or disadvantageous when the corresponding pair of cities is contained, i.e., neighbouring, in both tours. Different heuristics that the ants of the PACO use for the construction of the tours are compared experimentally. One result is that it is (often) advantageous when the heuristic for the second tour is different from the heuristic for the first tour such that the former heuristic uses knowledge about the first tour.