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 > Travelling salesman problem using branch and bound (penalty) method example
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
1. Algorithm & Example-1
(Previous example)		4. Travelling salesman branch and bound method
(Next method)

2. Example-2


Find Solution of Travelling salesman problem using branch and bound (penalty) method (MIN case)
Work\JobABCDE
Ax5845
B5x745
C87x86
D448x8
E5568x


Solution:
The number of rows = 5 and columns = 5
   `A`  `B`  `C`  `D`  `E`    
 `A` M5845
 `B` 5M745
 `C` 87M86
 `D` 448M8
 `E` 5568M
   



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` M1401(-4)
 `B` 1M301(-4)
 `C` 21M20(-6)
 `D` 004M4(-4)
 `E` 0013M(-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` M1301
 `B` 1M201
 `C` 21M20
 `D` 003M4
 `E` 0003M
   (-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` M101
 `B` 1M01
 `C` 212M
 `D` 00M4
   


Step-1: Find out the each row minimum element and subtract it from that row
   `A`  `B`  `D`  `E`    
 `A` M101(-0)
 `B` 1M01(-0)
 `C` 101M(-1)
 `D` 00M4(-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` M100
 `B` 1M00
 `C` 101M
 `D` 00M3
   (-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` M00
 `B` 10M
 `D` 0M3
   


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

   `D`  `E`    
 `A` M0
 `B` 0M
   


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


1. Algorithm & Example-1
(Previous example)		4. Travelling salesman branch and bound method
(Next method)


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
 
 

.