sas 16(7): e2

Research Article

A Population Based ACO Algorithm for the Combined Tours TSP Problem

Download1013 downloads
  • @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
Martin Clauss1, Lydia Lotzmann2, Martin Middendorf2,*
  • 1: Fraunhofer FKIE
  • 2: University of Leipzig
*Contact email: middendorf@informatik.uni-leipzig.de

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.