Information Technology Reference
In-Depth Information
Table 3.41.
City distance matrix
City
AB
C
D
E
2
3
2
4
D
1
5
1
C
2
3
B
1
No subtours mean that there is no need to return to a city before visiting all the
other cities. The objective function accumulates time as you go from city
i
to
j
. Con-
straint 3.18 ensures that the salesperson leaves each city. Constraint 3.19 ensures that
the salesperson enters each city. A subtour occurs when the salesperson returns to a city
prior to visiting all other cities. Restriction 3.20 enables the TSP formulation differs
from the Linear Assignment Problem programming (LAP) formulation.
3.8.1
Traveling Salesman Problem Example
Assume there are five cities
, for a traveling salesman to visit as shown
in Fig 3.19. The distance between each city is labelled in the vertex.
In order to understand TSP, assume a tour, where a salesman travels through all the
cities and returns eventually to the original city. Such a tour can be given as
A
{
A
,
B
,
C
,
D
,
E
}
→
B
→
C
→
D
→
E
→
A
. The graphical representation for such a tour is given in Fig 3.20.
B
1
3
2
A
C
3
5
2
1
2
1
E
D
4
Fig. 3.19.
TSP distance node graph
Search WWH ::
Custom Search