Skip to main navigationSkip to main content
The University of Southampton
CORMSIS Centre for Operational Research, Management Sciences and Information Systems

CORMSIS seminar

Published: 20 September 2018

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.

 

Notes for editors

CORMSIS seminar at 13:30, TODAY Thursday September 20, in Building 54/Room 10037 (10B)

Privacy Settings