Research Article
A Population Based ACO Algorithm for the Combined Tours TSP Problem
@ARTICLE{10.4108/eai.3-12-2015.2262573, author={Martin Clauss and Lydia Lotzmann and Martin Middendorf}, title={A Population Based ACO Algorithm for the Combined Tours TSP Problem}, journal={EAI Endorsed Transactions on Self-Adaptive Systems}, volume={2}, number={7}, publisher={ACM}, journal_a={SAS}, year={2016}, month={5}, keywords={ant colony optimization, population based aco, traveling salesperson problem, metaheuristic}, doi={10.4108/eai.3-12-2015.2262573} }- Martin Clauss
Lydia Lotzmann
Martin Middendorf
Year: 2016
A Population Based ACO Algorithm for the Combined Tours TSP Problem
SAS
EAI
DOI: 10.4108/eai.3-12-2015.2262573
Abstract
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.
Copyright © 2015 M. Middendorf et al., licensed to EAI. This is an open access article distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/3.0/), which permits unlimited use, distribution and reproduction in any medium so long as the original work is properly cited.
