2. Example-2
Find Solution of Travelling salesman problem using diagonal completion method (MIN case)
Work\Job | A | B | C | D | E | A | x | 2 | 5 | 7 | 1 | B | 6 | x | 3 | 8 | 2 | C | 8 | 7 | x | 4 | 7 | D | 12 | 4 | 6 | x | 5 | E | 1 | 3 | 2 | 8 | x |
Solution: The number of rows = 5 and columns = 5
| `A` | `B` | `C` | `D` | `E` | | `A` | M | 2 | 5 | 7 | 1 | | `B` | 6 | M | 3 | 8 | 2 | | `C` | 8 | 7 | M | 4 | 7 | | `D` | 12 | 4 | 6 | M | 5 | | `E` | 1 | 3 | 2 | 8 | M | | | | | | | | |
Step-1: Find out the each row minimum element and subtract it from that row
| `1` | `2` | `3` | `4` | `5` | | `1` | M | 1 | 4 | 6 | 0 | (-1) | `2` | 4 | M | 1 | 6 | 0 | (-2) | `3` | 4 | 3 | M | 0 | 3 | (-4) | `4` | 8 | 0 | 2 | M | 1 | (-4) | `5` | 0 | 2 | 1 | 7 | M | (-1) | | | | | | | |
Step-2: Find out the each column minimum element and subtract it from that column.
| `1` | `2` | `3` | `4` | `5` | | `1` | M | 1 | 3 | 6 | 0 | | `2` | 4 | M | 0 | 6 | 0 | | `3` | 4 | 3 | M | 0 | 3 | | `4` | 8 | 0 | 1 | M | 1 | | `5` | 0 | 2 | 0 | 7 | M | | | (-0) | (-0) | (-1) | (-0) | (-0) | |
Step-3: Calculate the penalty of all 0's (penalty = minimum element of that row + minimum element of that column.)
| `1` | `2` | `3` | `4` | `5` | | `1` | `M` | `1` | `3` | `6` | `0^(color{red}{(1)})` | | `2` | `4` | `M` | `0^(color{red}{(0)})` | `6` | `0^(color{red}{(0)})` | | `3` | `4` | `3` | `M` | `0^(color{red}{(9)})` | `3` | | `4` | `8` | `0^(color{red}{(2)})` | `1` | `M` | `1` | | `5` | `0^(color{red}{(4)})` | `2` | `0^(color{red}{(0)})` | `7` | `M` | | | | | | | | |
Step-4: List the penalties `P(i,j)` in descending order by value.
`P(3,4)=9`
`P(5,1)=4`
`P(4,2)=2`
`P(1,5)=1`
`P(2,3)=0`
`P(2,5)=0`
`P(5,3)=0`
Step-5: The links `(3,4),(5,1),(4,2),(2,3)` are selected for inclusion in the feasible partial tour.
Step-6: Feasible partial tour contains the following chains `3->4->2,5->1`
`(2,3),(1,5)` can not be selected, because they are the closing links and create prohibited subtours.
Step-7: The new submatrix is :
Repeat from step-1 to step-7 Step-1: Find out the each row minimum element and subtract it from that row
| `3` | `5` | | `2` | M | 0 | (-2) | `1` | 0 | M | (-5) | | | | |
Step-3: Calculate the penalty of all 0's (penalty = minimum element of that row + minimum element of that column.)
| `3` | `5` | | `2` | `M` | `0^(color{red}{(0)})` | | `1` | `0^(color{red}{(0)})` | `M` | | | | | |
Step-4: List the penalties `P(i,j)` in descending order by value.
`P(2,5)=0`
`P(1,3)=0`
Step-5: The links `(2,5),(1,3)` are selected for inclusion in the feasible partial tour.
Step-6: Feasible partial tour contains the following chains `3->4->2->5->1->3`
So our final path is `C->D->B->E->A->C`
and total distance is `4+4+2+1+5=16`
This material is intended as a summary. Use your textbook for detail explanation. Any bug, improvement, feedback then
|