1. Rules & Example-1
Travelling Salesman Problem Rule
A travelling salesman plans to visit n cities. He wishes to visit each city only once, and again arriving back to his home city from where he started. So that the total travelling distance is minimum.
If there are n cities, then there are (n - 1)! possible ways for his tour.
For example, if the number of cities to be visited is 4, then there are 3! = 6 different combination is possible.
Such type of problems can be solved by Hungarian method, branch and bound method, penalty method, nearest neighbor method.
Example
Find Solution of Travelling salesman problem (MIN case)
| Work\Job | 1 | 2 | 3 | 4 | | 1 | x | 4 | 9 | 5 | | 2 | 6 | x | 4 | 8 | | 3 | 9 | 4 | x | 9 | | 4 | 5 | 8 | 9 | x |
Solution:
The number of rows = 4 and columns = 4
| | `1` | `2` | `3` | `4` | | | `1` | M | 4 | 9 | 5 | | | `2` | 6 | M | 4 | 8 | | | `3` | 9 | 4 | M | 9 | | | `4` | 5 | 8 | 9 | M | | | | | | | | |
Step-1: Find out the each row minimum element and subtract it from that row
| | `1` | `2` | `3` | `4` | | | `1` | M M | 0 `0=4-4` | 5 `5=9-4` | 1 `1=5-4` | (-4) Minimum element of `1^(st)` row | | `2` | 2 `2=6-4` | M M | 0 `0=4-4` | 4 `4=8-4` | (-4) Minimum element of `2^(nd)` row | | `3` | 5 `5=9-4` | 0 `0=4-4` | M M | 5 `5=9-4` | (-4) Minimum element of `3^(rd)` row | | `4` | 0 `0=5-5` | 3 `3=8-5` | 4 `4=9-5` | M M | (-5) Minimum element of `4^(th)` row | | | | | | | |
Step-2: Find out the each column minimum element and subtract it from that column.
| | `1` | `2` | `3` | `4` | | | `1` | M M | 0 `0=0-0` | 5 `5=5-0` | 0 `0=1-1` | | | `2` | 2 `2=2-0` | M M | 0 `0=0-0` | 3 `3=4-1` | | | `3` | 5 `5=5-0` | 0 `0=0-0` | M M | 4 `4=5-1` | | | `4` | 0 `0=0-0` | 3 `3=3-0` | 4 `4=4-0` | M M | | | | (-0) Minimum element of `1^(st)` column | (-0) Minimum element of `2^(nd)` column | (-0) Minimum element of `3^(rd)` column | (-1) Minimum element of `4^(th)` column | |
Iteration-1 of steps 3 to 6
Step-3: Make assignment in the opporunity cost tablea. Identify rows with exactly one unmarked 0. Make an assignmment to this single 0 by make a square ( [0] ) around it and cross off all other 0 in the same column. b. Identify columns with exactly one unmarked 0. Make an assignmment to this single 0 by make a square ( [0] ) around it and cross off all other 0 in the same rows. c. If a row and/or column has two or more unmarked 0 and one cannot be chosen by inspection, then choose the cell arbitarily. d. Continue this process until all 0 in rows/columns are either assigned or cross off(  ).
Step-3: Make assignment in the opporunity cost table
(1) Rowwise cell `(2,3)` is assigned
(2) Rowwise cell `(3,2)` is assigned, so columnwise cell `(1,2)` crossed off.
(3) Rowwise cell `(4,1)` is assigned
(4) Columnwise cell `(1,4)` is assigned
Rowwise & columnwise assignment shown in table
| | `1` | `2` | `3` | `4` | | | `1` | M | 0 Columnwise `(1,2)` crossed off because
(2) Rowwise cell `(3,2)` is assigned | 5 | [0] (4) Columnwise cell `(1,4)` is assigned | | | `2` | 2 | M | [0] (1) Rowwise cell `(2,3)` is assigned | 3 | | | `3` | 5 | [0] (2) Rowwise cell `(3,2)` is assigned
so columnwise cell `(1,2)` crossed off. | M | 4 | | | `4` | [0] (3) Rowwise cell `(4,1)` is assigned | 3 | 4 | M | | | | | | | | |
Step-4: Number of assignments = 4, number of rows = 4
The solution gives the sequence : `1->4,4->1`
The above solution is not a solution to the travelling salesman problem as he visits each city only once.
Iteration-2 of steps 3 to 6
The next best solution can be obtained by bringing the minimum non-zero element, i.e., 2 into the solution.
The cost 2 occurs at 1 places. We will consider all the cases separately until the acceptable solution is obtained.
Case: 1 of 1 for minimum non-zero element 2
Make the assignment in the cell `(2,1)` and repeat Step-3.
Step-3: Make assignment in the opporunity cost table
(1) Rowwise cell `(2,1)` is assigned, so columnwise cell `(4,1)`,`(2,3)` crossed off.
(2) Rowwise cell `(3,2)` is assigned, so columnwise cell `(1,2)` crossed off.
(3) Columnwise cell `(1,4)` is assigned
Rowwise & columnwise assignment shown in table
| | `1` | `2` | `3` | `4` | | | `1` | M | 0 Columnwise `(1,2)` crossed off because
(2) Rowwise cell `(3,2)` is assigned | 5 | [0] (3) Columnwise cell `(1,4)` is assigned | | | `2` | [2] (1) Rowwise cell `(2,1)` is assigned
so columnwise cell `(4,1)`,`(2,3)` crossed off. | M | 0 Columnwise `(2,3)` crossed off because
(1) Rowwise cell `(2,1)` is assigned | 3 | | | `3` | 5 | [0] (2) Rowwise cell `(3,2)` is assigned
so columnwise cell `(1,2)` crossed off. | M | 4 | | | `4` | 0 Columnwise `(4,1)` crossed off because
(1) Rowwise cell `(2,1)` is assigned | 3 | 4 | M | | | | | | | | |
Step-4: Number of assignments = 3, number of rows = 4
Which is not equal, so solution is not optimal.
Step-5: Cover the 0 with minimum number of lines
(1) Mark(✓) row `4` since it has no assignment
(2) Mark(✓) column `1` since row `4` has 0 in this column
(3) Mark(✓) row `2` since column `1` has an assignment in this row `2`.
(4) Mark(✓) column `3` since row `2` has 0 in this column
(5) Since no other rows or columns can be marked, therefore draw straight lines through the unmarked rows `1,3` and marked columns `1,3`
Tick mark not allocated rows and allocated columns
| | `1` | `2` | `3` | `4` | | | `1` | M | 0 | 5 | [0] | | | `2` | [2] | M | 0 | 3 | ✓(3) (3) Mark(✓) row `2` since column `1` has an assignment in this row `2`. | | `3` | 5 | [0] | M | 4 | | | `4` | 0 | 3 | 4 | M | ✓(1) (1) Mark(✓) row `4` since it has no assignment | | | ✓
(2) (2) Mark(✓) column `1` since row `4` has 0 in this column | | ✓
(4) (4) Mark(✓) column `3` since row `2` has 0 in this column | | |
Step-6: Develop the new revised table by selecting the smallest element, among the cells not covered by any line (say k = 3)
Subtract k = 3 from every element in the cell not covered by a line.
Add k = 3 to every elment in the intersection cell of two lines.
| | `1` | `2` | `3` | `4` | | | `1` | M `M=M+3`
intersection cell of two lines | 0 cell covered by a line | 8 `8=5+3`
intersection cell of two lines | 0 cell covered by a line | | | `2` | 2 cell covered by a line | M `M=M-3`
cell not covered by a line | 0 cell covered by a line | 0 `0=3-3`
cell not covered by a line | | | `3` | 8 `8=5+3`
intersection cell of two lines | 0 cell covered by a line | M `M=M+3`
intersection cell of two lines | 4 cell covered by a line | | | `4` | 0 cell covered by a line | 0 `0=3-3`
cell not covered by a line | 4 cell covered by a line | M `M=M-3`
cell not covered by a line | | | | | | | | |
Repeat steps 3 to 6 until an optimal solution is arrived.
Iteration-3 of steps 3 to 6
Step-3: Make assignment in the opporunity cost table
(1) Rowwise cell `(3,2)` is assigned, so columnwise cell `(1,2)`,`(4,2)` crossed off.
(2) Rowwise cell `(4,1)` is assigned, so columnwise cell `(2,1)` crossed off.
(3) Columnwise cell `(2,3)` is assigned, so rowwise cell `(2,4)` crossed off.
(4) Columnwise cell `(1,4)` is assigned
Rowwise & columnwise assignment shown in table
| | `1` | `2` | `3` | `4` | | | `1` | M | 0 Columnwise `(1,2)` crossed off because
(1) Rowwise cell `(3,2)` is assigned | 8 | [0] (4) Columnwise cell `(1,4)` is assigned | | | `2` | 2 Columnwise `(2,1)` crossed off because
(2) Rowwise cell `(4,1)` is assigned | M | [0] (3) Columnwise cell `(2,3)` is assigned
so rowwise cell `(2,4)` crossed off. | 0 Rowwise `(2,4)` crossed off because
(3) Columnwise cell `(2,3)` is assigned | | | `3` | 8 | [0] (1) Rowwise cell `(3,2)` is assigned
so columnwise cell `(1,2)`,`(4,2)` crossed off. | M | 4 | | | `4` | [0] (2) Rowwise cell `(4,1)` is assigned
so columnwise cell `(2,1)` crossed off. | 0 Columnwise `(4,2)` crossed off because
(1) Rowwise cell `(3,2)` is assigned | 4 | M | | | | | | | | |
Step-4: Number of assignments = 4, number of rows = 4
The solution gives the sequence : `1->4,4->1`
The above solution is not a solution to the travelling salesman problem as he visits each city only once.
Iteration-4 of steps 3 to 6
The next best solution can be obtained by bringing the minimum non-zero element, i.e., 4 into the solution.
The cost 4 occurs at 2 places. We will consider all the cases separately until the acceptable solution is obtained.
Case: 1 of 2 for minimum non-zero element 4
Make the assignment in the cell `(3,4)` and repeat Step-3.
Step-3: Make assignment in the opporunity cost table
(1) Rowwise cell `(3,4)` is assigned, so columnwise cell `(1,4)`,`(2,4)`,`(3,2)` crossed off.
(2) Rowwise cell `(1,2)` is assigned, so columnwise cell `(4,2)` crossed off.
(3) Rowwise cell `(2,3)` is assigned, so columnwise cell `(4,3)` crossed off.
(4) Rowwise cell `(4,1)` is assigned, so columnwise cell `(2,1)` crossed off.
Rowwise & columnwise assignment shown in table
| | `1` | `2` | `3` | `4` | | | `1` | M | [0] (2) Rowwise cell `(1,2)` is assigned
so columnwise cell `(4,2)` crossed off. | 8 | 0 Columnwise `(1,4)` crossed off because
(1) Rowwise cell `(3,4)` is assigned | | | `2` | 2 Columnwise `(2,1)` crossed off because
(4) Rowwise cell `(4,1)` is assigned | M | [0] (3) Rowwise cell `(2,3)` is assigned
so columnwise cell `(4,3)` crossed off. | 0 Columnwise `(2,4)` crossed off because
(1) Rowwise cell `(3,4)` is assigned | | | `3` | 8 | 0 Columnwise `(3,2)` crossed off because
(1) Rowwise cell `(3,4)` is assigned | M | [4] (1) Rowwise cell `(3,4)` is assigned
so columnwise cell `(1,4)`,`(2,4)`,`(3,2)` crossed off. | | | `4` | [0] (4) Rowwise cell `(4,1)` is assigned
so columnwise cell `(2,1)` crossed off. | 0 Columnwise `(4,2)` crossed off because
(2) Rowwise cell `(1,2)` is assigned | 4 Columnwise `(4,3)` crossed off because
(3) Rowwise cell `(2,3)` is assigned | M | | | | | | | | |
Step-4: Number of assignments = 4, number of rows = 4
The solution gives the sequence : `1->2,2->3,3->4,4->1`
So solution is optimal
Optimal assignments are
| | `1` | `2` | `3` | `4` | | | `1` | M Original cost M | [0] Original cost 4 | 8 Original cost 9 | 0 Original cost 5 | | | `2` | 2 Original cost 6 | M Original cost M | [0] Original cost 4 | 0 Original cost 8 | | | `3` | 8 Original cost 9 | 0 Original cost 4 | M Original cost M | [4] Original cost 9 | | | `4` | [0] Original cost 5 | 0 Original cost 8 | 4 Original cost 9 | M Original cost M | | | | | | | | |
Optimal solution is
| Work | Job | Cost | | `1` | `2` | 4 | | `2` | `3` | 4 | | `3` | `4` | 9 | | `4` | `1` | 5 | | | Total | 22 |
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
|
