how to visit all 30 MLB baseball stadiums in a record amount of time

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?

 

Advertisements

3 responses to “how to visit all 30 MLB baseball stadiums in a record amount of time

  • Alan Erera

    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…

  • Laura McLay

    Thanks!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: