A Fast Algorithm for Euclidean Bounded Single-Depot Multiple Traveling Salesman Problem

The Multiple Traveling Salesman Problem (MTSP) is a combinatorial optimization problem that can model some real-life problems. There are given $n+1$ objects that are commonly referred to as cities, among which there is one distinct city called depot, and $k$ additional objects commonly referred to as salesman. Each salesman has to build its own tour that starts from the depot, ends also in depot and visits only once one or more other cities. Visiting city $j$ from city $i$ implies a cost $c_{ij}$. The cost of a tour is the sum of the individual costs of each pair of cities from that tour. The aim is to minimize the total cost of all $k$ tours. Here we consider the two-dimensional Euclidean version of the problem and impose lower and upper bounds on the minimum and maximum number of cities in a tour suggesting a 3-phase heuristic algorithm for that version. At the first phase the whole set of cities is partitioned into $k$ disjoint subsets, at the second phase a feasible tour for each of these subsets is constructed, and at phase 3 these feasible tours are iteratively improved. We report preliminary experimental results for the 22 benchmark instances. The approximation gap provided by the proposed heuristic is comparable to the state of the art results, whereas it is much faster than earlier known state-of-the-art algorithms.