Solving Multiple Traveling SalesmanProblem by Clustering and PSO

Multiple Traveling Salesman Problem (mTSP) is a classical problem which is a generalization of the traveling salesman problem (TSP), in which more than one salesman usually used to solving the problems in combinational ptimization. It can be generalized to wide variety of real-lifeproblem such as routing and scheduling. mTSP is a NPComplete problem and it should to minimize the traveled tourby all the salesmen, so it is not possible to use deterministic algorithms to solve it and often solved by heuristics methods. Inthe proposed algorithm, a two-level optimization problem have been used to solve the problem, where at the first stage a robustclustering algorithm used to divide the cities to k group for distributing the work identically among the salesman, and atthe second stage PSO algorithm is used to find the optimum length tour for each of the groups. Performance of theproposed algorithm has been compared with other mTSP improved algorithms on standard dataset and the experimentalresults show that it can outperform the other improved methods

کلیدواژه ها:

Multiple Traveling Salesman Problem ، Clustering ، Particle Swarm Optimization