Major League Baseball Roadtrip

[fredbow]

I'm planning a road trip to all 30 major league parks and trying to figure out the shortest route I can take to hit them all.

Here's what I have so far:
Denver
Minneapolis
Milwaukee
Chicago
Kansas City
St. Louis
Cinncinati
Pittsburg
Cleveland
Detroit
Toronto
Boston
New York
Baltimore
Philadelphia
Washington DC
Atlanta
Miami
Tampa Bay
Houston
Dallas
Phoenix
San Diego
Anaheim
Los Angeles
San Francisco
Oakland
Seattle

The total mileage is 9,744. Any ideas how to make it shorter? I would prefer to start and/or end in Boston, but this will make the trip considerably longer.

[Mark Sedenquist]

A helicopter might make it shorter... Just kidding. I would get a copy of Chris Epting's Roadside Baseball for some routing ideas.

[Boston Wrangler]

I think that this is about as short as I can get it: ~11,000 miles (measured to city centers)

Boston
New York
Philadelphia
Baltimore
Washington DC
Miami
Tampa Bay
Atlanta
Houston
Dallas
Phoenix
San Diego
Anaheim
Los Angeles
San Francisco
Oakland
Seattle
Denver
Kansas City
Minneapolis
Milwaukee
Chicago
St. Louis
Cinncinati
Detroit
Toronto
Cleveland
Pittsburgh
Boston

Edit: I think I misread that you want to start AND end in Boston. OK, if you make it a one-way trip, you can make it considerably shorter. Let me try that.

[Boston Wrangler]

OK I got it shortened:

Denver
Kansas City
Minneapolis
Milwaukee
Chicago
St. Louis
Cinncinati
Detroit
Toronto
Cleveland
Pittsburgh
Boston
New York
Philadelphia
Baltimore
Washington DC
Miami
Tampa Bay
Atlanta
Houston
Dallas
Phoenix
San Diego
Anaheim
Los Angeles
San Francisco
Oakland
Seattle

That is 1,300 miles shorter than my previous try, but it ends up equalling what you already figured (9,700).

[Mark Sedenquist]

That is 1,300 miles shorter than my previous try, but it ends up equalling what you already figured (9,700).

Wow, this process boggles my mind. How long did it take you to work out the mileage and route?

Mark

[Robert Schaller]

FredBow,
MS Streets and Trips has an "optimizing" feature -- given enough time (it's a laborious process, seemingly), it will attempt to find the shortest, most efficient route. It came very close to what Boston Wrangler already found -- with a couple of slight variations. If starting and ending in Boston is important to you, I'd suggest that a 1,200 mile difference really isn't very much! For that route, Streets and Trips figured 11,796 miles -- Boston Wrangler figured 11,000 so that saves a few miles -- I'd go with that routing as I doubt you'll do much better. Bob

[Midwest Michael]

Keep in mind, shorter doesn't mean less time in this case. It'd be great if you could see a game in Minneapolis one night, Milwaukee the next, and spend the next two in Chicago (as an example), however it's almost certain that one (if not more) of those teams will be on the road during the time you'll want to be there.

You also need to keep in mind day/night game issues. A saturday game in Cincinatti followed by a sunday in pittsburgh sounds fine, unless its a night game in Cinci... getting done at 10 p.m., followed by a 4 hour drive, and a day game at the next afternoon. It can be done, but you won't get much sleep or have all that much fun.

Baseball trips are a blast, but they are by their nature, very inefficent in terms of mileage. My Suggestion, prioritize areas that are more remote (Seattle and Colorado in particular), find times where relatively close teams are at home at the same time (Houston and the Rangers) be willing to backtrack in areas where there are lots of parks in relatively close proximity (Boston to D.C., Detroit-Toronto-Cleveland-Pittsburgh-Cinci), and give yourself a few days off to have fun and avoid ballpark burnout!

[Nicholas Mosher]

I'd love to visit all the MLB ballparks... just make sure you throw beer at the Yank's outfielders, and cheer for the Red Sox!

[Chuck C]

FredBow,
MS Streets and Trips has an "optimizing" feature -- given enough time (it's a laborious process, seemingly), it will attempt to find the shortest, most efficient route.

Your parenthetical comment there may be more significant than you know. This is actually a famous problem in computer science known as the "travelling salesman problem." It turns out that many problems can be reduced to this one, or problems very similar to it, so an algorithm for solving it has many applications beyond simply finding the shortest route covering a number of cities.

It is widely believed--but not proven--that any program which finds an exact solution to the traveling salesman problem requires what computer scientists call "exponential time."

(That is, the time required to find the solution doubles each time you add some fixed number of cities. If you have a program that takes twice as long to find a solution for 40 cities as it does for 30 (say, 10 minutes compared to 5 minutes), and twice again as long to find a solution for 50 (20 minutes) as it does for 40, and still twice more to find a solution for 60 (40 minutes) as it does for 50, that is a program that takes exponential time. If you had a different program that let you add more cities before you doubled the running time, but was still a fixed number you had to add to double the time--say, 30 cities takes 5 minutes, 50 cities takes 10 minutes, 70 cities takes 20 minutes, 90 cities takes 40 minutes--that's a better program, but it's still one which takes exponential time.)

If any algorithm is found which could solve the travelling salesman problem in less than exponential time, it would have wide-ranging implications in computer science, because it would mean that a large number of problems which are also widely thought to require exponential time would not.

A brute-force approach--calculate the length of every possible route among the cities, and see which is the shortest--becomes impractical even around 20 or so cities. There are better algorithms out there, but all known algorithms which find the exact solution still take exponential time. One case of a 15112-city problem, solved in 2001, required 22.6 years worth of processor time.

Alternately, algorithms are known which give approximate solutions (that is, they can't guarantee that the route produced is the shortest route, but can guarantee that the route produced is no more than, say, 2% longer than the shortest route) in polynomial time (i.e., better than exponential time). The Wikipedia article on the problem notes that these approximation algorithms can find solutions for millions of cities in "a reasonable time."

So yes, finding the shortest route among a number of cities is a seemingly laborious process--and not just seemingly so to you and me, but to the brightest minds in computer science right now. If anyone discovered a process which was less laborious (took less than exponential time), it would be a very significant result in computer science. A proof that any process for finding the solution requires exponential time would also be quite significant.

Sorry for the digression into computer science, but I couldn't resist the opportunity to talk about what I find a fascinating problem!

[Mark Sedenquist]

Chuck,

That was far more explanation than I dreamed was possible. But still quite fascinating!

What do you do professionally?

Mark