Question

Cheshire Plants is delivering the monthly supply of their fine product to their seven customers. The distances in miles between the customers are shown in the table and, wishing to be as efficient as possible, the driver would like to find the shortest route that takes her from the starting point A to every customer and then back to the starting point. Use the nearest neighbor heuristic to identify a route that would minimize the distance traveled. Show work

From/To	A	B	C	D	E	F	G	H
A	0	288	231	210	89	216	118	264
B	62	0	51	166	211	36	223	270
C	176	196	0	126	90	235	190	83
D	210	216	86	0	171	46	276	125
E	223	93	242	160	0	238	104	139
F	193	44	73	79	137	0	50	196
G	255	275	241	116	41	293	0	164
H	271	31	33	79	52	107	225	0

Answer 1

Solution:

Using the Nearest Neighbor Heuristic, the best route is computed below with site A as the start and end location.

1) From A, the nearest site is E, therefore, the first site to visit from A is E.

2) From E, the nearest site is B, therefore, the site to visit from E is B.

3) From B, the nearest site is F, therefore, the site to visit from B is F.

4) From F, the nearest site is B but B has already been covered, second nearest site is G, therefore, the site to visit from F is G.

5) From G, the nearest site is E but E has already been covered, second nearest site is D, therefore, the site to visit from G is D.

6) From D, the nearest site is F but F has already been covered, second nearest site is C, therefore, the site to visit from D is C.

7) From C, the nearest site is H, therefore, the site to visit from C is H.

8) Now that all the sites have been covered, from H the driver will come back to site A.

The Route to follow using Nearest Neighbor Heuristic is:

A - E - B - F - G - D - C - H - A

Total distance travelled is calculated as below:

The total number of miles travelled using this route is calculated as below:

A to E = 89

E to B = 93

B to F = 36

F to G = 50

G to D = 116

D to C = 86

C to H = 83

H to A = 271

Total distance travelled = 89 + 93 + 36 + 50 + 116 + 86 + 83 + 271

Total distance travelled = 824 miles