The Carry Over Effect in Round Robin Tournaments : An Exploration of Optimization Strategies

Abstract

Fairness and optimal design of sport schedules are relevant for business, security and logistical matters. Sports events nowadays represent huge business opportunities and challenges. Many stakeholders, such as the police and broadcasting companies, depend on the organization of those events. The problem of minimizing the Carry Over Effect (COE) in Single Round Robin Tournaments (SRRT) represents a difficult combinatorial optimization problem which makes it a challenging subject for academics and researchers. In sport scheduling, the COE is a measure of how teams efforts are balanced throughout the tournament. The article of Guedes and Ribeiro (2011) is the starting point of this thesis. The first objective was to linearize and simplify their basic Quadratic Integer Programming (QIP) formulation of the COE problem and see how a present-day solver would perform compared to the results of Guedes and Ribeiro. An Integer Linear Programming (ILP) formulation is provided and results show a reduced running time, on small instances. In the second part, a Simulated Annealing (SA) algorithm exploring the Game Rotation (GR) neighborhood was implemented to solve larger instances. This is a stochastic metaheuristic procedure that needs to start from an initial schedule in order to modify it according to a set of rules. These structures are constrained by many requirements and the COE is a complex measure because it implies every single element of the fixture. We have no precise knowledge on how to arrange these elements to reduce the COE value. Additionally, modifying a structure is a real challenge, the number of possible arrangements of the elements of a fixture is incredibly huge but moving from one to another is not always possible with the moves structures we know so far. Indeed, the solutions space is characterized by a low connectivity between its different points. Therefore, an alternative using the solver and weights is proposed with a double target. First, overcome the difficulty of generating initial schedules. Second, diversify them as much as possible thanks to random weighting to try to overcome this connectivity issue. Then, the SA is applied a few times to each initial solution. Finally, results are analyzed and conclusions are drawn. Initial solutions produced by the solver are varied and results are satisfying, final solutions matching the results of Guedes and Ribeiro (2011) were achieved. The conclusion is that this combination of the solver and the SA procedure is working even though it has a drawback. The time required by the solver to issue a solution increases exponentially as the instance size grows. This duration depends, notably, on choices regarding the objective function and weights. Therefore, future investigation might help reduce this running time and improve the method proposed in this work.