Travelling salesman problem using branch and bound method Example-1

1. Example-1

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

Support us

Home > Operation Research calculators > Assignment Problem example (Using Hungarian method)

4. Travelling salesman problem using branch and bound method example ( Enter your problem )

( Enter your problem )

Example-1
Example-2

Other related methods

Assignment problem using Hungarian method
Travelling salesman problem using Hungarian method
Travelling salesman branch and bound (penalty) method
Travelling salesman branch and bound method
Travelling salesman nearest neighbor method
Travelling salesman diagonal completion method
Crew assignment problem

3. Travelling salesman branch and bound (penalty) method
(Previous method)

2. Example-2
(Next example)

`x_(1,2)=1`

`x_(1,3)=1`

`x_(1,4)=1`

`x_(2,1)=1`

`x_(2,3)=1`

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

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`	M	4	8
`3`	9	M	9
`4`	5	9	M

`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`	6	M	8
`3`	M	4	9
`4`	5	8	M

`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`	6	M	4
`3`	9	4	M
`4`	M	8	9

`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`
22	24	21

`:.` 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`	4	M
`4`	M	9

`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`	9	M
`4`	M	8

`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

`:.` 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`	M	9
`4`	5	M

`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`	9	M
`4`	5	9

`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`
22		24	21
`x_(2,3)=1`	`x_(2,4)=1`		`x_(2,1)=1`	`x_(2,3)=1`
22	26		24	26

`:.` 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`
22		24	21
`x_(2,3)=1`	`x_(2,4)=1`		`x_(2,1)=1`	`x_(2,3)=1`
22	26		24	26
`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`
22		24	21
`x_(2,3)=1`	`x_(2,4)=1`		`x_(2,1)=1`	`x_(2,3)=1`
22	26		24	26
`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