TSP Example

Q2.A salesman has to visit 5 cities the distance between the 5 cities are as follows:

                             To City
                          A         B         C         D           E

From City   A[infi         7            6          8            4
                   B 7         infi            8          5            6
                   C 6           8           infi         9            7
                   D 8           5            9        infi            8
                   E  4           6            7          8           infi]

If the sales man starts from city A and has to come back to his starting point which route should he select so that the total distance covered is minimum.

Soln:'

If we solve this problem, the final distance matrix will be.

           A             B               C              D           E
A      infi              3                0              4             0
B       3              infi                1              0             1
C       0               1                infi             2             0
D       4               0                  2            infi            3
E        0               1                  0             3           infi

The travel is given as A-->E-->B-->D-->C-->A

Distance=4+5+6+9+6
             =30 Km

Travelling Salesman Problem (TSP)

Assuming the salesman has to visit 'n' cities.He wishes to start from a particular city visit each city once and return to his starting point.His objective is to select a sequence in which the total travelling time is minimized.

MATHEMATICAL FORMULATION:
Let Cij be the distance or time or cost of going from city 'i' to city 'j'.
Let the decision variable Xij=1, if the salesman travels from city'i' to city 'j', otherwise 0.
The objective is to minimize the travelling time.