2. Example-2
Find Solution of Travelling salesman problem using branch and bound (penalty) method (MIN case)
Work\Job | A | B | C | D | E | A | x | 5 | 8 | 4 | 5 | B | 5 | x | 7 | 4 | 5 | C | 8 | 7 | x | 8 | 6 | D | 4 | 4 | 8 | x | 8 | E | 5 | 5 | 6 | 8 | x |
Solution: The number of rows = 5 and columns = 5
| `A` | `B` | `C` | `D` | `E` | | `A` | M | 5 | 8 | 4 | 5 | | `B` | 5 | M | 7 | 4 | 5 | | `C` | 8 | 7 | M | 8 | 6 | | `D` | 4 | 4 | 8 | M | 8 | | `E` | 5 | 5 | 6 | 8 | M | | | | | | | | |
We know that the sum of row minimum gives us the lower bound. Step-1: Find out the each row minimum element and subtract it from that row
| `A` | `B` | `C` | `D` | `E` | | `A` | M | 1 | 4 | 0 | 1 | (-4) | `B` | 1 | M | 3 | 0 | 1 | (-4) | `C` | 2 | 1 | M | 2 | 0 | (-6) | `D` | 0 | 0 | 4 | M | 4 | (-4) | `E` | 0 | 0 | 1 | 3 | M | (-5) | | | | | | | |
So, row minimum will be `23`. (`4+4+6+4+5=23`)
Step-2: Find out the each column minimum element and subtract it from that column.
| `A` | `B` | `C` | `D` | `E` | | `A` | M | 1 | 3 | 0 | 1 | | `B` | 1 | M | 2 | 0 | 1 | | `C` | 2 | 1 | M | 2 | 0 | | `D` | 0 | 0 | 3 | M | 4 | | `E` | 0 | 0 | 0 | 3 | M | | | (-0) | (-0) | (-1) | (-0) | (-0) | |
So, column minimum will be `1`. (`0+0+1+0+0=1`)
we get the lower bound = `23+1=24`
Calculate the penalty of all 0's (penalty = minimum element of that row + minimum element of that column.)
| `A` | `B` | `C` | `D` | `E` | | `A` | `M` | `1` | `3` | `0^(color{red}{(1)})` | `1` | | `B` | `1` | `M` | `2` | `0^(color{red}{(1)})` | `1` | | `C` | `2` | `1` | `M` | `2` | `0^(color{red}{(2)})` | | `D` | `0^(color{red}{(0)})` | `0^(color{red}{(0)})` | `3` | `M` | `4` | | `E` | `0^(color{red}{(0)})` | `0^(color{red}{(0)})` | `0^(color{red}{(2)})` | `3` | `M` | | | | | | | | |
Here maximum penalty is 2, occur at `X_(C,E)` or `X_(E,C)` , so we choose `X_(E,C)` to begin branch
There are two branches. 1. If `X_(E,C)=0`, then we have an additional cost of `2` and the lower bound becomes `24+2=26`
2. If `X_(E,C)=1`,
we can go `E->C`
So we can't go `C->E`, so set it to M.
Now we leave row `E` and column `C`, so reduced matrix is
| `A` | `B` | `D` | `E` | | `A` | M | 1 | 0 | 1 | | `B` | 1 | M | 0 | 1 | | `C` | 2 | 1 | 2 | M | | `D` | 0 | 0 | M | 4 | | | | | | | |
Step-1: Find out the each row minimum element and subtract it from that row
| `A` | `B` | `D` | `E` | | `A` | M | 1 | 0 | 1 | (-0) | `B` | 1 | M | 0 | 1 | (-0) | `C` | 1 | 0 | 1 | M | (-1) | `D` | 0 | 0 | M | 4 | (-0) | | | | | | |
So, row minimum will be `1`. (`0+0+1+0=1`)
Step-2: Find out the each column minimum element and subtract it from that column.
| `A` | `B` | `D` | `E` | | `A` | M | 1 | 0 | 0 | | `B` | 1 | M | 0 | 0 | | `C` | 1 | 0 | 1 | M | | `D` | 0 | 0 | M | 3 | | | (-0) | (-0) | (-0) | (-1) | |
So, column minimum will be `1`. (`0+0+0+1=1`)
we get the lower bound = `24+1+1=26`
Calculate the penalty of all 0's (penalty = minimum element of that row + minimum element of that column.)
| `A` | `B` | `D` | `E` | | `A` | `M` | `1` | `0^(color{red}{(0)})` | `0^(color{red}{(0)})` | | `B` | `1` | `M` | `0^(color{red}{(0)})` | `0^(color{red}{(0)})` | | `C` | `1` | `0^(color{red}{(1)})` | `1` | `M` | | `D` | `0^(color{red}{(1)})` | `0^(color{red}{(0)})` | `M` | `3` | | | | | | | |
Here maximum penalty is 1, occur at `X_(C,B)` or `X_(D,A)` , so we choose `X_(C,B)` to begin branch
There are two branches. 1. If `X_(C,B)=0`, then we have an additional cost of `1` and the lower bound becomes `26+1=27`
2. If `X_(C,B)=1`,
we can go `C->B`
Here till now we traversed `E->C->B`
So we can't go `B->E`, so set it to M.
Now we leave row `C` and column `B`, so reduced matrix is
| `A` | `D` | `E` | | `A` | M | 0 | 0 | | `B` | 1 | 0 | M | | `D` | 0 | M | 3 | | | | | | |
Here we have 0 in every row and column. So, the lower bound remains the same i.e, `26+0=26`
Calculate the penalty of all 0's (penalty = minimum element of that row + minimum element of that column.)
| `A` | `D` | `E` | | `A` | `M` | `0^(color{red}{(0)})` | `0^(color{red}{(3)})` | | `B` | `1` | `0^(color{red}{(1)})` | `M` | | `D` | `0^(color{red}{(4)})` | `M` | `3` | | | | | | |
Here maximum penalty is 4, occur at `X_(D,A)` , so we choose `X_(D,A)` to begin branch
There are two branches. 1. If `X_(D,A)=0`, then we have an additional cost of `4` and the lower bound becomes `26+4=30`
2. If `X_(D,A)=1`,
we can go `D->A`
So we can't go `A->D`, so set it to M.
Now we leave row `D` and column `A`, so reduced matrix is
Here we have 0 in every row and column. So, the lower bound remains the same i.e, `26+0=26`
Calculate the penalty of all 0's (penalty = minimum element of that row + minimum element of that column.)
| `D` | `E` | | `A` | `M` | `0^(color{red}{(0)})` | | `B` | `0^(color{red}{(0)})` | `M` | | | | | |
we can go `A->E`
and `B->D`
So our final path is `E->C->B->D->A->E`
and total distance is `6+7+4+4+5=26`
This material is intended as a summary. Use your textbook for detail explanation. Any bug, improvement, feedback then
|