Enhanced Approaches to Solving the Multiple Traveling Salesman Problem

Abstract

Two modifications to the solution methods for the Multiple Traveling Salesman Problem (MTSP) will be presented with a focus on their potential applications to UAV swarm route planning. The scenario discussed in this paper involves a set of randomly distributed cities and a specified number of UAVs. To solve the MTSP, cities are divided into clusters based on their location in space, typically using K-means clustering, and each UAV is assigned to a cluster. Next the Traveling Salesman Problem (TSP) is solved for each cluster using a constructive heuristic called the 2-Opt to determine the shortest route through the set of cities. An optimal solution to the problem is one that minimizes the longest route of any UAV. The first modification that will be presented is a modification to the 2-Opt which improves computation time by beginning with an initial route determined using the nearest neighbor algorithm, rather than a route determined at random. The second modification is a new clustering method that builds upon K-means clustering to reduce the maximum tour distance of any cluster. These results could lead to large reductions in UAV mission times.