Answer to November 29, 2004 Problem of the Week

Mr. Pleacher and his wife want to take a trip to visit his brother, his parents, and each of their children.

Mr. Pleacher and his wife live in Stephens City, VA. (SC on the map below)

Mr. Pleacher's brother lives in Leitchfield, KY. (L on the map)

Mr. Pleacher's parents live in Owensboro, KY. (O on the map)

Mr. Pleacher's daughter Elizabeth and her family live in Ponte Vedra Beach, FL. (PVB on the map)

Mr. Pleacher's daughter Sarah and her family live in Fort Collins, CO. (FC on the map)

Mr. Pleacher's son Michael and his wife live in Portland, ME. (P on the map)

The distances between the cities are given below:

Stephens City to Portland is 615 miles
Stephens City to Ponte Vedra Beach is 758 miles
Stephens City to Fort Collins 1,639 miles
Stephens City to Leitchfield is 588 miles
Stephens City to Owensboro 651 miles
Owensboro to Ponte Vedra Beach is 744 miles
Owensboro to Fort Collins is 1,111 miles
Owensboro to Leitchfield is 65 miles
Owensboro to Portland is 1,188 miles
Ponte Vedra Beach to Portland is 1,280 miles
Ponte Vedra Beach to Fort Collins is 1,824 miles
Portland to Fort Collins is 2,070 miles

Using the data above, help Mr. Pleacher and his wife plan a roundtrip to visit each relative without passing through any city more than once (except the return home to Stephens City).

You may use only the routes indicated on the map -- there is only one road into Leitchfield and one road out (you must go through Stephens City or Owensboro to get there).

Find the shortest path.

Solution to the Problem:

The shortest paths are:
SC - P - PVB - FC - O - L - SC
and its reverse
SC - L - O - FC - PVB - P - SC,
which are both 5,483 miles.

I used a tree diagram to examine all possible paths. Then I set up a table to find the shortest path(s).

SC	-	P	-	FC	-	PVB	-	O	-	L	-	SC	=	5,906 miles
SC	-	P	-	PVB	-	FC	-	O	-	L	-	SC	=	5,483 miles
SC	-	L	-	O	-	PVB	-	P	-	FC	-	SC	=	6,386 miles
SC	-	L	-	O	-	PVB	-	FC	-	P	-	SC	=	5,906 miles
SC	-	L	-	O	-	P	-	PVB	-	FC	-	SC	=	6,584 miles
SC	-	L	-	O	-	P	-	FC	-	PVB	-	SC	=	6,493 miles
SC	-	L	-	O	-	FC	-	P	-	PVB	-	SC	=	5,872 miles
SC	-	L	-	O	-	FC	-	PVB	-	P	-	SC	=	5,483 miles
SC	-	PVB	-	P	-	FC	-	O	-	L	-	SC	=	5,872 miles
SC	-	PVB	-	FC	-	P	-	O	-	L	-	SC	=	6,493 miles
SC	-	FC	-	P	-	PVB	-	O	-	L	-	SC	=	6,386 miles
SC	-	FC	-	PVB	-	P	-	O	-	L	-	SC	=	6,584 miles

So, paths #2 and #8 above have the least mileage of 5,483 miles, a savings of 1,101 miles over routes #5 or 12.

Correctly solved by:

1. John Funk	Ventura, California
2. Henry Woodward	Columbus, Georgia
3. Jasmine Gonzalez and Leanna Thammavongsa	Charlton, Massachussetts
4. Trey Mason	Winchester, Virginia
5. Sharina Broughton	Old Dominion University, Norfolk, Virginia
6. Per BjÖrkil	Tullängskolan, Örebro, Sweden
7. Viktor Logrell	Tullängskolan, Örebro, Sweden
8. Bahadir Güngör	Tullängskolan, Örebro of Sweden
9. Jonas Sutinen	Tullängsskolan, Örebro, Sweden
10. Gustav Nilsson	Tullängsskolan, Örebro, Sweden
11. Jim Kennedy	Limerick, Ireland
12. Nate Troup	Arlington, Virginia
13. David & Judy Dixon	Bennettsville, South Carolina
14. Jeffrey Gaither	Winchester, Virginia
15. Jonathan Haxxor	Tullängskolans, Örebro, Sweden
16. Daniel Kvist	Tullängskolan, Örebro, Sweden
17. Erik Hultgren	Tullängskolan, Örebro, Sweden
18. James Alarie	University of Michigan -- Flint, Flint, Michigan
19. Erik Ekman	Tullängskolan, Örebro, Sweden
20. Clay Thomas	----------
21. Cameron S.	Columbus, Georgia
22 Ann Norman	Columbus, Georgia
23. Anders Johansson	Tullängsskolan, Örebro, Sweden
24. Linda Axelsson	Tullängsskolan, Örebro, Sweden
25. Joanna Sturk	Tullängsskolan, Örebro, Sweden
26. Stehr Ako	Tullängskolan, Örebro, Sweden