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 language | English |
---|---|
Pages (from-to) | 223-243 |
Number of pages | 21 |
Journal | Annals of Operations Research |
Volume | 275 |
Issue number | 1 |
DOIs | |
Publication status | Published - 1 Apr 2019 |
Keywords
- Branch-and-price
- Column generation
- Decomposition strategies
- Integer programming
- Meta-heuristic
- Sport teams grouping problem