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

2 Citations (Scopus)

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

Cite this

Toffolo, T. A. M., Christiaens, J., Spieksma, F. C. R., & Vanden Berghe, G. (2019). The sport teams grouping problem. Annals of Operations Research, 275(1), 223-243. https://doi.org/10.1007/s10479-017-2595-z