Tackling the Bi-criteria Facet of Multiple Traveling Salesman Problem with Ant Colony Systems

The single-depot multiple TSP (SD-MTSP) is a simple extension of the standard TSP, in which more than one salesman is allowed to visit the set of interconnected cities, such that each city is visited exactly once (by a single salesman) and the total cost of the traveled subtours is minimized. Although Ant Colony Systems (ACSs) are a natural choice for shortest-path problems, with TSP at its core, the application of ACS on this straightforward extension is not properly explored. The reasons may lie in the bi-criteria nature of the problem (shortest cost versus balanced subtours) and the lack of dedicated benchmarks exposing optimal solutions. This paper attempts at proposing and evaluating from a bi-criteria perspective several multi-objective ACSs to tackle SD-MTSP when two objectives need to be simultaneously optimized: minimizing the total cost of traveled subtours while achieving balanced subtours. Experiments are conducted towards investigating the efficiency of the algorithms in a multi-objective setting.