Find Solution of Travelling salesman problem using branch and bound method

Work\Job	A	B	C	D	E
A	x	2	5	7	1
B	6	x	3	8	2
C	8	7	x	4	7
D	12	4	6	x	5
E	1	3	2	8	x

Solution:
The number of rows = 5 and columns = 5

	`A`	`B`	`C`	`D`	`E`
`A`	M	2	5	7	1
`B`	6	M	3	8	2
`C`	8	7	M	4	7
`D`	12	4	6	M	5
`E`	1	3	2	8	M

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`	M	3	8	2
`C`	8	M	4	7
`D`	12	6	M	5
`E`	1	2	8	M

`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`	6	M	8	2
`C`	M	7	4	7
`D`	12	4	M	5
`E`	1	3	8	M

`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`	6	M	3	2
`C`	8	7	M	7
`D`	M	4	6	5
`E`	1	3	2	M

`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`	6	M	3	8
`C`	8	7	M	4
`D`	12	4	6	M
`E`	M	3	2	8

`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`
14		16		21		14

---

`:.` 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`	7	M	4
`D`	4	6	M
`E`	M	2	8

`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`	8	M	4
`D`	12	4	M
`E`	M	3	8

`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`	8	7	M
`D`	12	M	6
`E`	M	3	2

`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`
14		16		21		14
						`x_(B,A)=1`		`x_(B,C)=1`		`x_(B,D)=1`
						17		15		24

---

`:.` 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`	M	4	7
`D`	12	M	5
`E`	1	8	M

`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`	8	M	7
`D`	12	6	5
`E`	1	2	M

`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`	8	M	4
`D`	12	6	M
`E`	1	2	8

`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`
14						16		21		14
`x_(B,C)=1`		`x_(B,D)=1`		`x_(B,E)=1`						`x_(B,A)=1`		`x_(B,C)=1`		`x_(B,D)=1`
15		23		15						17		15		24

---

`:.` 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`	6	M
`E`	M	8

`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`	12	M
`E`	M	2

`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`
14								16		21		14
`x_(B,C)=1`		`x_(B,D)=1`		`x_(B,E)=1`								`x_(B,A)=1`		`x_(B,C)=1`		`x_(B,D)=1`
15		23		15								17		15		24
				`x_(C,A)=1`		`x_(C,D)=1`
				26		22

---

`:.` 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`	M	5
`E`	1	M

`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`	12	M
`E`	1	8

`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`
14										16		21		14
`x_(B,C)=1`				`x_(B,D)=1`		`x_(B,E)=1`								`x_(B,A)=1`		`x_(B,C)=1`		`x_(B,D)=1`
15				23		15								17		15		24
`x_(C,D)=1`		`x_(C,E)=1`				`x_(C,A)=1`		`x_(C,D)=1`
15		25				26		22

---

`:.` 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`
14										16		21		14
`x_(B,C)=1`				`x_(B,D)=1`		`x_(B,E)=1`								`x_(B,A)=1`		`x_(B,C)=1`		`x_(B,D)=1`
15				23		15								17		15		24
`x_(C,D)=1`		`x_(C,E)=1`				`x_(C,A)=1`		`x_(C,D)=1`
15		25				26		22
`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`
14										16		21		14
`x_(B,C)=1`				`x_(B,D)=1`		`x_(B,E)=1`								`x_(B,A)=1`		`x_(B,C)=1`		`x_(B,D)=1`
15				23		15								17		15		24
`x_(C,D)=1`		`x_(C,E)=1`				`x_(C,A)=1`		`x_(C,D)=1`
15		25				26		22
`x_(D,E)=1`
15
`x_(E,A)=1`
15

---

---