Clustering-Based Optimisation of Multiple Traveling Salesman Problem

Abstract

The TSP is the problem to find the shortest path in a graph visiting every nodes exactly once and returning to the start node. The TSP is shown to be an NP-hard problem. To provide an acceptable solution for real life problems, the TSP are usually solved with some heuristic optimization algorithms. The paper proposes a clustering-based problem decomposition algorithm to form the global route with merging of best local routes. Based on our test results, The proposed method can improve the efficiency of the standard heuristic methods for the TSP and MTSP problems.