A Hybrid ILS Heuristic to the Referee Assignment Problem with an Embedded MIP Strategy

Optimization in sports is a field of increasing interest. A novel problem in sports management is the Referee Assignment Problem, in which a limited number of referees with different qualifications and availabilities should be assigned to a set of games already scheduled. We extend and improve a previous three-phase approach for this problem, based on a constructive heuristic, a repair heuristic to make the initial solutions feasible, and an ILS improvement heuristic. We propose a new constructive algorithm based on a greedy criterion to build initial solutions. Furthermore, we develop a hybridization strategy in which a mixed integer programming exact algorithm replaces the original neighborhood-based local search within the ILS heuristic. Computational experiments are performed for large realistic instances. The use of time-to-target-solution-value plots is emphasized in the evaluation of the numerical results, illustrating the efficiency and the robustness of the new approach. The proposed hybridization of MIP with local search can be extended to other metaheuristics and applications, opening a new research avenue to more robust algorithms.