% formatted on 970304 by morris
\documentstyle[fleqn]{article}
\setcounter{page}{25}
\textheight 9.5in
\textwidth 5.75in
\voffset -1in
\hoffset -0.55in
%\documentclass[12pt,fleqn]{article}

\begin{document}

\begin{center}
\Large
Parallel Optimization for TSP \\

\vspace{0.7cm}
\large
Hai Xiang Lin and Kees Lemmens \\

\normalsize
\vspace{0.5cm}
Faculty of Technical Mathematics and Computer Science, \\
Delft University of Technology, 
2628 CD, Mekelweg 4, Delft, The Netherlands  \\
Tel: +31-15-2787229, Fax: +31-15-2787209,
e-mail: h.x.lin@twi.tudelft.nl
\end{center}

\section{Introduction}

The traveling salesman problem (TSP) is probably the most well-known 
member among the combinatorial optimization problems.
It tries to find a shortest (or most economical) path visiting a number
of cities exactly once with the same city as the starting and ending
point. The TSP has many practical applications in real life, such as
in vehicle routing, determining the best route for the pen movement
of a plotter, ordering-picking problem in warehouses, drilling of
printed circuit boards, etc.

\vskip 2truemm

The TSP is a very computation intensive problem. The number of feasible
solutions grows exponentially as $\frac{(n-1)!}{2}$ 
($n$ is the number of cities). It is an NP hard problem.
Therefore, for large $n$ it is unrealistic to find the optimum.
In practical applications, the determination of the optimum solutions
of TSP is seldom necessary. Usually one is satisfied with solutions that
is within a certain percentage of an optimum solution. So, in practice,
heuristics are used for finding a good approximation of the optimization
problem. 

\vskip 2truemm

However, for a TSP with a very large number of cities, the most
heuristics such as the well-known Lin-Kernighan heuristic with an $O(n^3)$
time complexity still require too much computer time. 
One way to speed up the optimization for TSP is parallel computation. 
In this paper we report a promising parallel algorithm and some results 
on finding good approximation for very large TSPs using parallel computers.

\section{A partitioning based parallel algorithm}

A good parallel algorithm must satisfy two properties: 1. the required 
computation can be subdivided into a large number of roughly independent
tasks; 2. only a small amount of data communication among the tasks is
required. 

\vskip 2truemm

We consider a divide and conquer method, which is based on the partitioning
heuristic proposed by Karp. First the $n$ cities into a number of sub-regions
in such a way that any two neighboring sub-regions have exactly one common 
city duplicated. Each sub-region is then a smaller TSP to be solved.
After an optimal solution (Hamiltonian cycle) has been computed for 
each sub-region, a larger (sub)optimal Hamiltonian cycle for two neighboring 
sub-regions can be obtained through combining the two Hamiltonian cycles. 
This combining procedure is performed repeatedly under a path
for the entire TSP has been obtained.

\vskip 2truemm

Karp has shown some nice theoretical analysis results on the accuracy of
the approximated solutions. The length of an approximated solution is 
within $O(t^{-0.5})$ percentage with respect to the optimum,
where $t$ is the number of cities in a subregion which is solved to the
optimum. But this is not very useful in practice. Because even for a 
10\% error we need to solve subproblems of size 100 to the optimum. 
The solution of each subregion may require hours, days or more on today's 
workstations, and there are $\frac{n}{100}$ subproblems to be solved.
So, in order to obtain an accurate approximation (say within a few percent
of the optimum), hybrid schemes should be applied by using
heuristics for the sub-regions and/or using heuristics for
improving the Hamiltonian cycle after the combining procedure.

\vskip 2truemm

We have used a hybrid scheme to implement a parallel optimizer for TSP.
After the partitioning, the smaller TSPs in the sub-regions 
can be solved in parallel without requiring communication. Communication
is required during the combining phase where two (smaller) Hamiltonian
cycles are merged into one Hamiltonian cycle. 

\vskip 2truemm

We have investigated several algorithms for computing the (sub)optimal
path for each sub-region. One of them is to use the branch and bound
method for each sub-region TSP. This results in an optimal path for each
sub-region. However, for a large number of cities per sub-region, other
heuristics such as Lin-Kernighan algorithm is preferred if the number
of cities per sub-region is large. The procedure of combining two 
sub-regions produces a path through connecting the duplicated common
city. This path can be further improved using heuristics. We have
implemented the two-way and the three-way exchange heuristics. Experimental
results show that a three-way exchange (what we called a 
disconnect-and-connect (DCC)) heuristic is very effective for improving
a path obtained via divide and conquer. 

\section{Parallel implementation}

We have implemented the hybrid scheme based on partitioning on a
distributed memory parallel computer. The first phase of solving the
sub-regions are simple to parallelize, since the sub-regions can be
computed independently from each other. However, the solution time for
the sub-regions may vary largely even though all sub-regions
have an equal number of cities, especially when Branch-and-Bound algorithm
is used. So, some dynamic load-balancing is necessary in order to
achieve a good parallel efficiency.

\vskip 2truemm

During the combining phase, the remaining number of Hamiltonian cycles 
to be merged is decreasing to eventually one single cycle. Therefore,
The improvement heuristic after combining two Hamiltonian cycles into
one cycle must be parallelized too. This is a difficult part of the
parallel algorithm which requires communication and synchronization,
so careful considerations must be made.
We have implemented a parallel version of the three-way exchange and 
Lin-Kernighan heuristic as improvement heuristics. 

\vskip 2truemm

Our parallel optimizer have been used to compute a number of very large
TSPs (varied from several hundreds to ten thousand cities). Some of these
problems are generated randomly and some are from the well-known TSPLIB. 
Results show that a near linear speedup is obtained. Depending on the
parameters (e.g. the maximum number of iterations in an improvement
heuristic), we can compute approximated solutions to the problems in 
a time between 1 and 20 minutes, while the most approximations are within
a few percentage of the optimum.
\end{document}


