1. Algorithm & Example-1
Algorithm
|
Travelling salesman problem using branch and bound (penalty) method Steps (Rule)
|
|
Step-1:
|
Find out the each row minimum element and subtract it from that row.
Also add each row minimum element is called row minimum.
|
|
Step-2:
|
Find out the each column minimum element and subtract it from that column.
Also add each column minimum element is called column minimum.
|
|
Step-3:
|
lower bound = row minimum + column minimum
|
|
Step-4:
|
Calculate the penalty of all 0's
penalty (of each 0) = minimum element of that row + minimum element of that column.
|
|
Step-5:
|
Find maximum penalty from all this penalties. And the new branch will be start from this location.
If there are more than 1 such location then choose any one arbitrarily.
|
|
Step-6:
|
Let branch will occur at `X_(A,D)`.
There are two branches.
1. If `X_(A,D)=0`, then we have an additional cost of say t and the lower bound becomes LB + t
2. If `X_(A,D)=1`, then we can go `A->D`
So we can't go `D->A`, so set it to M.
Now we leave row A and column D.
Again repeat the steps from step-1 using this reduced matrix, until whole path is found.
|
|
Step-7:
|
So finally we get total distance and final path.
|
Example-1
1. Find Solution of Travelling salesman problem using branch and bound (penalty) 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 | | | | | | | | |
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
| | `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) | | | | | | | |
So, row minimum will be `17`. (`4+4+4+5=17`)
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) | |
So, column minimum will be `1`. (`0+0+0+1=1`)
we get the lower bound = `17+1=18`
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` | | | | | | | | |
Here maximum penalty is 6, occur at `X_(2,3)` , so we choose `X_(2,3)` to begin branch
There are two branches.
1. If `X_(2,3)=0`, then we have an additional cost of `6` and the lower bound becomes `18+6=24`
2. If `X_(2,3)=1`,
we can go `2->3`
So we can't go `3->2`, so set it to M.
Now we leave row `2` and column `3`, so reduced matrix is
| | `1` | `2` | `4` | | | `1` | M | 0 | 0 | | | `3` | 5 | M | 4 | | | `4` | 0 | 3 | M | | | | | | | |
Step-1: Find out the each row minimum element and subtract it from that row
| | `1` | `2` | `4` | | | `1` | M | 0 | 0 | (-0) | | `3` | 1 | M | 0 | (-4) | | `4` | 0 | 3 | M | (-0) | | | | | | |
So, row minimum will be `4`. (`0+4+0=4`)
we get the lower bound = `18+4+0=22`
Calculate the penalty of all 0's (penalty = minimum element of that row + minimum element of that column.)
| | `1` | `2` | `4` | | | `1` | `M` | `0^(color{red}{(3)})` | `0^(color{red}{(0)})` | | | `3` | `1` | `M` | `0^(color{red}{(1)})` | | | `4` | `0^(color{red}{(4)})` | `3` | `M` | | | | | | | |
Here maximum penalty is 4, occur at `X_(4,1)` , so we choose `X_(4,1)` to begin branch
There are two branches.
1. If `X_(4,1)=0`, then we have an additional cost of `4` and the lower bound becomes `22+4=26`
2. If `X_(4,1)=1`,
we can go `4->1`
So we can't go `1->4`, so set it to M.
Now we leave row `4` and column `1`, so reduced matrix is
Here we have 0 in every row and column. So, the lower bound remains the same i.e, `22+0=22`
Calculate the penalty of all 0's (penalty = minimum element of that row + minimum element of that column.)
| | `2` | `4` | | | `1` | `0^(color{red}{(0)})` | `M` | | | `3` | `M` | `0^(color{red}{(0)})` | | | | | | |
we can go `1->2`
and `3->4`
So our final path is `2->3->4->1->2`
and total distance is `4+9+5+4=22`
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
|
