The sport teams grouping problem

Tulio A.M. Toffolo (Corresponding author), Jan Christiaens, Frits C.R. Spieksma, Greet Vanden Berghe

Research output: Contribution to journalArticleAcademicpeer-review

11 Citations (Scopus)
309 Downloads (Pure)

Abstract

The sport teams grouping problem (STGP) concerns the assignment of sport teams to round-robin tournaments. The objective is to minimize the total travel distance of the participating teams while simultaneously respecting fairness constraints. The STGP is an NP-Hard combinatorial optimization problem highly relevant in practice. This paper investigates the performance of some complimentary optimization approaches to the STGP. Three integer programming formulations are presented and thoroughly analyzed: two compact formulations and another with an exponential number of variables, for which a branch-and-price algorithm is proposed. Additionally, a meta-heuristic method is applied to quickly generate feasible high-quality solutions for a set of real-world instances. By combining the different approaches’ results, solutions within 1.7% of the optimum values were produced for all feasible instances. Additionally, to support further research, the considered STGP instances and corresponding solutions files were shared online.
Original languageEnglish
Pages (from-to)223-243
Number of pages21
JournalAnnals of Operations Research
Volume275
Issue number1
DOIs
Publication statusPublished - 1 Apr 2019

Keywords

  • Branch-and-price
  • Column generation
  • Decomposition strategies
  • Integer programming
  • Meta-heuristic
  • Sport teams grouping problem

Fingerprint

Dive into the research topics of 'The sport teams grouping problem'. Together they form a unique fingerprint.

Cite this