CORMSIS seminar

The Traveling Umpire Problem: recent advances

Abstract:

-----------

The Traveling Umpire Problem (TUP) is an optimization problem in which umpires (or referees) have to be assigned to games in a double round robin tournament. The objective is to obtain a solution with minimum total travel distance over all umpires, while respecting hard constraints on assignments and sequences.

When the problem was introduced in 2008 only instances with 10 teams could be solved to optimality. For larger instances it was even hard to find a feasible solution. Recently, several exact and heuristic approaches have been proposed increasing the limits of exact methods to 18 teams.

We give an overview of these methods and focus on our recent work.

A branch and bound in which a round-based decomposition scheme is applied for generating lower bounds. We also present a constructive matheuristic and a parallel version of the branch and bound that is able to significantly improve the calculation times.

In addition to the new optimal solutions, some new best solutions were found and other instances were proven (in)feasible.