ABSTRACT
In this talk we will focus on an ongoing project on approximation algorithms
for the Euclidean Traveling Salesman Problems (TSP). Given $n$ points and
the distances between them, the aim is to construct a tour that visits
each point exactly once and has the minimum total cost/distance
(the total cost of a tour is the sum of the distances defined by each pair
of points from that tour). The Euclidean version of the TSP, in which the
distances between the objects (points or cities) are distances in a
two-dimensional Euclidean space, is strongly NP-hard. However,
compared to the general setting, the Euclidean version is still more treatable since
it naturally allows to employ simple geometric tolls in the solution process, so
that a ``blind'' enumeration of all feasible tours can be replaced by a more
rational and transparent kind of selection of reasonable tours. Our method for
solving Euclidean TSP initially, at phase 1 constructs a girding polygon, a boundary
that includes all the given points. The convex boundary (hull) of the polygon consisting
of its edges already defines a partial tour, which is optimal for the set of
nodes that this boundary contains. The insertion heuristic of
Phase 2 augments iteratively the partial tour of Phase 1 to a complete feasible
tour using the cheapest insertion strategy: iteratively, current partial tour is
augmented with a new point, one yielding the minimal increase in the cost. The tour improvement heuristic of Phase 3 improves the tour of Phase 2 using some local
optimality conditions. Thanks to a simple geometry in decision-taking process
at Phases 2 and 3, our algorithm is extremely fast and requires a little computer
memory, whereas the quality of the
delivered solutions is comparable with that of the state-of-the-art algorithms.
Currently we are working on another approximation algorithm for the Euclidean TSP
which also starts with the girding polygon. Iteratively, special kind of
inner and outer convex boundaries (convex hulls) that include subsets of points
are constructed. Each convex hull defines an optimal tour for the points of that
hull. Two successively generated convex hulls are unified into a partial feasible tour
that covers the nodes from both boundaries. The algorithm halts when it constructs
a complete feasible tour.
In Multiprocessor TSP there is one distinguished point called the depot,
and $k$ salesman. Each salesman has to build its own tour that starts from the depot,
ends also in depot and visits only once one or more additional points. All
points are to be visited by a salesman. The aim is to minimize the total cost
of all $k$ tours. In the bounded version of Multiprocessor TSP lower and upper
bounds determine the minimum and maximum number of points in a tour, i.e.,
a feasible tour respects these restrictions. Our algorithm for the Bounded
Multiprocessor TSP initially
partitions the set of vertices into $k$ disjoint subsets at phase 1. Then,
at phase 2, it constructs the initial $k$ tours using the above mentioned
three-phase algorithm for TSP. The feasible solution of
phase 2 is further improved at phase 3: iteratively, a vertex from a tour
is moved from its current position to another specially determined position
within the same or another tour so that the resultant solution remains feasible.
The destiny vertex and its new position are selected so that the accomplished
rearrangement provides the maximum decrease of the current cost.
We obtained preliminary experimental results for the known 22
benchmark instances. The approximation rate provided by the proposed heuristic
is comparable to the state of the art results but it requires considerably
less memory and CPU time.