Traveling Umpire Problem

The Traveling Umpire Problem (TUP) considers the problem of assigning umpires (or referees) to a tournament of games. In a TUP instance, 2n teams are playing a double round robin tournament. Each team has a home venue, and every pair of teams plays twice in the tournament, once at each team's venue. There are 4n-4 time slots in the tournament; every team plays exactly once in each time slot. There are signicant distances between home venues, defined by a symmetric distance matrix satisfying the triangle inequality.

There are n umpires to handle these games. Each game needs one umpire; each umpire handles one game per time slot. There are three main conflicting goals that drive the assignment of umpires to games. First, the umpires should not travel too much. Travel for the umpires is defined to be the sum of the distances between home venues of successive handled games. Second, umpires should see all the home venues. Third, umpires should not handle the games of a team too often in short succession.

The first goal is handled by the objective function: the objective is to minimize the total travel distance of the umpires. The second goal is handled as a hard constraint: every umpire must handle at least one game for each team at that team's home venue. The third goal is handled by two constraints with parameters to denote how closely to ideal the constraints must be met:

1. No umpire is in a home venue more than once in any n-d₁ consecutive slots, and
2. No umpire sees a team (either home or away) more than once in any n/2-d₂ (rounded down) consecutive slots.

The parameters d₁ and d₂ are tightness parameters: lower values of these parameters makes the corresponding constraint more difficult to satisfy.

The Traveling Umpire Problem abstracts out key issues faced by Major League Baseball in scheduling their umpires, in the same way the Traveling Tournament Problem handles the key issues faced by MLB in scheduling their games.

Scheduling Major League Baseball Umpires and the Traveling Umpire Problem, M.A. Trick, H. Yildiz, and T. Yunes, accepted Interfaces

Locally Optimized Crossover for the Traveling Umpire Problem, M.A. Trick and H. Yildiz, accepted European Journal of Operational Research

Bender's Cuts Guided Large Neighborhood Search for the Traveling Umpire Problem, M.A. Trick and H. Yildiz, accepted Naval Research Logistics