Question

# Consider a TSP case with 9 cities to be visited (starting from D and returning to...

Consider a TSP case with 9 cities to be visited (starting from D and returning to D). Using the distance matrix is provided below, use the nearest neighborhood heuristic to find the minimum distance route.

Distances

 D 1 2 3 4 5 6 7 8 D 0 61 42 22 50 45 32 57 30 1 61 0 21 62 80 91 32 76 82 2 42 21 0 41 61 71 20 71 67 3 22 62 41 0 28 30 41 78 51 4 50 80 61 28 0 22 67 106 76 5 45 91 71 30 22 0 71 100 64 6 32 32 20 41 67 71 0 51 50 7 57 76 71 78 106 100 51 0 41 8 30 82 67 51 76 64 50 41 0

a. D-3-4-5-8-7-6-1-2-D (D-3-4-2-1-6-8-7-5-D also accepted)

b. D-1-2-3-4-5-6-7-8-D

c. D-5-3-6-4-2-1-7-8-D

d. D-2-7-4-8-5-1-2-D

SOLUTION:

Given that,

Consider a TSP case with 9 cities to be visited ( starting from D and returnig to D).

To find the minimum distance rout by using the nearest neighborhood heuristic:

DISTANCES:

 S.NO From Node Un-visited nearest neighbor Distances 1 D 3 22 2 3 4 28 3 4 5 22 4 5 8 64 5 8 7 41 6 7 6 51 7 6 2 20 8 2 1 21 9 1 D 61 10 Total distances 330

So, the minimum rout using the nearest neighborhood algorith will be:

D-3-4-5-8-7-6-2-1-D .

--------------------------------------- O --------------------------------------

Please give a rating for this solution, THANK YOU.

#### Earn Coins

Coins can be redeemed for fabulous gifts.