Question

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. 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

Answer 1

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.