27 June 2008

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

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.


Barry said...

Another variant is The Santa Claus Problem. How does he get to all those millions (or billions) of houses in less in 24 hours? How many microseconds can he spend at each house? How fast does he have to travel between houses? Wouldn't friction with the atmosphere set his sleigh on fire? How much reindeer power is required to accelerate and decelerate a sleigh that quickly?
It's frightening!

Anonymous said...

I claim that 24 days is theoretically possible (where "theoretically possible" is defined as above).

From Shea or Yankee Stadium to Fenway Park is 205 miles (3:42 on Google Maps). Maybe not doable if you had 1pm and 7pm starts, but on July 27 the Mets have a home game at 1:10 and the Red Sox have a home game at 8:05, so with the 7-hour gap you could probably combine those two (and then separately combine Yankees and Phillies, and the Orioles and Nationals, as well as your other three pairs) to do thirty in 24, if the rest of the schedule worked in your favor.

Naturally you'd also need the Mets game to finish fast! It's a good thing that the Yankees @ Red Sox contest is the night game, since those games tend to go about 5 hours each.

Anonymous said...

I was sure there were more pairs - but look at how many are 4 hours apart...

I remember when the Blue Jays were good (am I old?) fans couldn't get tickets, so they'd drive to Cleveland or Detroit. I think the Tigers were closer, but Municipal Stadium was huge and could fit as many Torontoans (?) as could make it.

Anonymous said...

[color=#bb3300]Группа [url=http://dejavu-group.ru/artist.php]Дежа вю[/url] - это коллектив заслуженных вокалистов и музыкантов.
[url=http://dejavu-group.ru/about_us.php]Dejavu-group[/url]- законодатель в области музыкального сопровождения концертов, свадеб, копоративов, дней рождения, музыкальных шой программ, дней рождения, музыкальных шоу.
В копилке Музыкантов Dejavu-group около 3 тыс. произведений.
Живой звук. Поп, хиты 70-80-90-х, диско, джаз, ретро, современная музыка, европейские хиты, фоновая музыка, шансон .
Музыканты Дежа вю располагает мощной качественной аппаратурой, позволяющей заполнить приятным и плотным уху звуком как небольшое помещение (фуршет), так и огромное помещение (корпоратив до тысячи человек).

Игорь +7 916 623 4047 [/color]

Anonymous said...

[color=#bb3300]Музыканты на праздник [url=http://dejavu-group.ru/artist.php]Дежа вю[/url] - это коллектив профессиональных вокалистов и музыкантов на праздник.
[url=http://dejavu-group.ru/artist.php]Дежа вю[/url]- законодатель в области проведения и организации музыкальных мероприятий, свадеб, юбилеев.
В копилке Музыкантов Deja Vu около 3 тыс. песен.
Только живое исполнение. Поп, хиты 70-80-90-х, диско, джаз, ретро, современная музыка, европейские хиты, фоновая музыка, шансон .
Музыканты Dejavu-group располагает мощной качественной аппаратурой, позволяющей заполнить приятным уху звуком как компактное помещение (фуршет), так и большое пространство (корпоратив до тысячи человек).

Андрей +7 910 483 8294, Игорь +7 916 623 4047 [/color]

Anonymous said...

Как дела? Может-быть... есть мега предложение по[url=http://www.pi7.ru] видео[/url] порталу Думаю вам понравится

[url=http://www.pary.ws/sc.html]Скачать / Смотреть малолетку в рот - сначала растревожил Даше гланды,а потом...
aнекдот для разнообразия :)

Разговаривают две блондинки:
- Ты знаешь, я сегодня узнала, что такое куннилингус!
-??? и что это?
- Это как минет, только наооборот!
- Подожди, это что, в НЕГО дуть что ли надо?!

Я 5 часов блуждала по сети, пока не вышела на ваш форум! Думаю, я здесь останусь надолго!
прошу прощения за опечатки.... очень малеьнккя клавиатура у PDA!


Anonymous said...

Не знаеш который час в этом городе? мм.. есть cупер предложение по[url=http://www.pi7.ru] видео[/url] порталу Думаю вам понравится

[url=http://www.pi7.ru]он подошел сзади и начал ласкать мою киску[/url]
[url=http://www.pi7.ru]кино [/url]
aнекдот для разнообразия :)

Парень склоняет девукшу к близости:
- До сважьбы нельзя...
- Ничего, до свадьбы заживет

Я 6 часов бдуждала по сети, пока не вышела на ваш форум! Думад, я здесь останусь надолго!
прошу прощения за опечатки.... очень маленькая клавиатуна у PDA!


Anonymous said...

Подумали с мужем о подарочках на день варении младшему сыну, ему три года, разные-машинки-конструкторы у него есть много, ему нравится мышка Тич. Я выискала типа подобной игрушки, только мишку http://mishkiland.ru/subcategory_item.php?id=600 , кто-либо покупал такого? Стоит покупать? Или порекомендуйте что-либо еще. Не дайте малышу остаться без праздника от папы с мамой.

Anonymous said...

В Голландии появилась новая услуга, [url=http://bit.ly/9irYlh ]платная подруга[/url]
она поговорит с вами по телефону, составит компанию по магазинам, пойдет с вами в кафе и если нужно припрется наночь глядя с бутылкой вина поговорить по душам.

И ничего не потребует взамен, кроме 50 евро в час.