A New Strategy to Solve the Traveling Salesman Problem with a Multi-Agent System

Abstract
The large-scale traveling salesman problem is difficult to solve especially when the computing resources are limited. In this thesis, we propose a good strategy to solve it with multiple traveling salesmen. There are two steps in the strategy. One is to divide all the cities into m groups. The other is to solve the traveling salesman problem using a multi-agent system with m salesmen, which means each salesman is assigned to find the shortest path covering all the cities in the assigned group. To demonstrate our strategy is effective and useful when there are only finite computing sources, we define a new problem generalized from traveling salesman problem. In this problem, the aim is to find out the optimal number m of salesmen that costs least. We define a cost function involving the cost of hiring additional salesman cs and a cost of time ct to covering all the cities. Given certain computational power, we can calculate an optimal number m depending on the number of cities n, cs and ct. We test this strategy with finite computing resources on a random configuration of points on a plain and a real data set in TSPLIB and find a good solution efficiently.