The sport teams grouping problem

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

Uittreksel

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.
TaalEngels
Pagina's223-243
Aantal pagina's21
TijdschriftAnnals of Operations Research
Volume275
Nummer van het tijdschrift1
DOI's
StatusGepubliceerd - apr 2019

Trefwoorden

    Citeer dit

    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. DOI: 10.1007/s10479-017-2595-z
    Toffolo, Tulio A.M. ; Christiaens, Jan ; Spieksma, Frits C.R. ; Vanden Berghe, Greet. / The sport teams grouping problem. In: Annals of Operations Research. 2019 ; Vol. 275, Nr. 1. blz. 223-243
    @article{7c27f75ffb0f44c797ceb0fd4818247f,
    title = "The sport teams grouping problem",
    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.",
    keywords = "Sport teams grouping problem, Branch-and-price, Column generation, Decomposition strategies, Integer programming, Meta-heuristic",
    author = "Toffolo, {Tulio A.M.} and Jan Christiaens and Spieksma, {Frits C.R.} and {Vanden Berghe}, Greet",
    year = "2019",
    month = "4",
    doi = "10.1007/s10479-017-2595-z",
    language = "English",
    volume = "275",
    pages = "223--243",
    journal = "Annals of Operations Research",
    issn = "0254-5330",
    publisher = "Springer",
    number = "1",

    }

    Toffolo, TAM, Christiaens, J, Spieksma, FCR & Vanden Berghe, G 2019, 'The sport teams grouping problem' Annals of Operations Research, vol. 275, nr. 1, blz. 223-243. DOI: 10.1007/s10479-017-2595-z

    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, Nr. 1, 04.2019, blz. 223-243.

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer 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 -

    Toffolo TAM, Christiaens J, Spieksma FCR, Vanden Berghe G. The sport teams grouping problem. Annals of Operations Research. 2019 apr;275(1):223-243. Beschikbaar vanaf, DOI: 10.1007/s10479-017-2595-z