A variant of the traveling salesman problem

Josh Robbins attempts to see a baseball game in all thirty major league baseball parks in 26 days.

Yes, you read that right.

And Major League Baseball doesn't make that easy. As you can guess, he has to see two games in one day four times -- but in markets with two teams (New York, Chicago, San Francisco/Oakland, Los Angeles) they try to schedule the two teams to be on the home at opposite times. That makes sense, because that way if you think "I want to see a baseball game today" you've got a good chance.

In fact, his four doubleheaders are Dodgers-Padres (which apparently was a bit of a tight squeeze, since the Dodgers went into extra innings), Yankees-Mets (that one should be easy; every few years the Mets and the Yankees play a game at one park in the afternoon and at the other park the same night; they're doing it today); Phillies-Nationals (which will be tight even if the games go the ordinary length; they start six hours apart, average game length is three hours or so, and the cities are two and a half hours apart with no traffic -- oh, and he's doing it on a Thursday); Cubs-Brewers.

My point is that 25 days might be possible -- but probably not. Most baseball games are scheduled for around 1 PM or around 7 PM, and games last three hours, to see two in one day requires the sites to be no more than three hours apart. The pairs that are doable in one day are probably:

Mets-Yankees, Mets-Phillies, Yankees-Phillies
Phillies-Orioles, Phillies-Nationals, Orioles-Nationals
Dodgers-Padres, Padres-Angels, Angels-Dodgers
White Sox-Cubs, White Sox-Brewers, Cubs-Brewers
Giants-A's

but of course one can do only one from each row, so it's only possible to double up on five days. Basically, this is the problem of looking for the largest matching in the graph that I defined above, where the edges are teams within about three hours' driving distance of each other.

(Oddly enough, each two-team market (and yes, I know, Baltimore and Washington may or may not be the same market) seems to have another team a couple hours away. In two cases that team is the Phillies. As you may know, this blog likes the Phillies.)

So 25 is theoretically possible, if the Scheduling Gods worked in one's favor -- but I'd be scared to even look at the schedules to try and figure it out. And what happens if there's a rainout?

As a problem in actually scheduling things, the other tricky part is that Denver really isn't near any other team. And Robbins' schedule had him at a 7:05 game in San Diego, followed by a 1:05 game in Denver the next day -- but Denver's a time zone to the east of San Diego, so that's seventeen hours between starts. Fourteen hours driving time. For 1,078 miles.

For some other variants of the traveling salesman problem which involve the road network, see Barry Stiefel's 50 states in a week's vacation (driving, with flights to Alaska and Hawaii) and 21 states in one day. The last one cheats a bit -- it's a 26-hour day, since he started in the Eastern time zone during daylight savings time (GMT-4), and did the trip on a day when we went back to standard time (GMT-5) and then crossed into the Central time zone (GMT-6). The difference here is that you only have to enter each state instead of reaching a point.

Oh, and I feel obliged to point out that I find the meme of going on a long road trip this summer because "this is the last summer it'll ever be possible" kind of stupid. (Not that anybody here brought it up.)

Edited (Saturday morning): Google Maps says Cleveland to Detroit can be driven in 2:46. I didn't realize they were that close together. They'd be even closer if someone built a bridge across Lake Erie.
(Saturday afternoon): Cleveland to Pittsburgh in 2:18. I'll admit the reason I forgot this one is that mentally I think of Pittsburgh as being in the same state as me and Cleveland as not being in it, so they must be far apart. This is despite the fact that I live about five miles from New Jersey.
Anyway, you could shave off yet another day by combining the Indians with either the Pirates or the Tigers.

what good is an "average"?

Ugly Airline Math: Planes Late, Fliers Even Later -- from the July 5 New York Times.

Basically, airlines count the "average delay" by how late the average plane is. But what really matters is how late the average passenger is, which is a different problem because of connecting flights. If you're scheduled to have a ninety-minute layover and your incoming flight is forty minutes late, then suddenly your connection is tighter but you'll be okay, and moreover you get to your destination at the same time you would have otherwise. But if your incoming flight is two hours late, then you have to get on the next flight -- which means you'll be far more than two hours delayed.

The average delay for planes is 15 minutes; for passengers, 25.

But is this statistic even meaningful? The article talks of people who were, say, 12 or 24 hours late to their destinations. The mean isn't meaningful for these sorts of distributions, which are very skewed. Sure, it's easy to calculate. But if I were a passenger, and I had to pick one number to know about an airline's performance, it wouldn't be the mean delay. I'd want to know what percentage of their passengers get where they're going more than, say, an hour late. Or which percentage get there not on the flight they were originally ticketed on. (The same flight number on the next day doesn't count as the "same flight", although I bet they'd find a way to make it count.)

But whatever you do, the airlines will probably find a way to game the system so that they look good under the performance metric in question without actually satisfying their customers. This is because people will demand some simple metric they can understand, even though I suspect that any single number that measures an airline's performance would be something like, say, Google's PageRank -- impossible for the layperson to calculate but still remarkably useful.