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.