Sweet Action, Inc is making the daily cupcake run across the Oklahoma City metropolitan area. They have seven customers and have identified the driving distance (in miles) between each pairwise combination as shown in the table
One-way streets and various construction projects affect driving distances such that the distance from one to the other may not be same depending on which site is the starting point. Identify the most energy efficient route that begins at Sweet Action headquarters (SA) and visits each customer once before returning to headquarters.
From/To SA Bosco's Champion Damron Enumclaw Luther Jones Heidi
SA 0 9 97 17 22 34 55 71
Bosco's 14 0 99 29 20 39 84 53
Champion 63 8 0 90 96 89 66 78
Damron 98 90 29 0 46 88 62 13
Enumclaw 27 88 94 81 0 49 53 35
Luther 91 95 62 91 19 0 73 91
Jones 87 2 27 69 11 4 0 25
Heidi 61 31 58 13 15 92 44 0
Starting at site SA, the closest site is Bosco's at 9 miles. The next legs of the journey are:
Site Bosco's to site Enumclaw = 20 miles
Site Enumclaw to site Heidi = 35 miles
Site Heidi to site Damron = 13 miles
Site Damron to site Champion = 29 miles
Site Champion to site Jones = 66 miles
Site Jones to site Luther = 4 miles
Site Luther to site Sweet Action = 91 miles
The total distance driven is 267 miles.