The traveling salesman problem is a favorite math conundrum: if a salesman has to visit a ____1____ of cities, how do you get him to all of them once via the shortest possible route. But the traveling salesman’s predicament ____2____ in comparison to figuring out the best ways to get four-man crews of umpires to every major league baseball game. A research team attacked the problem for the last few years. Their solution appears in Interfaces. It’s a journal of Operations Research.

In addition to minimizing travel, here are some of the umpire ____3____. Crews should visit each MLB city at least once. They should work each team at home and on the road. They should not work more than 21 days in a row. They should not ump any one team’s games for more than four____4____all year. There are plenty more.

The researchers first had to develop the question, dubbed the Traveling Umpire Problem. They used brute-force computation and heuristics for their solutions. The result was good enough for Major League Baseball to adopt the last three seasons. Previously, a former umpire made the ____5____. That guy is out.
【視聽版科學(xué)小組榮譽出品】
bunch pales constraints series schedule
那些跑銷售的人有一個苦惱的數(shù)學(xué)題:如果一個推銷員需要拜訪數(shù)個城市,那么他怎樣才能一次完成任務(wù)并且采用最短的路線。但當(dāng)找尋合適的方法為棒球職業(yè)聯(lián)賽中的四名裁判員成完成裁判任務(wù)擺在推銷人員的困境面前時,他們的無奈蒼白了許多。一個研究小組已經(jīng)研究了這個問題幾年。他們的研究結(jié)果發(fā)表在《界面》(一本機械研究雜志)上 此外,為了減少行程,對裁判有很多限制。他們需要在至少到一次職棒聯(lián)盟城市,需要在吹當(dāng)?shù)鼗蛘呗愤^城市中的比賽,并且他們在一個巡回中不能工作超過21天,不能在一年中吹同一個隊伍的比賽四季。當(dāng)然還有更多的規(guī)矩。 研究者們首先要列出裁判們行程中的問題。他們利用抗窮舉性計算和啟發(fā)式數(shù)學(xué)法來設(shè)計路線。這些結(jié)果已經(jīng)被職業(yè)棒球聯(lián)盟采納三個賽季。從前都是裁判自己定行程,這種方式已經(jīng)過時。