Abstract
| Language | English |
|---|---|
| Pages | 223-243 |
| Number of pages | 21 |
| Journal | Annals of Operations Research |
| Volume | 275 |
| Issue number | 1 |
| DOIs | |
| State | Published - Apr 2019 |
Keywords
- Sport teams grouping problem
- Branch-and-price
- Column generation
- Decomposition strategies
- Integer programming
- Meta-heuristic
Cite this
}
The sport teams grouping problem. / Toffolo, Tulio A.M. (Corresponding author); Christiaens, Jan; Spieksma, Frits C.R.; Vanden Berghe, Greet.
In: Annals of Operations Research, Vol. 275, No. 1, 04.2019, p. 223-243.Research output: Contribution to journal › Article › Academic › peer-review
TY - JOUR
T1 - The sport teams grouping problem
AU - Toffolo,Tulio A.M.
AU - Christiaens,Jan
AU - Spieksma,Frits C.R.
AU - Vanden Berghe,Greet
PY - 2019/4
Y1 - 2019/4
N2 - 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.
AB - 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.
KW - Sport teams grouping problem
KW - Branch-and-price
KW - Column generation
KW - Decomposition strategies
KW - Integer programming
KW - Meta-heuristic
U2 - 10.1007/s10479-017-2595-z
DO - 10.1007/s10479-017-2595-z
M3 - Article
VL - 275
SP - 223
EP - 243
JO - Annals of Operations Research
T2 - Annals of Operations Research
JF - Annals of Operations Research
SN - 0254-5330
IS - 1
ER -