TSP Example

Q1.A Travelling salesman has to visit 5 cities the cost of going from one city to another is shown below.

                    A        B        C        D        E
From  A [  infi         4         10      14        2
City    B     12       infi         6        10        4
          C     16       14         infi        8       14
          D      24       8          12        infi     10
          E        2        6           4        16      infi ]

Soln:

STEP I:
Process row wise

[ infi   2      8      12      0
   8    infi     2       6      0
   8     6     infi      0      6
  16    0      4      infi     2
   0     4      2      14    infi ]

STEP II:
 Process column wise. Strike out either horizontally / vertically in such a way that maximum number of zeros are covered.

[ infi     2      6     12     0
  8      infi      0      6     0
  8        6     infi     0     6
 16       0      4     infi    2
  0        4      0     14   infi ]

STEP III:
Number of Straight lines N=5
Order of matrix n=5
N=n. Therefore the optimal solution is

                   A             B               C             D           E
A     [       infi               2                 6           12            0
B              8               infi                 0             6            0
C              8                 6                infi            0            6
D             16                0                 4            infi           2
E               0                 4                 0             14         infi ]

A-->E; E-->A          B-->C;C-->D;D-->B

A-->E-->A;
B-->C-->D-->B     There is a break in the travel.

STEP IV:
When this situation occurs find the minimum value from the above cost matrix. Here it is  2 cancel this value and the other minimum value '0' in that row.

                   A             B               C             D           E
A     [       infi               2                 6           12            0
B              8               infi                 0             6            0
C              8                 6                infi            0            6
D             16                0                 2            infi           2
E               0                 4                 0             14         infi ]

A-->B;   B-->C;   C-->D;  D-->E;  E-->A

therefore the optimum sequence is A-->B-->C-->D-->E-->A
                                                    4+6+8+10+2
cost=Rs.30