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 
Group of answer choices
a. D34587612D (D34216875D also accepted)
b. D12345678D
c. D53642178D
d. D2748512D
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  Unvisited 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:
D34587621D .
 O 
Please give a rating for this solution, THANK YOU.
Get Answers For Free
Most questions answered within 1 hours.