Helping Harvest is a food bank in the Greater Miami area that collects food donations from local grocery stores and transports them back to a distribution center for sorting and transfer to local food kitchens that feed needy clients. Tight budgets and environmental concerns require that both fuel and driver resources be used sparingly. Thus, Mr. Vivek, Helping Harvest’s general manager, would like to ensure that collection vehicles are routed most efficiently. The table below provides the driving distance in miles among the depot (the distribution center from where truck begins and ends its route) and the five stores that donate food. From/To Depot Store A Store B Store C Store D Store E Depot – 10 24 60 40 26 Store A 10 – 34 46 35 44 Store B 24 34 – 48 20 15 Store C 60 46 48 – 15 35 Store D 40 35 20 15 – 12 Store E 26 44 15 35 12 – Currently, the Helping Harvest truck travels the following route Depot–Store A–Store B–Store C–Store D–Store E–Depot. a. Use the NN heuristics to find a shorter route and calculate the savings in miles traveled per day. b. The manager at Store B would like the Helping Harvest truck to pick up from her store as early as possible. How many miles does the constraint of visiting Store B first add to the route selected in part a?

Royal Seafood delivers fresh fin and shellfish to specialty grocery stores in the state of Oregon. The company packs a delivery truck in Corvallis and then drives in one single route to its five customers spread throughout the state. The distances in miles between all locations may be found in the table below. From/To Corvallis (A) Roseburg (B) Bend (C) Baker (D) Lakeview (E) Burns (F) Corvallis (A) – 225 234 233 169 189 Roseburg (B) 225 – 159 244 265 168 Bend (C) 234 159 – 253 246 197 Baker (D) 233 244 253 – 153 287 Lakeview (E) 169 265 246 153 – 171 Burns (F) 189 168 197 287 171 – a. Propose an efficient route by using the NN heuristic with Corvallis as the starting city. What is the total distance traveled? b. Use the NN heuristic to calculate five routes, each starting from one of Royal Seafood’s customer’s location. What is the best route for Royal Seafood?