Information Technology Reference
In-Depth Information
Bur26 History
1.3
10
7
1.2
10
7
1.1
10
7
1.
10
7
9.
10
6
8.
10
6
10
6
7.
0
50
100
150
200
Number of Generations
Fig. 3.18.
Sample output of the Bur26a problem
3.8
Traveling Salesman Problem
The third and final problem class to be experimented is the
Traveling Salesman Problem
(TSP). The TSP is a very well known optimisation problem. A traveling salesman has
a number,
N
, cities to visit. The sequence in which the salesperson visits different cities
is called a
tour
. A tour is such that every city on the list is visited only once, except that
the salesperson returns to the city from which it started. The objective to is minimise
the total distance the salesperson travels, among all the tours that satisfy the criterion.
Several mathematical formulations exist for the TSP. One approach is to let
x
ij
be 1
if city
j
is visited immediately after
i
, and be 0 if otherwise [24, 25]. The formulation of
TSP is given in Equations 3.17 to 3.20.
N
i
=1
N
j
=1
c
ij
•
x
ij
min
(3.17)
Each city is left after visiting subject to
N
j
=1
x
ij
= 1;
∀
i
(3.18)
Ensures that each city is visited
N
i
=1
x
ij
= 1;
∀
j
(3.19)
No subtours
x
ij
= 0
or
1
(3.20)
Search WWH ::
Custom Search