A novel method for multiple depot and open paths, Multiple Traveling Salesmen Problem

Travelling Salesman Problem (TSP) is a typical combinatorial optimization problem. Multiple Travelling Salesmen Problem (MTSP) is a generalization of the TSP, and seems more appropriate for real-life application. Although there exists a great mount of literature for solving TSP, the research on MTSP is limited. This paper proposes a new method which is based on the knowledge of Graph Theory to solve a heterogeneity of MTSP with multiple depots and open paths (marked as mdop). A simple model SModel is proposed to implement the mdop by transforming a complicate graph into a simplified graph with a small number of edges. During the operation of generating SModel, high weighted edges are removed preferentially as possible. Since mdop is implemented based on the SModel, it can be guaranteed that the final result is superior. By the experimental results, it is shown that the new solution is efficient.