1. 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 table
a. 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 |
