1 of 48

Travelling Salesman Problem�

Travelling Salesman Problem states-

A salesman has to visit every city exactly once.
He has to come back to the city from where he starts his journey.
What is the shortest possible route that the salesman must follow to complete his tour?

Amity School of Engineering & Technology

2 of 48

Problem-�

Solve Travelling Salesman Problem using Branch and Bound Algorithm in the following graph-

Amity School of Engineering & Technology

3 of 48

Solution-�

Step-01:

Write the initial cost matrix and reduce it-

Amity School of Engineering & Technology

4 of 48

Rules

To reduce a matrix, perform the row reduction and column reduction of the matrix separately.
A row or a column is said to be reduced if it contains at least one entry ‘0’ in it.

Amity School of Engineering & Technology

5 of 48

Row Reduction-

Consider the rows of above matrix one by one.

If the row already contains an entry ‘0’, then-

There is no need to reduce that row.

If the row does not contains an entry ‘0’, then-

Reduce that particular row.
Select the least value element from that row.
Subtract that element from each element of that row.
This will create an entry ‘0’ in that row, thus reducing that row.

Amity School of Engineering & Technology

6 of 48

Following this, we have-

Reduce the elements of row-1 by 4.
Reduce the elements of row-2 by 5.
Reduce the elements of row-3 by 6.
Reduce the elements of row-4 by 2.

Amity School of Engineering & Technology

7 of 48

Performing this, we obtain the following row-reduced matrix-

Amity School of Engineering & Technology

8 of 48

Column Reduction-

Consider the columns of above row-reduced matrix one by one.

If the column already contains an entry ‘0’, then-

There is no need to reduce that column.

If the column does not contains an entry ‘0’, then-

Reduce that particular column.
Select the least value element from that column.
Subtract that element from each element of that column.
This will create an entry ‘0’ in that column, thus reducing that column.

Amity School of Engineering & Technology

9 of 48

Following this, we have-

There is no need to reduce column-1.
There is no need to reduce column-2.
Reduce the elements of column-3 by 1.
There is no need to reduce column-4.

Amity School of Engineering & Technology

10 of 48

Performing this, we obtain the following column-reduced matrix-

Amity School of Engineering & Technology

11 of 48

Finally, the initial distance matrix is completely reduced.
Now, we calculate the cost of node-1 by adding all the reduction elements.

Cost(1)

= Sum of all reduction elements

= 4 + 5 + 6 + 2 + 1

= 18

Amity School of Engineering & Technology

12 of 48

Step-02:

We consider all other vertices one by one.
We select the best vertex where we can land upon to minimize the tour cost.
Choosing To Go To Vertex-B: Node-2 (Path A → B)

From the reduced matrix of step-01, M[A,B] = 0
Set row-A and column-B to ∞
Set M[B,A] = ∞

Amity School of Engineering & Technology

13 of 48

Now, resulting cost matrix is-

Now,

We reduce this matrix.

Then, we find out the cost of node-02.

Amity School of Engineering & Technology

14 of 48

Row Reduction-

We can not reduce row-1 as all its elements are ∞.
Reduce all the elements of row-2 by 13.
There is no need to reduce row-3.
There is no need to reduce row-4.

Amity School of Engineering & Technology

15 of 48

Performing this, we obtain the following row-reduced matrix-

Amity School of Engineering & Technology

16 of 48

Column Reduction-

Reduce the elements of column-1 by 5.
We can not reduce column-2 as all its elements are ∞.
There is no need to reduce column-3.
There is no need to reduce column-4.

Amity School of Engineering & Technology

17 of 48

Performing this, we obtain the following column-reduced matrix-

Finally, the matrix is completely reduced.

Amity School of Engineering & Technology

18 of 48

Now, we calculate the cost of node-2.

Cost(2)

= Cost(1) + Sum of reduction elements + M[A,B]

= 18 + (13 + 5) + 0

= 36

Amity School of Engineering & Technology

19 of 48

Choosing To Go To Vertex-C: Node-3 (Path A → C)

From the reduced matrix of step-01, M[A,C] = 7
Set row-A and column-C to ∞
Set M[C,A] = ∞

Amity School of Engineering & Technology

20 of 48

Now, resulting cost matrix is-

Now,

We reduce this matrix.

Then, we find out the cost of node-03.

Amity School of Engineering & Technology

21 of 48

Row Reduction-

We can not reduce row-1 as all its elements are ∞.
There is no need to reduce row-2.
There is no need to reduce row-3.
There is no need to reduce row-4.
Thus, the matrix is already row-reduced.

Amity School of Engineering & Technology

22 of 48

Column Reduction-

There is no need to reduce column-1.
There is no need to reduce column-2.
We can not reduce column-3 as all its elements are ∞.
There is no need to reduce column-4.
Thus, the matrix is already column reduced.
Finally, the matrix is completely reduced.

Amity School of Engineering & Technology

23 of 48

Choosing To Go To Vertex-D: Node-4 (Path A → D)

From the reduced matrix of step-01, M[A,D] = 3
Set row-A and column-D to ∞
Set M[D,A] = ∞

Amity School of Engineering & Technology

24 of 48

Now, resulting cost matrix is-

Now,

We reduce this matrix.

Then, we find out the cost of node-04.

Amity School of Engineering & Technology

25 of 48

Row Reduction-

We can not reduce row-1 as all its elements are ∞.
There is no need to reduce row-2.
Reduce all the elements of row-3 by 5.
There is no need to reduce row-4.

Amity School of Engineering & Technology

26 of 48

Performing this, we obtain the following row-reduced matrix-

Amity School of Engineering & Technology

27 of 48

Column Reduction-

There is no need to reduce column-1.
There is no need to reduce column-2.
There is no need to reduce column-3.
We can not reduce column-4 as all its elements are ∞.

Thus, the matrix is already column-reduced.

Finally, the matrix is completely reduced.

Amity School of Engineering & Technology

28 of 48

Now, we calculate the cost of node-4.

Cost(4)

= Cost(1) + Sum of reduction elements + M[A,D]

= 18 + 5 + 3

= 26

Amity School of Engineering & Technology

29 of 48

Thus, we have-

Cost(2) = 36 (for Path A → B)
Cost(3) = 25 (for Path A → C)
Cost(4) = 26 (for Path A → D)

We choose the node with the lowest cost.
Since cost for node-3 is lowest, so we prefer to visit node-3. Thus, we choose node-3 i.e. path A → C.

Amity School of Engineering & Technology

30 of 48

Step-03:

We explore the vertices B and D from node-3.
We now start from the cost matrix at node-3 which is-

Amity School of Engineering & Technology

31 of 48

Choosing To Go To Vertex-B: Node-5 (Path A → C → B)
From the reduced matrix of step-02, M[C,B] = ∞
Set row-C and column-B to ∞
Set M[B,A] = ∞

Amity School of Engineering & Technology

32 of 48

Now, resulting cost matrix is-

Now,

We reduce this matrix.

Then, we find out the cost of node-5.

Amity School of Engineering & Technology

33 of 48

Row Reduction-

We can not reduce row-1 as all its elements are ∞.
Reduce all the elements of row-2 by 13.
We can not reduce row-3 as all its elements are ∞.
Reduce all the elements of row-4 by 8.

Amity School of Engineering & Technology

34 of 48

Performing this, we obtain the following row-reduced matrix-

Amity School of Engineering & Technology

35 of 48

Column Reduction-

There is no need to reduce column-1.
We can not reduce column-2 as all its elements are ∞.
We can not reduce column-3 as all its elements are ∞.
There is no need to reduce column-4.
Thus, the matrix is already column reduced.
Finally, the matrix is completely reduced.

Amity School of Engineering & Technology

36 of 48

Now, we calculate the cost of node-5.

Cost(5)

= cost(3) + Sum of reduction elements + M[C,B]

= 25 + (13 + 8) + ∞

= ∞

Amity School of Engineering & Technology

37 of 48

Choosing To Go To Vertex-D: Node-6 (Path A → C → D)

From the reduced matrix of step-02, M[C,D] = 0
Set row-C and column-D to ∞
Set M[D,A] = ∞

Amity School of Engineering & Technology

38 of 48

Now, resulting cost matrix is-

Now,

We reduce this matrix.

Then, we find out the cost of node-6.

Amity School of Engineering & Technology

39 of 48

Row Reduction-

We can not reduce row-1 as all its elements are ∞.
There is no need to reduce row-2.
We can not reduce row-3 as all its elements are ∞.
We can not reduce row-4 as all its elements are ∞.
Thus, the matrix is already row reduced.

Amity School of Engineering & Technology

40 of 48

Column Reduction-

There is no need to reduce column-1.
We can not reduce column-2 as all its elements are ∞.
We can not reduce column-3 as all its elements are ∞.
We can not reduce column-4 as all its elements are ∞.
Thus, the matrix is already column reduced.
Finally, the matrix is completely reduced.

Amity School of Engineering & Technology

41 of 48

Now, we calculate the cost of node-6.

Cost(6)

= cost(3) + Sum of reduction elements + M[C,D]

= 25 + 0 + 0

= 25

Amity School of Engineering & Technology

42 of 48

Thus, we have-

Cost(5) = ∞ (for Path A → C → B)
Cost(6) = 25 (for Path A → C → D)
We choose the node with the lowest cost.
Since cost for node-6 is lowest, so we prefer to visit node-6.
Thus, we choose node-6 i.e. path C → D.

Amity School of Engineering & Technology

43 of 48

Step-04:

We explore vertex B from node-6.
We start with the cost matrix at node-6 which is-

Amity School of Engineering & Technology

44 of 48

Choosing To Go To Vertex-B: Node-7 (Path A → C → D → B)

From the reduced matrix of step-03, M[D,B] = 0
Set row-D and column-B to ∞
Set M[B,A] = ∞

Amity School of Engineering & Technology

45 of 48

Now, resulting cost matrix is-

Now,

We reduce this matrix.

Then, we find out the cost of node-7.

Amity School of Engineering & Technology

46 of 48

Row Reduction-

We can not reduce row-1 as all its elements are ∞.
We can not reduce row-2 as all its elements are ∞.
We can not reduce row-3 as all its elements are ∞.
We can not reduce row-4 as all its elements are ∞.

Amity School of Engineering & Technology

47 of 48

Column Reduction-

We can not reduce column-1 as all its elements are ∞.
We can not reduce column-2 as all its elements are ∞.
We can not reduce column-3 as all its elements are ∞.
We can not reduce column-4 as all its elements are ∞.

Thus, the matrix is already column reduced.

Finally, the matrix is completely reduced.

Amity School of Engineering & Technology

48 of 48

Now, we calculate the cost of node-7.

Cost(7)

= cost(6) + Sum of reduction elements + M[D,B]

= 25 + 0 + 0

= 25

Thus,

Optimal path is: A → C → D → B → A

Cost of Optimal path = 25 units

Amity School of Engineering & Technology