Find Solution of Travelling salesman problem using diagonal completion method (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 | 0 | 5 | 1 | (-4) |
| `2` | 2 | M | 0 | 4 | (-4) |
| `3` | 5 | 0 | M | 5 | (-4) |
| `4` | 0 | 3 | 4 | M | (-5) |
| | | | | | |
Step-2: Find out the each column minimum element and subtract it from that column.
| | `1` | `2` | `3` | `4` | |
| `1` | M | 0 | 5 | 0 | |
| `2` | 2 | M | 0 | 3 | |
| `3` | 5 | 0 | M | 4 | |
| `4` | 0 | 3 | 4 | M | |
| | (-0) | (-0) | (-0) | (-1) | |
Step-3: Calculate the penalty of all 0's (penalty = minimum element of that row + minimum element of that column.)
| | `1` | `2` | `3` | `4` | |
| `1` | `M` | `0^(color{red}{(0)})` | `5` | `0^(color{red}{(3)})` | |
| `2` | `2` | `M` | `0^(color{red}{(6)})` | `3` | |
| `3` | `5` | `0^(color{red}{(4)})` | `M` | `4` | |
| `4` | `0^(color{red}{(5)})` | `3` | `4` | `M` | |
| | | | | | |
Step-4: List the penalties `P(i,j)` in descending order by value.
`P(2,3)=6`
`P(4,1)=5`
`P(3,2)=4`
`P(1,4)=3`
`P(1,2)=0`
Step-5: The links `(2,3),(4,1),(1,2)` are selected for inclusion in the feasible partial tour.
Step-6: Feasible partial tour contains the following chains
`4->1->2->3`
So our final path is `4->1->2->3->4`
and total distance is `5+4+4+9=22`
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
