USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

Routing Problems

There are various types of routing problems which occurs in a network. The most widely discussed problem is the 'Travelling Salesman Problem (TSP)'. Suppose there is a network of n cities and a salesman wants to make a tour i.e., starting from a city 1 he will visit each of the other (n - 1) cities once and will return to city 1. In this tour the objective is to minimize either the total distance travelled or the cost of travelling by the salesman.

 

(a) Mathematical Formulation

 

Let the cities be numbered as 1, 2, .. . , n and the distance matrix as follows:

Generally an infinity symbol is placed in the principal diagonal elements where there is no travelling. So dij represents the distance from city i to city j (i * j). If the cost of travelling is considered then D is referred as cost matrix. It is also to be noted that D may be symmetric in which case the problem is called 'Symmetric TSP' or asymmetric in which case the problem is called 'Asymmetric TSP'.

 

Let us define the decision variables as follows :

 

xij = 1, if he travels from city I to city j

0, otherwise

where i, j = 1, 2, ... , n

 

Then the linear programming formulation can be stated as follows :

Minimize

xij = 0 or 1 for all i and j = 1, 2, .. . , n

and                                          x = (xij) is a tour.

 

The above problem has been solved with various approaches e.g., Graph Theoretic Approach, Dynamic Programming, Genetic algorithm etc.

 

The above problem looks like a special type of Assignment problem. Consider a 4 x 4 assignment problem and a solution as 1 - 4, 2 - 3, 3 - 1, 4 - 2 which can also be viewed as a tour i.e., 1 - 4 - 2 - 3 - 1. If the solution is 1 - 4, 2 - 3, 3 - 2, 4 - 1 then this consists of two sub-tours 1 - 4 - 1, 2- 3 - 2.

 

Here one algorithm known as 'Branch and Bound' algorithm is described below :

 

(b) Branch and Bound Algorithm for TSP

 

  1. Ignoring tour, solve [D] using Hungarian Algorithm. The transformed matrix is denoted as [D0]. If there is a tour, stop, else go to next step while storing the solution in a node denoted by TSP.

 

  1. Calculate the evaluation for the variables in [D0] whose values are zero i.e., xij = 0 where evaluation means the sum of smallest elements of the i-th row and the j-th column excluding the (i,j )th entry.

 

  1. Select the variable with highest evaluation, say xij. If there is a tie, break it arbitrarily. The variable xij is called the branching variable.

 

  1. Create a left branch (TSP1) with xij = 0. To implement this put dif = oo in [D0l i.e., travelling from city i to city j is restricted.

Set [D] = transformed [D0] and goto step (i).

 

  1. Create a. right branch (TSP2) with xij = 1 . This means the salesman must visit city j from city i. To implement this take [D0] of the parent node. Delete the i-th row and j-th column and put dji = ∞ (to prevent a sub tour).

Set [D] = transformed [D0l and goto step (i).

 

Note.

 

(a)   There may be a situation arises in step (i) where further solution is not possible then we shall stop that branch.

(b)  There may be multiple tours. We shall select the tour with minimum distance or travelling cost.

(c)   Calculate total distance (TD) from the given [D] which increases with the level of the tree.

 

Example 6. Solve the following travelling salesman problem using branch and bound algoritrm.

Solution. Let us apply the Hungarian Algorithm on [D) and obtain the following matrix :

The solution is 1 - 2, 2 - 1 , 3 - 4, 4 - 3. i.e., there exists two sub tours 1 - 2 - 1, 3 - 4 -3.

 

The total distance (ID) = 3 + 3 + 2· + 2 = 10 units.

 

Then we have to calculate the evaluations for the variables having the value zero in [D0] .

 

 

 

Variable                      Evaluation

X12                             2 + 3 = 5

X21                             2 + 3 = 5

X34                             3 + 2 = 5

X43                              3 + 2 = 5

 

Since there are ties in the values, let us select x12 as branching variable.

 

Sub problem TSPl

 

Let x12 = 0 ::::> Put d12 = oo in [D0 ] and obtain

The solution is 1 - 4, 2 - 1, 3 - 2, 4 - 3 i.e., 1 - 4 - 3 - 2 - 1 which is a tour and TD = 5 + 3 + 5 + 2 = 15 units from [D].

 

Sub problem TSP2

 

Let x12 = 1 => Delete row 1 and column 2 from [D0] and put d21 = ∞ to prevent subtour. The resultant transformed matrix is obtained as follows :

The solution is 1 - 2, 2 - 3, 3 - 4, 4 - 1 i.e., 1 - 2 - 3 - 4 - 1 which is a tour and TD = 3 + 5 + 2 + 5 = 1 5 units from [r>]. The above calculations is presented in the following tree diagram :

Since there are two tours with same TD, the given problem has two solutions.

 

PROBLEMS

 

Solve the following travelling salesman problems using branch and bound algorithm :

1.

2.

3.

ANSWERS

 

  1. 1 - 4 - 3 - 2 - 1 , TD = 1 9 units.
  2. 1 - 4 - 5 - 3 - 2 - 1 , TD = 22 units.
  3. 1 - 3 - 5 - 4 - 2 - 1 and 1 - 2 - 4 - 5 - 3 - l, TD = 1 6 units.