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
1. Example-1
(Previous example)		5. Travelling salesman nearest neighbor method
(Next method)

2. Example-2


Find Solution of Travelling salesman problem using branch and bound method
Work\JobABCDE
Ax2571
B6x382
C87x47
D1246x5
E1328x


Solution:
The number of rows = 5 and columns = 5
   `A`  `B`  `C`  `D`  `E`    
 `A` M2571
 `B` 6M382
 `C` 87M47
 `D` 1246M5
 `E` 1328M
   



The lower bound of total distance is
LB `=1+2+4+4+1=12`

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

`:.` we create 4 more branches as `x_(A,B)=1,x_(A,C)=1,x_(A,D)=1,x_(A,E)=1` and `x_(A,A)=1` is a sub tour.

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

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

   `A`  `C`  `D`  `E`    
 `B` M382
 `C` 8M47
 `D` 126M5
 `E` 128M
   


`A` to `B` will be `2+2+4+5+1=14`

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

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

   `A`  `B`  `D`  `E`    
 `B` 6M82
 `C` M747
 `D` 124M5
 `E` 138M
   


`A` to `C` will be `5+2+4+4+1=16`

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

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

   `A`  `B`  `C`  `E`    
 `B` 6M32
 `C` 87M7
 `D` M465
 `E` 132M
   


`A` to `D` will be `7+2+7+4+1=21`

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

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

   `A`  `B`  `C`  `D`    
 `B` 6M38
 `C` 87M4
 `D` 1246M
 `E` M328
   


`A` to `E` will be `1+3+4+4+2=14`

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

4. The branch and bound diagram
LB
12
`x_(A,B)=1``x_(A,C)=1``x_(A,D)=1``x_(A,E)=1`
14162114



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

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

Here till now we traversed `B->A->E`

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

   `B`  `C`  `D`    
 `C` 7M4
 `D` 46M
 `E` M28
   


`B` to `A` will be `1+6+4+4+2=17`

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

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

   `A`  `B`  `D`    
 `C` 8M4
 `D` 124M
 `E` M38
   


`B` to `C` will be `1+3+4+4+3=15`

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

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

   `A`  `B`  `C`    
 `C` 87M
 `D` 12M6
 `E` M32
   


`B` to `D` will be `1+8+7+6+2=24`

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

4. The branch and bound diagram
LB
12
`x_(A,B)=1``x_(A,C)=1``x_(A,D)=1``x_(A,E)=1`
14162114
`x_(B,A)=1``x_(B,C)=1``x_(B,D)=1`
171524



`:.` we create 3 more branches as `x_(B,C)=1,x_(B,D)=1,x_(B,E)=1` and `x_(B,A)=1` is a sub tour.

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

Here till now we traversed `A->B->C`

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

   `A`  `D`  `E`    
 `C` M47
 `D` 12M5
 `E` 18M
   


`B` to `C` will be `2+3+4+5+1=15`

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

   `A`  `C`  `E`    
 `C` 8M7
 `D` 1265
 `E` 12M
   


`B` to `D` will be `2+8+7+5+1=23`

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

   `A`  `C`  `D`    
 `C` 8M4
 `D` 126M
 `E` 128
   


`B` to `E` will be `2+2+4+6+1=15`

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

4. The branch and bound diagram
LB
12
`x_(A,B)=1``x_(A,C)=1``x_(A,D)=1``x_(A,E)=1`
14162114
`x_(B,C)=1``x_(B,D)=1``x_(B,E)=1``x_(B,A)=1``x_(B,C)=1``x_(B,D)=1`
152315171524



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

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

Here till now we traversed `C->A->B->E`

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

   `C`  `D`    
 `D` 6M
 `E` M8
   


`C` to `A` will be `2+2+8+6+8=26`

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

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

   `A`  `C`    
 `D` 12M
 `E` M2
   


`C` to `D` will be `2+2+4+12+2=22`

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

4. The branch and bound diagram
LB
12
`x_(A,B)=1``x_(A,C)=1``x_(A,D)=1``x_(A,E)=1`
14162114
`x_(B,C)=1``x_(B,D)=1``x_(B,E)=1``x_(B,A)=1``x_(B,C)=1``x_(B,D)=1`
152315171524
`x_(C,A)=1``x_(C,D)=1`
2622



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

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

Here till now we traversed `A->B->C->D`

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

   `A`  `E`    
 `D` M5
 `E` 1M
   


`C` to `D` will be `2+3+4+5+1=15`

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

   `A`  `D`    
 `D` 12M
 `E` 18
   


`C` to `E` will be `2+3+7+12+1=25`

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

4. The branch and bound diagram
LB
12
`x_(A,B)=1``x_(A,C)=1``x_(A,D)=1``x_(A,E)=1`
14162114
`x_(B,C)=1``x_(B,D)=1``x_(B,E)=1``x_(B,A)=1``x_(B,C)=1``x_(B,D)=1`
152315171524
`x_(C,D)=1``x_(C,E)=1``x_(C,A)=1``x_(C,D)=1`
15252622



`:.` we create 1 more branches as `x_(D,E)=1` and `x_(D,A)=1` is a sub tour.

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

   `A`    
 `E` 1
   


`D` to `E` will be `2+3+4+5+1=15`

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

4. The branch and bound diagram
LB
12
`x_(A,B)=1``x_(A,C)=1``x_(A,D)=1``x_(A,E)=1`
14162114
`x_(B,C)=1``x_(B,D)=1``x_(B,E)=1``x_(B,A)=1``x_(B,C)=1``x_(B,D)=1`
152315171524
`x_(C,D)=1``x_(C,E)=1``x_(C,A)=1``x_(C,D)=1`
15252622
`x_(D,E)=1`
15



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

`E` to `A` will be `2+3+4+5+1=15`

Answer :
The best optimal solution is `AtoB,BtoC,CtoD,DtoE,EtoA`

The city path is `A->B->C->D->E->A`

which is 15

4. The branch and bound diagram
LB
12
`x_(A,B)=1``x_(A,C)=1``x_(A,D)=1``x_(A,E)=1`
14162114
`x_(B,C)=1``x_(B,D)=1``x_(B,E)=1``x_(B,A)=1``x_(B,C)=1``x_(B,D)=1`
152315171524
`x_(C,D)=1``x_(C,E)=1``x_(C,A)=1``x_(C,D)=1`
15252622
`x_(D,E)=1`
15
`x_(E,A)=1`
15


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


1. Example-1
(Previous example)		5. Travelling salesman nearest neighbor method
(Next method)


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
 
 

.