The Wall Street Journal reports how to find the shortest path to visit all 30 Major League Baseball stadiums in 35 days. Of course, this is a constrained Traveling Salesman Problem (TSP) with additional constraints that take the scheduling of home games at each stadium into account. Unfortunately, the TSP was not mentioned by name in the article. The distances between the stadiums reflect driving time and additional rest time (unless you’re a robot, you need rest before you drive). The model was built and solved by Ben Blatt of the Harvard Sports Analysis Collective using “linear programming.” Last time I checked, the TSP was a discrete problem, and those of you who study the TSP will have to let me know if there are linear programming based heuristics that can be used.
Blatt has not been enjoying his optimal tour. Efficiency may be beautiful, but it’s not always fun.
Are you using OR models to plan a vacation this summer?
Punk Rock Operations Research 
June 7th, 2011 at 2:40 pm
I’ve thought just briefly about how I would formulate this problem, using a minimum cost flow on a circulation network with some side constraints. Here is the idea. (1) Create a node for each baseball game (or double-header) played. This is a sort of “time-space” network, where the time dimension is discretized into the days of the baseball season. (2) Create a directed arc between each game node and the first subsequent game node in a different city that can be reached feasibly by driving. (3) Create a single external node, connected to and from each game node.
To minimize the trip duration (in days) required to visit every ballpark, set the cost on each arc as its duration in days, and find a unit circulation flow such that the flow out and into the external node is one with a side constraint that the sum of the flow out of game nodes at each distinct stadium is exactly one (so that you leave each stadium once). This is a network flow problem with flow bundle constraints, but should be relatively easy to solve to optimality with off-the-shelf integer programming software. You could also attempt to instead minimize driving distance.
I might actually make this into a homework problem…
June 8th, 2011 at 6:52 am
The problem is actually modeled as a MIP model which is available below:
Click to access shortest_possible_baseball_road_trip1.pdf
June 8th, 2011 at 7:14 am
Thanks!