Information Technology Reference
In-Depth Information
N
i
=1
x
ij
= 1;
∀
i
(2.5)
No subtours
x
ij
= 0or1
(2.6)
No
subtours
mean that there is no need to return to a city prior to visiting all other
cities. The objective function accumulates time as we go from city
i
to
j
. Constraint 2.4
ensures that we leave each city. Constraint 2.5 ensures that we visit (enter) each city.
A subtour occurs when we return to a city prior to visiting all other cities. Restriction
6.6 enables the TSP-formulation, differ from a linear assignment programming (LAP)
formulation. Unfortunately, the non-subtour constraint significantly complicates model
solution. One reasonable construction procedure for solving TSP is the closest insertion
algorithm. This is now discussed.
The Traveling Salesman Problem (TSP) is a fairly universal, strict-sense combi-
natorial problem into which many other
strict-sense
combinatorial problems can be
transformed. Consequently, many findings about DE
s performance on the TSP can be
extrapolated to other
strict-sense
combinatorial problems.
2.2.2.1 TSP Using Closest Insertion Algorithm
The closest insertion algorithm starts by selecting any city. We then proceed through
N
1 stages, adding a new city to the sequence at each stage. Thus a partial sequence
is always maintained, and the sequence grows by one city each stage. At each stage
we select the city from those currently unassigned that is closest to any city in the
partial sequence. We add the city to the location that causes the smallest increase in the
tour length. The closest insertion algorithm can be shown to produce a solution with a
cost no worse than twice the optimum when the cost matrix is symmetric and satisfies
the triangle inequality. In fact, the closest insertion algorithm may be a useful seed-
solution for combinatorial search methods when large problems are solved. Symmetric
implies
c
ij
=
c
ji
where
c
ij
is the cost to go from city
i
directly to city
j
. Unfortunately,
symmetry need not exist in our changeover problem. Normally, the triangular inequality
(
c
ij
≤
−
c
ik
+
c
kj
) will be satisfied, but this alone does not suffice to ensure the construction
of a good solution. We may also try repeated application of the algorithm choosing a
different starting city each time and then choose the best sequence found. Of course,
this increases our workload by a factor of
N
. Alternatively, a different starting city may
be chosen randomly for a specific number of times, less than the total number of cities.
This option is preferred for large problem instances.
We now state the algorithm formally. Let
S
a
be the set of available (unassigned) cities
at any stage.
S
p
will be the partial sequence in existence at any stage and is denoted
S
p
=
{
s
1
,
s
2
,...,
s
n
}
, implying that city
s
2
immediately follows
s
1
. For each unassigned
city
j
,weuse
r
(
j
) to keep track of the city in the partial sequence that is closest to
j
.We
store
r
(
j
) only to avoid repeating calculations at each stage. Last, bracketed subscripts
[
i
] refer to the
i
th
city in the current partial sequence. The steps involved are:
Search WWH ::
Custom Search