Chapter 6, Problem 65E

Julie is the marketing manager for a small software company based in Boston. She is planning a sales trip to Michigan to visit customers in each of the nine cities shown on the mileage chart in $Fig.6-54$. She can fly from Boston to any one of the cities and fly out of any one of the cities back to Boston for the same price (call the arrival city A and the departure city D). Her plan is to pick up a rental car at A, drive to each of the other cities, and drop off the rental car at the last city D. Slightly complicating the situation is that Michigan has two separate peninsulas—an upper peninsula and a lower peninsula—and the only way to get from one to the other is through the Mackinaw Bridge connecting Cheboygan to Sault Ste. Marie. (There is a $3 toll to cross the bridge in either direction.)

	Detroit	Lansing	Grand Rapids	Flint	Cheboygan	Sault Ste. Marie	Marquette	Escanaba	Menominee
Detroit	$\ast$	90	158	68	280
Lansing	90	$\ast$	68	56	221
Grand Rapids	158	68	$\ast$	114	233
Flint	68	56	114	$\ast$	215
Cheboygan	280	221	223	215	$\ast$	78
Sault Ste. Marie					78	$\ast$	164	174	227
Marquette						164	*	67	120
Escanaba						174	67	*	55
Menominee						237	55	55	*

$Figure6-54$

a. Suppose that the rental car company charges 39 cents per mile plus a drop off fee of $250 if A and D are different cities (there is no charge if $\text{A }=\text{ D}$). Find the optimal (cheapest) route and give the total cost.

b. Suppose that the rental car company charges 49 cents per mile but the car can be returned to any city without a drop off fee. Find the optimal route and give the total cost.