Joint Decision Making in Ant Colony Systems for Solving the Multiple Traveling Salesman Problem

The Multiple Traveling Salesman Problem (multiple-TSP) is a straightforward extension of the well-known Traveling Salesman Problem (TSP), in which more salesmen must visit a set of interconnected cities. Ant Colony Optimization (ACO) algorithms are designed to build sequentially the solutions, aspect which on multiple-TSP imposes new challenges. Compared to TSP which deals with one sample space - the set of cities (locations), multiple-TSP involves two sample spaces: the set of salesmen (agents) and the set of cities. Existing ACO algorithms addressing multiple-TSP are two-phase sampling procedures which, firstly, independently sample from the first set (the set of salesmen), and then conditionally sample from the second set. Our claim is that a joint sampling mechanism, which will exploit a joint probability space, is likely to lead to superior results. We validate our hypothesis by implementing five ACO-based algorithms to solve multiple-TSP: three of them are two-phase algorithms exploring various methods to sample from the salesmen space, while two of them implement the joint sampling scheme. The results are analyzed both in a single-objective manner that considers the minimization of the longest tour, and also from a bi-objective perspective that considers two conflicting objectives: 1) minimization of the total traveled distance and 2) work balancing – which amounts to minimizing the amplitude of the costs of individual tours.