Travelling Salesman Problem
You are given
 A set of some cities
 Distance between every pair of cities
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?
Example
The following graph shows a set of cities and distance between every pair of cities
If salesman starting city is A, then a TSP tour in the graph is
A → B → D → C → A
Cost of the tour
= 10 + 25 + 30 + 15
= 80 units
In this article, we will discuss how to solve travelling salesman problem using branch and bound approach with example.
PRACTICE PROBLEM BASED ON TRAVELLING SALESMAN PROBLEM USING BRANCH AND BOUND APPROACH
Problem
Solve Travelling Salesman Problem using Branch and Bound Algorithm in the following graph
Solution
Step01:
Write the initial cost matrix and reduce it
Rules

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.
Following this, we have
 Reduce the elements of row1 by 4.
 Reduce the elements of row2 by 5.
 Reduce the elements of row3 by 6.
 Reduce the elements of row4 by 2.
Performing this, we obtain the following rowreduced matrix
Column Reduction
Consider the columns of above rowreduced 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.
Following this, we have
 There is no need to reduce column1.
 There is no need to reduce column2.
 Reduce the elements of column3 by 1.
 There is no need to reduce column4.
Performing this, we obtain the following columnreduced matrix
Finally, the initial distance matrix is completely reduced.
Now, we calculate the cost of node1 by adding all the reduction elements.
Cost(1)
= Sum of all reduction elements
= 4 + 5 + 6 + 2 + 1
= 18
Step02:
 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 VertexB: Node2 (Path A → B)
 From the reduced matrix of step01, M[A,B] = 0
 Set rowA and columnB to ∞
 Set M[B,A] = ∞
Now, resulting cost matrix is
Now,
 We reduce this matrix.
 Then, we find out the cost of node02.
Row Reduction
 We can not reduce row1 as all its elements are ∞.
 Reduce all the elements of row2 by 13.
 There is no need to reduce row3.
 There is no need to reduce row4.
Performing this, we obtain the following rowreduced matrix
Column Reduction
 Reduce the elements of column1 by 5.
 We can not reduce column2 as all its elements are ∞.
 There is no need to reduce column3.
 There is no need to reduce column4.
Performing this, we obtain the following columnreduced matrix
Finally, the matrix is completely reduced.
Now, we calculate the cost of node2.
Cost(2)
= Cost(1) + Sum of reduction elements + M[A,B]
= 18 + (13 + 5) + 0
= 36
Choosing To Go To VertexC: Node3 (Path A → C)
 From the reduced matrix of step01, M[A,C] = 7
 Set rowA and columnC to ∞
 Set M[C,A] = ∞
Now, resulting cost matrix is
Now,
 We reduce this matrix.
 Then, we find out the cost of node03.
Row Reduction
 We can not reduce row1 as all its elements are ∞.
 There is no need to reduce row2.
 There is no need to reduce row3.
 There is no need to reduce row4.
Thus, the matrix is already rowreduced.
Column Reduction
 There is no need to reduce column1.
 There is no need to reduce column2.
 We can not reduce column3 as all its elements are ∞.
 There is no need to reduce column4.
Thus, the matrix is already column reduced.
Finally, the matrix is completely reduced.
Now, we calculate the cost of node3.
Cost(3)
= Cost(1) + Sum of reduction elements + M[A,C]
= 18 + 0 + 7
= 25
Choosing To Go To VertexD: Node4 (Path A → D)
 From the reduced matrix of step01, M[A,D] = 3
 Set rowA and columnD to ∞
 Set M[D,A] = ∞
Now, resulting cost matrix is
Now,
 We reduce this matrix.
 Then, we find out the cost of node04.
Row Reduction
 We can not reduce row1 as all its elements are ∞.
 There is no need to reduce row2.
 Reduce all the elements of row3 by 5.
 There is no need to reduce row4.
Performing this, we obtain the following rowreduced matrix
Column Reduction
 There is no need to reduce column1.
 There is no need to reduce column2.
 There is no need to reduce column3.
 We can not reduce column4 as all its elements are ∞.
Thus, the matrix is already columnreduced.
Finally, the matrix is completely reduced.
Now, we calculate the cost of node4.
Cost(4)
= Cost(1) + Sum of reduction elements + M[A,D]
= 18 + 5 + 3
= 26
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 node3 is lowest, so we prefer to visit node3.
Thus, we choose node3 i.e. path A → C.
Step03:
We explore the vertices B and D from node3.
We now start from the cost matrix at node3 which is
Cost(3) = 25
Choosing To Go To VertexB: Node5 (Path A → C → B)
 From the reduced matrix of step02, M[C,B] = ∞
 Set rowC and columnB to ∞
 Set M[B,A] = ∞
Now, resulting cost matrix is
Now,
 We reduce this matrix.
 Then, we find out the cost of node5.
Row Reduction
 We can not reduce row1 as all its elements are ∞.
 Reduce all the elements of row2 by 13.
 We can not reduce row3 as all its elements are ∞.
 Reduce all the elements of row4 by 8.
Performing this, we obtain the following rowreduced matrix
Column Reduction
 There is no need to reduce column1.
 We can not reduce column2 as all its elements are ∞.
 We can not reduce column3 as all its elements are ∞.
 There is no need to reduce column4.
Thus, the matrix is already column reduced.
Finally, the matrix is completely reduced.
Now, we calculate the cost of node5.
Cost(5)
= cost(3) + Sum of reduction elements + M[C,B]
= 25 + (13 + 8) + ∞
= ∞
Choosing To Go To VertexD: Node6 (Path A → C → D)
 From the reduced matrix of step02, M[C,D] = ∞
 Set rowC and columnD to ∞
 Set M[D,A] = ∞
Now, resulting cost matrix is
Now,
 We reduce this matrix.
 Then, we find out the cost of node6.
Row Reduction
 We can not reduce row1 as all its elements are ∞.
 There is no need to reduce row2.
 We can not reduce row3 as all its elements are ∞.
 We can not reduce row4 as all its elements are ∞.
Thus, the matrix is already row reduced.
Column Reduction
 There is no need to reduce column1.
 We can not reduce column2 as all its elements are ∞.
 We can not reduce column3 as all its elements are ∞.
 We can not reduce column4 as all its elements are ∞.
Thus, the matrix is already column reduced.
Finally, the matrix is completely reduced.
Now, we calculate the cost of node6.
Cost(6)
= cost(3) + Sum of reduction elements + M[C,D]
= 25 + 0 + 0
= 25
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 node6 is lowest, so we prefer to visit node6.
Thus, we choose node6 i.e. path C → D.
Step04:
We explore vertex B from node6.
We start with the cost matrix at node6 which is
Cost(6) = 25
Choosing To Go To VertexB: Node7 (Path A → C → D → B)
 From the reduced matrix of step03, M[D,B] = 0
 Set rowD and columnB to ∞
 Set M[B,A] = ∞
Now, resulting cost matrix is
Now,
 We reduce this matrix.
 Then, we find out the cost of node7.
Row Reduction
 We can not reduce row1 as all its elements are ∞.
 We can not reduce row2 as all its elements are ∞.
 We can not reduce row3 as all its elements are ∞.
 We can not reduce row4 as all its elements are ∞.
Column Reduction
 We can not reduce column1 as all its elements are ∞.
 We can not reduce column2 as all its elements are ∞.
 We can not reduce column3 as all its elements are ∞.
 We can not reduce column4 as all its elements are ∞.
Thus, the matrix is already column reduced.
Finally, the matrix is completely reduced.
All the entries have become ∞.
Now, we calculate the cost of node7.
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
To gain better understanding about Travelling Salesman Problem,
Get more notes and other study material of Design and Analysis of Algorithms.
Watch video lectures by visiting our YouTube channel LearnVidFun.