ODU MATH PROFESSOR DEVELOPS MAJOR LEAGUE BASEBALL SCHEDULE

When Mark Dorrepaal was growing up in Ontario, just across the border from Detroit, he was a devoted fan of the Tigers and, like many boys, was a student of Major League Baseball (MLB) statistics.

But, unlike most young fans, Dorrepaal had an interest in statistics that extended well beyond the performance of players. He found fascination in baseball schedules.

"The Yankees would come to town, and I'd wonder, where were they last night, where will they travel next, and where are all the teams at any one time," said the man who now chairs the Old Dominion University Department of Mathematics and Statistics.

This boyhood fascination never left him, and to prove it, Dorrepaal chalked up a remarkable achievement this spring as the major league season was getting under way. He jumped into the lead of a World Wide Web-based contest to develop an optimized schedule for National League teams.

He accomplished his feat without computer genius, which is what drives the sports scheduling of most of his competitors. He did it with paper and pencil and "noggin' power."

Even people who do not follow baseball can appreciate the kind of interdependent scheduling that helps airplane travelers make their connections or keeps a school bus driver from traveling wasteful miles or making wasteful stops. Many people, too, have heard of the decades-old mathematical word problems involving a traveling salesman who wants to know the most efficient way to visit several cities on a business trip.

But no schedule seems as complex as the ones for the major league baseball season. Imagine 14 or 16 teams-depending on the league-playing 162 regular season games apiece. Also consider what the experts call the scheduling "constraints." The Yankees, for example, would rather be playing road games outside of New York when the Mets are playing home games to minimize competition for spectator dollars. Also, for various reasons, including player fatigue, no road trip by a team should be longer than, say, 11 days.

Efficiency hinges largely on miles traveled, so the Mets would not want a road series that took them first to San Diego, next to Atlanta and then back to the West Coast to play San Francisco. The more efficient itinerary would take the Mets to San Diego, Los Angeles and San Francisco.

Only recently have the major leagues begun to rely on sophisticated computing in order to fashion efficient schedules. Because there are billions of possible schedules, however, the National League (NL) and American League (AL) remain far from certain about how close they are to optimal travel schemes. In other words, they know that the Yankees and the Mets, and all of the other teams, could be traveling many unnecessary miles each season.

About seven years ago, an academician under contract to MLB instituted the Challenge Traveling Tournament Web site (http://mat.gsia.cmu.edu/TOURN/) to solicit efficient schedules for baseball and other sports from hobbyists such as Dorrepaal and anyone else who was willing to participate just for the honor of getting a citation on the Web. The site's originator and keeper is Michael Trick, professor of operations research at Carnegie Mellon's Tepper School of Business.

Several separate baseball scheduling contests are on the Website, all for National League (NL) teams. For instance, you can try scheduling a season for only 6 NL teams, or 8, and so forth, just to get the hang of it. The contest that Dorrepaal led in the spring of 2006 is the 14 NL team schedule. (The NL has 16 teams.)
Competitors are given distances for travel between the NL cities, and directed to make a schedule in which each team plays each other both home and away.

The schedule is subject to constraints, such as no more than three consecutive home stands or road stands, as well as no consecutive home/away stands between the same teams. The objective is to complete the schedule with the fewest miles of travel for all teams.

In the 1970s when he was in graduate school at the University of Toronto, Dorrepaal mailed off his first schedule to MLB. He served up another one in the late 1980s after he lost his wife to cancer and found himself working on the scheduling problem as a diversion. He never got more than a thank-you letter for all his effort. Having his name on the Web site now as leader of the 14 NL team contest is a far greater reward, he says.

How did he surge into the lead? Since 2002 he has been a top-drawer performer on the scheduling Web site, but several computer experts, including Pascal Van Hentenryck, professor of computer science at Brown University, blew onto the site a few years ago with the kind of sophisticated software that can run circles around a paper and pencil guy such as Dorrepaal.

Van Hentenryck, who currently leads the 16 NL team contest, took the lead in the 14 NL team contest in May 2004 with a miles total of 189,766. "The big boys had been trading the lead for a year or so in the 14-team contest, and Van Hentenryck's new low miles total in the spring of 2004 seemed to be hard to beat," Dorrepaal said.

But the ODU professor wasn't ready to admit defeat. Early this year, he began poring over the Van Hentenryck 14 NL team schedule. He divided it up into scheduling blocks and applied some of his tried and true "manual" methods of optimization. At Eastertime he was inspecting one block of the Van Hentenryck schedule when he had his "eureka!" moment.

"His computer program is quite good. There is no question about that," Dorrepaal said of Van Hentenryck. "But in doing a good job on the big picture, the program missed a shortcut or two."

Dorrepaal came up with a schedule that required only 189,759 miles of team travel, seven miles better than Van Hentenryck's best total.

The next quest would be a manual analysis of Van Hentenryck's 16 NL team schedule. But Dorrepaal is not sure he wants to put himself, and his collaborating graduate student, George Chackman, through the rigors of another analysis.

"Frankly, I'm not the computer genius you need to be," said Dorrepaal, who has been on the ODU faculty since 1976. "I am maximizing my publicity with a minimum amount of ability." (Editor's note: Van Hentenryck retook the lead in the 14 NL team contest from Dorrepaal after this article was written. For the latest result, see the Web site.)

But the Web site competition, and his success, has sparked his interest in developing a scheduling template, or broad scheduling theorems, that might apply to many scheduling problems. He also has been talking with the ODU psychology professor Janis Sanchez-Hucles, the university's NCAA representative, about advice he might give the Colonial Athletic Association about basketball scheduling.

He hopes that some of the scheduling patterns the Web site competition has produced will be used by MLB. He noticed that the 2006 schedule included some of the optimizing characteristics that are evident in the competition's best entries.

"I sent a note to Professor Trick asking whether the current major league schedule was generated by a software program similar to the ones used to generate solutions on the Web site," Dorrepaal explained. "He answered that he and George Nemhauser (professor of industrial and systems engineering at Georgia Tech) had done the 2005 schedule and that the current schedule was done by a Canadian company-a tiny, three-man outfit-that uses optimization software."

The Canadian company, Optimal Planning Solutions, was founded by a man who at one time scheduled the delivery of frozen French fries to McDonald's franchises. The company now does scheduling not only for MLB, but also for the National Football League and several hockey leagues.

In the real world, the MLB schedule has constraints, such as those imposed by television or by particular rivalries-between the Red Sox and Yankees, for one-that are not imposed on the Web site hobbyists. "It's a tremendously complicated choreography," Dorrepaal said.

He would be the first to admit that computer scheduling experts have supplanted the veteran paper and pencil guys.

But the guys at Optimal Planning Solutions should not be surprised if they get mail sometime over the next few years from a fellow Canadian, a mathematician named Dorrepaal. Inside, they just may find MLB scheduling tips written on a napkin.