Approaching the Traveling Tournament Problem with Randomized Beam Search

Area of Science:

• Operations Research
• Combinatorial Optimization
• Sports Analytics

Background:

• The traveling tournament problem (TTP) is a complex sports scheduling challenge focused on minimizing total team travel distances.
• A common variant involves constraints like no repeaters and a streak limit of three, increasing its difficulty.

Purpose of the Study:

• To develop and evaluate an effective beam search approach for solving the constrained traveling tournament problem.
• To minimize total travel distances in double round-robin tournaments for leagues with an even number of teams.

Main Methods:

• A state-space formulation of the TTP guided by heuristics derived from lower bounds.
• Solving capacitated vehicle routing subproblems exactly (up to 18 teams) or heuristically (up to 24 teams).
• Employing a randomized beam search with random team ordering and Gaussian noise for diversification and parallelization.

Main Results:

• The beam search approach successfully solved instances up to 24 teams.
• Achieved a mean gap difference of 1.2% to the best-known feasible solutions on benchmark instances.
• Found five new best feasible solutions for the studied benchmark instances.

Conclusions:

• The proposed beam search method, enhanced with randomization, is effective for the constrained traveling tournament problem.
• The approach offers a practical and parallelizable solution for sports league scheduling with significant travel distance minimization.