We use cookies to improve your experience on our site and to show you relevant advertising. By browsing this website, you agree to our use of cookies. Learn more   

AtoZmath.com
Support us
(New) All problem can be solved using search box
I want to sell my website www.AtoZmath.com with complete code
Home What's new College Algebra Games Feedback About us
Algebra Matrix & Vector Numerical Methods Statistical Methods Operation Research Word Problems Calculus Geometry Pre-Algebra


Home > Operation Research calculators > Assignment Problem example (Using Hungarian method)
3. Travelling salesman problem using branch and bound (penalty) method example ( Enter your problem )
( Enter your problem )
  1. Algorithm & Example-1
  2. Example-2
 		Other related methods
  1. Assignment problem using Hungarian method
  2. Travelling salesman problem using Hungarian method
  3. Travelling salesman branch and bound (penalty) method
  4. Travelling salesman branch and bound method
  5. Travelling salesman nearest neighbor method
  6. Travelling salesman diagonal completion method
  7. Crew assignment problem
2. Travelling salesman problem using Hungarian method
(Previous method)		2. Example-2
(Next example)

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
Find Solution of Travelling salesman problem using branch and bound (penalty) method (MIN case)
Work\Job1234
1x495
26x48
394x9
4589x


Solution:
The number of rows = 4 and columns = 4
   `1`  `2`  `3`  `4`    
 `1` M495
 `2` 6M48
 `3` 94M9
 `4` 589M
   



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` M051(-4)
 `2` 2M04(-4)
 `3` 50M5(-4)
 `4` 034M(-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` M050
 `2` 2M03
 `3` 50M4
 `4` 034M
   (-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` M00
 `3` 5M4
 `4` 03M
   


Step-1: Find out the each row minimum element and subtract it from that row
   `1`  `2`  `4`    
 `1` M00(-0)
 `3` 1M0(-4)
 `4` 03M(-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

   `2`  `4`    
 `1` 0M
 `3` M0
   


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 Submit Here


2. Travelling salesman problem using Hungarian method
(Previous method)		2. Example-2
(Next example)


Share this solution or page with your friends.


Home What's new College Algebra Games Feedback About us
 
Copyright © 2023. All rights reserved. Terms, Privacy
 
 

.