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

1. Example-1


1. Find Solution of Travelling salesman problem using branch and bound method
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
   



The lower bound of total distance is
LB `=4+4+4+5=17`

So the tour has to travel at least `17`. Optimal solution will have to be more than or equal to the lower bound of `17`.

`:.` we create 3 more branches as `x_(1,2)=1,x_(1,3)=1,x_(1,4)=1` and `x_(1,1)=1` is a sub tour.

Branch-1 `->` For `x_(1,2)=1`, leave row `1` and column `2`

So we can't go `2->1`, so set it to M.

   `1`  `3`  `4`    
 `2` M48
 `3` 9M9
 `4` 59M
   


`1` to `2` will be `4+4+9+5=22`

Branch-2 `->` For `x_(1,3)=1`, leave row `1` and column `3`

So we can't go `3->1`, so set it to M.

   `1`  `2`  `4`    
 `2` 6M8
 `3` M49
 `4` 58M
   


`1` to `3` will be `9+6+4+5=24`

Branch-3 `->` For `x_(1,4)=1`, leave row `1` and column `4`

So we can't go `4->1`, so set it to M.

   `1`  `2`  `3`    
 `2` 6M4
 `3` 94M
 `4` M89
   


`1` to `4` will be `5+4+4+8=21`

Step 4: We want to minimize the total distance travelling, so evaluate up to this point `21` is minimum, so we branch further from this node.

4. The branch and bound diagram
LB
17
`x_(1,2)=1``x_(1,3)=1``x_(1,4)=1`
222421



`:.` we create 2 more branches as `x_(2,1)=1,x_(2,3)=1` and `x_(2,2)=1` is a sub tour.

Branch-1 `->` For `x_(2,1)=1`, leave row `2` and column `1`

Here till now we traversed `2->1->4`

So we can't go `4->2`, so set it to M.

   `2`  `3`    
 `3` 4M
 `4` M9
   


`2` to `1` will be `5+6+4+9=24`

Branch-2 `->` For `x_(2,3)=1`, leave row `2` and column `3`

So we can't go `3->2`, so set it to M.

   `1`  `2`    
 `3` 9M
 `4` M8
   


`2` to `3` will be `5+4+9+8=26`

Step 4: We want to minimize the total distance travelling, so evaluate up to this point `22` is minimum, so we branch further from this node.

4. The branch and bound diagram
LB
17
`x_(1,2)=1``x_(1,3)=1``x_(1,4)=1`
222421
`x_(2,1)=1``x_(2,3)=1`
2426



`:.` we create 2 more branches as `x_(2,3)=1,x_(2,4)=1` and `x_(2,1)=1` is a sub tour.

Branch-1 `->` For `x_(2,3)=1`, leave row `2` and column `3`

Here till now we traversed `1->2->3`

So we can't go `3->1`, so set it to M.

   `1`  `4`    
 `3` M9
 `4` 5M
   


`2` to `3` will be `4+4+9+5=22`

Branch-2 `->` For `x_(2,4)=1`, leave row `2` and column `4`

   `1`  `3`    
 `3` 9M
 `4` 59
   


`2` to `4` will be `4+8+9+5=26`

Step 4: We want to minimize the total distance travelling, so evaluate up to this point `22` is minimum, so we branch further from this node.

4. The branch and bound diagram
LB
17
`x_(1,2)=1``x_(1,3)=1``x_(1,4)=1`
222421
`x_(2,3)=1``x_(2,4)=1``x_(2,1)=1``x_(2,3)=1`
22262426



`:.` we create 1 more branches as `x_(3,4)=1` and `x_(3,1)=1` is a sub tour.

Branch-1 `->` For `x_(3,4)=1`, leave row `3` and column `4`

   `1`    
 `4` 5
   


`3` to `4` will be `4+4+9+5=22`

Step 4: We want to minimize the total distance travelling, so evaluate up to this point `22` is minimum, so we branch further from this node.

4. The branch and bound diagram
LB
17
`x_(1,2)=1``x_(1,3)=1``x_(1,4)=1`
222421
`x_(2,3)=1``x_(2,4)=1``x_(2,1)=1``x_(2,3)=1`
22262426
`x_(3,4)=1`
22



`:.` we create 1 more branches as `x_(4,1)=1`

`4` to `1` will be `4+4+9+5=22`

Answer :
The best optimal solution is `1to2,2to3,3to4,4to1`

The city path is `1->2->3->4->1`

which is 22

4. The branch and bound diagram
LB
17
`x_(1,2)=1``x_(1,3)=1``x_(1,4)=1`
222421
`x_(2,3)=1``x_(2,4)=1``x_(2,1)=1``x_(2,3)=1`
22262426
`x_(3,4)=1`
22
`x_(4,1)=1`
22




This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then Submit Here


3. Travelling salesman branch and bound (penalty) 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 © 2024. All rights reserved. Terms, Privacy
 
 

.