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. |
Year | DOI | Venue |
---|---|---|
2019 | 10.1007/s10479-017-2595-z | Annals of Operations Research |
Keywords | Field | DocType |
Sport teams grouping problem, Branch-and-price, Column generation, Decomposition strategies, Integer programming, Meta-heuristic | Mathematical optimization,Column generation,Exponential function,Combinatorial optimization problem,Branch and price,Meta heuristic,Integer programming,Mathematics | Journal |
Volume | Issue | ISSN |
275 | 1 | 1572-9338 |
Citations | PageRank | References |
0 | 0.34 | 26 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Túlio A. Toffolo | 1 | 26 | 4.35 |
Jan Christiaens | 2 | 0 | 0.34 |
Frits C. R. Spieksma | 3 | 591 | 58.84 |
Greet Van Den Berghe | 4 | 24 | 3.37 |