Improving the Performance of Multi-start Search on the Traveling Salesman Problem - Developing Concepts in Applied Intelligence - page 79

algorithm performs relative
random algorithm performe
its poor performance on the
to be less than the greedy a
of the input graph.

ely poorly regardless the structure of the input graph. T
ed the best of the six algorithms on two of the data sets,
e non-planar graph data set brings its average performa
approaches, and indicates that it is sensitive to the struct

The
but
ance
ture

3.2 Construction Algorit hms and Tour Redundancy

The next set of experiments e
the construction algorithms
despite the structure of inpu
exploit the record keeping e
Figure 1a shows the average
with the greedy construction
identical, but the greedy-jum
1b, 1c, and 1d show the di
using Concorde, GRASP, a
normal distribution [10], w

examines the quality and redundancy associated with som
. Because the greedy algorithms perform among the b
ut graphs and due to the fact that the random restart does
efficiently, we perform this set of experiment only on th
e redundancy and tour qualities produced when running I
n algorithms. The average quality of all algorithms is ne
mp algorithm has far less redundancy than the others. Figu
stribution of solution quality for 400 random graphs sol
and GE. All the graphs show a distribution that is close
where Concorde has the best mean and lowest varian

me of
best
not
hem.
IHC
early
ures
lved
e to
nce.

a

b

c

d

Fig. 1 1. Average tour Quality and Redundancy.