Travelling Salesman Problem
This humorously named problem refers to the following situation:
A travelling salesman, named Rover plans to visit each of n cities. He wishes to visit each city once and only once, arriving back to city from where he started. The distance between City i and City j is cij. What is the shortest tour Rover can take?
If there are n cities, there are (n - 1)! possible ways for his tour. For example, if the number of cities to be visited is 5, then there are 4! different combinations. Such type of problems can be solved by the assignment method.
Let cij be the distance (or cost or time) between City i to City j and
| xij = |  |
1 if a tour includes travelling from city i to city j (for i ≠ j) |
| 0 otherwise |
The following example will help you in understanding the travelling salesman problem of operation research.
Example: Travelling Salesman Problem
A travelling salesman, named Rolling Stone plans to visit five cities 1, 2, 3, 4 & 5. The travel time (in hours) between these cities is shown below:
| To | |||||
|---|---|---|---|---|---|
| From | 1 | 2 | 3 | 4 | 5 |
| 1 | ∞ | 5 | 8 | 4 | 5 |
| 2 | 5 | ∞ | 7 | 4 | 5 |
| 3 | 8 | 7 | ∞ | 8 | 6 |
| 4 | 4 | 4 | 8 | ∞ | 8 |
| 5 | 5 | 5 | 6 | 8 | ∞ |
How should Mr. Rolling Stone schedule his touring plan in order to minimize the total travel time, if he visits each city once a week?
Solution
After applying steps 1 to 3 of the Hungarian method, we get the following assignments.
Table
| To | |||||
|---|---|---|---|---|---|
| From | 1 | 2 | 3 | 4 | 5 |
| 1 | ∞ | 1 | 3 |  |
1 |
| 2 | 1 | ∞ | 2 |  |
1 |
| 3 | 2 | 1 | ∞ | 2 | |
| 4 | |
|
3 | ∞ | 4 |
| 5 | |
|
|
3 | ∞ |
Draw the minimum number of vertical and horizontal lines necessary to cover all the zeros in the reduced matrix.
Table
Select the smallest element from all the uncovered elements. Subtract this smallest element from all the uncovered elements and add it to the elements, which lie at the intersection of two lines. Thus, we obtain another reduced matrix for fresh assignment. Repeating step 3 on the reduced matrix, we get the following assignments.
Table
| To | |||||
|---|---|---|---|---|---|
| From | 1 | 2 | 3 | 4 | 5 |
| 1 | ∞ | |
2 | |
1 |
| 2 | |
∞ | 1 | |
1 |
| 3 | 1 | |
∞ | 2 | |
| 4 | |
|
3 | ∞ | 5 |
| 5 | |
|
|
4 | ∞ |
The above solution suggests that the salesman should go from city 1 to city 4, city 4 to city 2, and then city 2 to 1 (original starting point). The above solution is not a solution to the travelling salesman problem as he visits city 1 twice.
The next best solution can be obtained by bringing the minimum non-zero element, i.e., 1 into the solution. Please note that the value 1 occurs at four places. We will consider all the cases separately until the acceptable solution is obtained. To make the assignment in the cell (2, 3), delete the row & the column containing this cell so that no other assignment can be made in the second row and third column.
Now, make the assignments in the usual manner as shown in the following table.
Table
He starts from city 1 and goes to city 4; from city 4 to city 2; from city 2 to city 3; from city 3 to city 5; from city 5 to city 1.
Substituting values from original table:
4 + 7 + 6+ 4 + 5 = 26 hours.
