A new neighborhood structure for round robin scheduling problems

• Several works proposed local search heuristics for round robin sport scheduling problems.
• The neighborhood structures used in those works do not connect the solution space.
• We present a novel neighborhood structure for single round robin sport scheduling problems.
• The neighborhood structure is described in graph theory terms and its correctness is proven.
• The new neighborhood structure increases the connectivity of the solution space.

In recent years, several works proposed local search heuristics for round robin sport scheduling problems. It is known that the neighborhood structures used in those works do not fully connect the solution space. The aim of this paper is to present a novel neighborhood structure for single round robin sport scheduling problems. The neighborhood structure is described in graph theory terms and its correctness is proven. We show that the new neighborhood structure increases the connectivity of the solution space when compared to previous neighborhood structures. We evaluate its performance using the Traveling Tournament Problem with Predefined Venues and the Weighted Carry-Over Effects Value Minimization Problem as case studies.