The traveling salesman problem, like many nonlinear optimization problems
with a large number of parameters, is typically solved using an approach that
utilizes randomness, rewards improved optimization, and allows for diversity in
possible solutions to reduce the chance of becoming stuck in a local minimum.
The model used in this case is a simulated annealing model, in which
perturbations are made to the salesman's path. Perturbations that improve the
optimization are automatically accepted, and perturbations that do not improve
the optimization are sometimes accepted at early stages in the optimization, but
less often accepted in later stages of the optimization. This can be thought of
as a "cooling" process, and indeed the parameter used to determine whether or
not to accept a perturbation that does not improve the optimization is called
the temperature. If one thinks of the optimization process as a simplex rolling
downward, a higher temperature would occasionally "shake things up", allowing a
simplex to pop out of a local minimum and possibly find a better global minimum.
Perturbations in this model can take one of many forms--a random
rearrangement of all cities, a random rearrangement of a few contiguous cities,
a swap of two random cities, a reversal of some number of contiguous cities--and
the optimization parameter in the model is the total length of the salesman's
The parallelization of this problem is not entirely trivial, as having 10
processes attempt 10 trials in parallel is not equivalent to having 1 process
calculate 100 trials. Each trial has the potential to improve the solution, but
if all processes improve by the same amount, having more processes participate
may or may not be helpful. The implementation that has been used in this problem
has P processes attempting N trials and then comparing to see who has the best
solution. Each process restarts using the best current known solution, and this
process is repeated M times.
This traveling salesman model is designed to run on a UNIX machine from a
command line, with X-Windows used for visualization. Parallelization of the code
has been done using MPI.