Home

RobinX: an XML-driven classification for round-robin sports timetabling
Info: The source code of the validator is now available on github! GitHub

Project Overview Explore on GitHub View EJOR publication View MLS publication Watch a demo

Problem logo A benchmarking problem
  • In a round-robin timetable, every team plays against every other team a fixed number of times
  • Most sports timetabling problems differ in terms of the objective function and the type of additional timetabling restrictions they include
  • Researchers typically develop a method for one specific type of sports timetabling problem
  • Datasets are rarely shared and methods are almost never benchmarked with previous literature
RobinX: an XML-based solution
  • We propose a data-driven three-field classification scheme
  • Our approach is able to classify a wide range of sports scheduling problems ranging from time-relaxed to time-constrained, both single- and multi-league
  • This scheme is embedded in an XML template that separates instances from solutions
  • The framework helps researchers to store, retrieve, and benchmark generated solutions with minimal effort
3-Field classification of a sports timetabling problem

Alpha-field

  • focus on \(k\)-round robins (\(kRR\))
  • Time-constrained \((C)\) or time-relaxed \((R)\)
    • Mirror image
  • Game mode
    • Same pairings recur in different round
      \(1^{st}\) half \(2^{nd}\) half
      Inverted (I) 1 2 3 3 2 1
      English (E) 1 2 3 3 1 2
      Mirrored (M) 1 2 3 1 2 3
    • Additionally, the home advantage is swapped
    Mirror image

Beta-field

  • Sports timetables are highly constrained
  • Around 20 popular constraints are grouped into 5 constraint groups: capacity, game, break, fairness, and separation constraints
  • Constraints can be hard or soft and have a penalty value, if the constraint is violated:
    • Hard: add penalty to infeasibility value
    • Soft: add penalty to objective value
Examples of specific constraints
CA1 Each team in team group \(T\) plays at least \(k_{min}\) and at most \(k_{max}\) {home games, away games, games} in time group \(S\).
BR1 Each team in team group \(T\) has at least \(k_{min}\) and at most \(k_{max}\) {home breaks, away breaks, breaks} in time group \(S\).

Gamma-field

  • If the user opts for one of the following objectives, all constraints should be hard:
    • Minimum (weighted) break (BR)
    • Minimum travel (TR)
    • Minimum cost (CR)
    • Minimum (weighted) carry-over (COE)
  • Alternatively, users can minimize soft constraint violations (SC)

Integrated example

  • Time-constrained double round-robin with inverted second half
  • The objective is to minimize travel distance under capacity and break constraints $$2\text{RR}, \text{C}, \text{I} | \text{CA1}, \text{BR1} | \text{TR}$$
XML Implementation
Corresponding data format
  • Classification scheme is implemented in XML
  • Instance file:
    • Description of the problem instance
    • Static information
  • Solution file:
    • Link to instance
    • Dynamic: updated when better solution is found
A web-based validator
Web-based application:
  • User-friendly web application that allows users to create data files
  • Free and open-source C++ library to read, write, validate, and evaluate both XML files
  • If a solution respects all hard constraints as described by the instance file, the validator returns the objective value of the solution.
  • Otherwise the validator returns all violated hard constraints
XML Archives: A sports timetabling database
  • Wide range of instances are published online
  • Competition with list of best-known solutions
  • User can enter queries based on three-field classification scheme to retrieve instances of interest
  • User can enter queries based on three-field classification scheme to retrieve papers of interest
  • We invite researchers to join the project and submit their own problem instances and solutions


The sports timetabling archives

I often compare open source to science. To where science took this whole notion of developing ideas in the open and improving on other peoples' ideas and making it into what science is today and the incredible advances that we have had. And I compare that to witchcraft and alchemy, where openness was something you didn't do. Linus Torvalds
The sports timetabling archives of RobinX contain a wide variety of of test problems within the domain of sports timetabling. The library consists of problems organized by subject area and are all classified according to the 3-field notation. In order to select instances from different subject domains, we developed a query tool that enables user to select instances that have or do not have a specific classification tag.
For each problem instance, our library also contains the best found solution. This allows users to verify solutions and compare their own solutions with the ones found in the literature. Finally, the library also contains (a link to) the source code used to solve the problem. Although not obligatory, we strongly encourage researchers to publish their code.