Page 169 - DCOM303_DMGT504_OPERATION_RESEARCH

Operations Research

Notes 4. Modified Matrix – 2.
To
From 1 2 3 4 5
I - 0 1 0 0
II 0 - 0 0 1
III 2 2 - 6 0
IV 0 0 2 - 3
V 2 0 0 6 -

The routes chosen for journey are:
Alternative - I Alternative - II
From To From To

I 2 I 4
II 4 II 1
III 5 III 5
IV 1 IV 2
V 3 V 3
Note: In both the solutions, there is looping, Hence, it is not an optimum solution to travelling
salesman problem. Hence, it is to be improved further.

8.5.1 Steps to Resolve Looping in Travelling Salesman Problem

1. Choose the next minimum uncovered element in the reduced matrix. If there are more
than one such numbers, all the possible alternatives are to be tried until an unique optimum
solution is found out.
2. Check whether looping is present in modified matrix after trial assignment. Modified
matrix having no looping is an optimum solution.

Did u know? The TSP has several applications even in its purest formulation, such as
planning, logistics, and the manufacture of microchips. Slightly modified, it appears as a
sub-problem in many areas, such as DNA sequencing. In these applications, the concept
city represents, for example, customers, soldering points, or DNA fragments, and the
concept distance represents travelling times or cost, or a similarity measure between
DNA fragments. In many applications, additional constraints such as limited resources or
time windows make the problem considerably harder.

Example: A travelling sales man has to visit 5 cities. He wishes to start form a particular
city visit each city once and then return to his starting point. The travelling time (in hours) for
each city from a particular city is given below:

164 LOVELY PROFESSIONAL UNIVERSITY