THESIS
2019
xi, 66 pages : illustrations (some color) ; 30 cm
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 invol...[
Read more ]
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 c
s and a cost of time c
t to covering all the cities. Given
certain computational power, we can calculate an optimal number m
* depending on the
number of cities n, c
s and c
t. 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.
Post a Comment