Travelling Salesman Problem | Branch and Bound

Travelling Salesman Problem-

 

You are given a set consisting of some cities and you are told the distances between every pair of cities.

The problem states-

“What is the shortest possible route that the salesman must follow to complete his tour such that he visits every city exactly once and then comes back to the city from where he started his journey?”

 

Example-

Consider the graph shown-

City A is the home town of Salesman from where he starts his journey.

 

 

A TSP tour in the graph is-

A → B → D → C → A

Cost of the tour = 10 + 25 + 30 + 15 = 80 units

 

PRACTICE PROBLEM BASED ON TRAVELLING SALESMAN PROBLEM USING BRANCH AND BOUND APPROACH-

 

Problem-

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

 

 

Solution-

 

Step-01:

Write the initial cost matrix and reduce it-

 

 

Now, to reduce this matrix, we will perform the row reduction and column reduction of the above matrix separately.

 

Remember

A row or a column is said to be already reduced if it contains at least one entry ‘0’ in it.

 

Perform row reduction-

 

Now, consider all the rows of the above matrix one by one.

  • If the row already contains an entry ‘0’, then there is no need to reduce it.
  • If the row does not contains an entry ‘0’, then reduce that particular row.

 

To reduce such a row, select the least value element from that row and then subtract that particular element from each element of that row. This will create an entry ‘0’ in that row.

 

Following this, we have-

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

 

Performing this, we obtain the following matrix which is now row reduced-

 

 

Perform column reduction-

 

Now, consider all the columns of the above row reduced matrix one by one.

  • If the column already contains an entry ‘0’, then there is no need to reduce it.
  • If the column does not contains an entry ‘0’, then reduce that particular column.

 

To reduce such a column, select the least value element from that column and then subtract that particular element from each element of that column. This will create an entry ‘0’ in that column.

 

Following this, we have-

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

 

Performing this, we obtain the following matrix which is now column reduced-

 

 

Finally, this matrix is now completely reduced as it is row reduced as well as column reduced.

 

Now, Cost of node-1 is calculated by adding all the reduction elements.

Cost(1) = 4 + 5 + 6 + 2 + 1 = 18

 

Step-02:

 

Now, we will consider all other vertices one by one and select the best vertex where we can land upon to minimize the cost of the tour.

 

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] = 
  • Now, resulting cost matrix is-

 

 

Now, we will reduce this matrix in the same way as we reduced the matrix in step-01 and will find out the cost of node-02.

 

Perform row reduction-

 

  • We can not reduce row-1 as all 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

 

Performing this, we obtain the following matrix which is now row reduced-

 

 

Perform column reduction-

 

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

 

Performing this, we obtain the following matrix which is now column reduced-

 

 

Finally, this matrix is now completely reduced as it is row reduced as well as column reduced.

 

Now, Cost of node-2 is calculated as-

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

Cost(2) = 18 + (13 + 5) + 0

Cost(2) = 36

 

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] = 
  • Now, resulting cost matrix is-

 

 

Now, we will reduce this matrix in the same way as we reduced the matrix in step-01 and will find out the cost of node-03.

 

Perform row reduction-

 

  • We can not reduce row-1 as all 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, this matrix is already row reduced.

 

Perform 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 elements are 
  • There is no need to reduce column-4

 

Thus, this matrix is already column reduced as well.

So, the matrix is already completely reduced as it is row reduced as well as column reduced.

 

Now, Cost of node-3 is calculated as-

Cost(3) = cost(1) + Sum of reduction elements + M[A,C]

Cost(3) = 18 + 0 + 7

Cost(3) = 25

 

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] = 
  • Now, resulting cost matrix is-

 

 

Now, we will reduce this matrix in the same way as we reduced the matrix in step-01 and will find out the cost of node-04.

 

Perform row reduction-

 

  • We can not reduce row-1 as all 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

 

Performing this, we obtain the following matrix which is now row reduced-

 

 

Perform 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 elements are 

 

Thus, this matrix is already column reduced.

Finally, this matrix is now completely reduced as it is row reduced as well as column reduced.

 

Now, Cost of node-4 is calculated as-

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

Cost(2) = 18 + 5 + 3

Cost(2) = 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 will 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

 

Step-03:

Now, we will explore the vertices B and D from node-3.

 

Note-

We will now start from the cost matrix at node-3 which is-

 

Cost(3) = 25

 

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] = 
  • Now, resulting cost matrix is-

 

 

Now, we will reduce this matrix and will find out the cost of node-5.

 

Perform row reduction-

 

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

 

Performing this, we obtain the following matrix which is now row reduced-

 

 

Perform column reduction-

 

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

 

Thus, this matrix is already column reduced.

Finally, this matrix is now completely reduced as it is row reduced as well as column reduced.

 

Now, Cost of node-5 is calculated as-

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

Cost(5) = 25 + (13 + 8) + 

Cost(5) = 

 

Choosing to go to vertex-D: Node-6 (Path A → C → D)

 

  • From the reduced matrix of step-02, M[C,D] = 
  • Set row-C and column-D to 
  • Set M[D,A] = 
  • Now, resulting cost matrix is-

 

 

Now, we will reduce this matrix and will find out the cost of node-6.

 

Perform row reduction-

 

  • We can not reduce row-1 as all elements are 
  • There is no need to reduce row-2
  • We can not reduce row-3 as all elements are 
  • We can not reduce row-4 as all elements are 

 

Thus, this matrix is already row reduced.

 

Perform column reduction-

 

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

 

Thus, this matrix is already column reduced.

Finally, this matrix is now completely reduced as it is row reduced as well as column reduced.

 

Now, Cost of node-6 is calculated as-

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

Cost(6) = 25 + 0 + 0

Cost(6) = 25

 

Thus, we have-

Cost(5) =  (for Path A → C → B)

Cost(6) = 25 (for Path A → C → D)

We will 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

 

Step-04:

 

Now, we will explore the vertex B from node-6.

We will start with the cost matrix at node-6 which is-

 

Cost(6) = 25

 

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] = 
  • Now, resulting cost matrix is-

 

 

Now, we will reduce this matrix and will find out the cost of node-7.

 

Perform row reduction-

 

  • We can not reduce row-1 as all elements are 
  • We can not reduce row-2 as all elements are 
  • We can not reduce row-3 as all elements are 
  • We can not reduce row-4 as all elements are 

 

Perform column reduction-

 

  • We can not reduce column-1 as all elements are 
  • We can not reduce column-2 as all elements are 
  • We can not reduce column-3 as all elements are 
  • We can not reduce column-4 as all elements are 

 

Thus, this matrix is already column reduced.

Finally, this matrix is now completely reduced as it is row reduced as well as column reduced. All the entries have become ∞.

 

Now, Cost of node-7 is calculated as-

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

Cost(7) = 25 + 0 + 0

Cost(7) = 25

Thus,

Optimal Path is: A → C → D → B → A with cost = 25 units

 

To gain better understanding of how to solve Travelling Salesman Problem Using Branch and Bound Approach,

Watch this Video

 

Download the handwritten notes of “How to solve Travelling Salesman Problem Using Branch and Bound Approach” here-

Get more notes and other study material of Design and Analysis of Algorithms (DAA).

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary
Travelling Salesman Problem | Branch and Bound
Article Name
Travelling Salesman Problem | Branch and Bound
Description
In this article, we will learn how to solve Travelling Salesman Problem using Branch and Bound Approach. In Travelling Salesman Problem, you are given a set of cities and distance between every pair of vertices, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting city.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-