On Thursdays, Traxis Consolidated delivers liquid oxygen to its industrial customers in northern Michigan. Table 1 provides the driving time in minutes among all customers and the Traxis liquid oxygen depot location.

A. Using the depot? (A) as the beginning ? location, create a route using the Nearest Neighbor heuristic. What is the total driving time using this? route?

The route is __________ with total driving time of_____ minutes. ?(Enter your response as a whole? number.)

B.?Use the Nearest Neighbor heuristic to calculate seven? routes, each starting from one of? Traxis's customer's locations. What are your? conclusions?

The shortest route is ______ having the driving time of _____ minutes. Note that using the same sequence of cities we can start the route at any one of them and travel the same total distance.

?

?

A [depot] Love D E F GH A [depot] 84 32 29 23 B 30 27 51 45 D E F G 67 33 46 18 D H 23 1 45 52 2 7 18 - Nearest Neighbor (NN) heuristic consists of the following steps: 1. Start with the city that is designated as the central location. Call this city the start city. Place all other cities in an unvisited set. 2. Choose the city in the unvisited set that is closest to the start city. Remove that city from the unvisited set. 3. Repeat the procedure with the latest visited city as the start city. 4. Conclude when all the cities have been visited, and return back to the central location. 5. Compute the total distance traveled along the selected route.