Analysis of a constructive matheuristic for the traveling umpire problem

The Traveling Umpire Problem (TUP) is a combinatorial optimization problem that concerns the assignment of umpires to the games of a fixed double round-robin tournament. The objective is to minimize the total travel distance of the umpires respecting several hard constraints that enforce fairness in the assignment of umpires. This paper presents a constructive matheuristic approach applied on an Integer Programming (IP) formulation of the TUP focusing primarily on the large benchmark instances. A decomposition based approach is implemented that solves the IP formulations of the subproblems sequentially to arrive at a feasible solution for the entire problem. The algorithm generates feasible solutions for the large benchmark instances of 26, 28 and 32-teams and improves the best solution for the 30-team instance in limited time. The paper also outlines experiments conducted to test various design parameters like size and overlap of the subproblems and the penalty function employed.

Publication year:2019

Accessibility:Open