Hybridizing biogeography-based optimization and integer programming for solving the travelling tournament problem in sport scheduling

Combining metaheuristics with exact methods improves solution quality by efficiently exploring promising regions and refining the obtained solutions. This paper introduces a novel hybrid approach that combines exact methods and metaheuristics to address the Traveling Tournament Problem (TTP) in sports scheduling. The TTP, a critical aspect of sports management, aims to create a tournament schedule that minimizes the total travel distance of participating teams, which is essential for controlling league management costs and maximizing revenue. However, its complex optimization requirements and tournament structure make it highly challenging to solve efficiently. Our hybrid approach combines exact methods with the Biogeography-Based Optimization (BBO) metaheuristic to tackle both the TTP and its variant, the Unconstrained Traveling Tournament Problem (UTTP). We introduce a novel relaxation technique to enhance the efficiency of the Integer Linear Programming (ILP) formulation for the TTP. This technique involves fixing the schedule for a subset of teams and employing an ILP solver to optimize the schedule for the remaining teams. This relaxation technique is seamlessly integrated into the BBO operators. We evaluate the effectiveness of our method using publicly available benchmark instances and compare it with existing techniques for both TTP and UTTP. Our experimental results demonstrate that the proposed approach achieves competitive solution quality. It outperforms prior methods on UTTP for the US National Baseball League NL16 instances and some prominent methods when applied to TTP.