IDEAS home Printed from https://ideas.repec.org/a/spr/jsched/v25y2022i3d10.1007_s10951-022-00738-6.html
   My bibliography  Save this article

A fix-and-optimize heuristic for the ITC2021 sports timetabling problem

Author

Listed:
  • George H. G. Fonseca

    (Federal University of Ouro Preto)

  • Túlio A. M. Toffolo

    (Federal University of Ouro Preto)

Abstract

This paper addresses the general and challenging Sports Timetabling Problem proposed during the International Timetabling Competition of 2021 (ITC2021). The problem is expressed in a flexible format which enables modeling a number of real-world constraints that often occur in Sports Timetabling. An integer programming (IP) formulation and a fix-and-optimize heuristic are proposed to address the problem. The fix-and-optimize approach uses the IP formulation to heuristically decompose the problem into sub-problems and efficiently search on very large neighborhoods. The diverse ITC2021 benchmark instances were used to evaluate the proposed methods. The formulation resulted in proven optimal solutions for two instances. However, it failed to produce feasible solutions for most instances. The proposed fix-and-optimize, which uses an automatic sub-problem size calibration strategy, resulted in feasible solutions for 37 out of the 45 ITC2021 instances. Among these solutions, four are the best known in the literature. The proposed approach participated in the ITC2021 and was one of the finalists.

Suggested Citation

  • George H. G. Fonseca & Túlio A. M. Toffolo, 2022. "A fix-and-optimize heuristic for the ITC2021 sports timetabling problem," Journal of Scheduling, Springer, vol. 25(3), pages 273-286, June.
    • Handle: RePEc:spr:jsched:v:25:y:2022:i:3:d:10.1007_s10951-022-00738-6
    DOI: 10.1007/s10951-022-00738-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10951-022-00738-6
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10951-022-00738-6?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Fabrício Costa & Sebastián Urrutia & Celso Ribeiro, 2012. "An ILS heuristic for the traveling tournament problem with predefined venues," Annals of Operations Research, Springer, vol. 194(1), pages 137-150, April.
    2. Rasmussen, Rasmus V. & Trick, Michael A., 2008. "Round robin scheduling - a survey," European Journal of Operational Research, Elsevier, vol. 188(3), pages 617-636, August.
    3. Guido Cocchi & Alessandro Galligari & Federica Picca Nicolino & Veronica Piccialli & Fabio Schoen & Marco Sciandrone, 2018. "Scheduling the Italian National Volleyball Tournament," Interfaces, INFORMS, vol. 48(3), pages 271-284, June.
    4. Haroldo G. Santos & Túlio A. M. Toffolo & Rafael A. M. Gomes & Sabir Ribas, 2016. "Integer programming techniques for the nurse rostering problem," Annals of Operations Research, Springer, vol. 239(1), pages 225-251, April.
    5. Van Bulck, David & Goossens, Dries & Schönberger, Jörn & Guajardo, Mario, 2020. "RobinX: A three-field classification and unified data format for round-robin sports timetabling," European Journal of Operational Research, Elsevier, vol. 280(2), pages 568-580.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Guillermo Durán, 2021. "Sports scheduling and other topics in sports analytics: a survey with special reference to Latin America," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(1), pages 125-155, April.
    2. Dries Goossens & Jeroen Beliën, 2023. "Teaching Integer Programming by Scheduling the Belgian Soccer League," INFORMS Transactions on Education, INFORMS, vol. 23(3), pages 164-172, May.
    3. Roberto Maria Rosati & Matteo Petris & Luca Di Gaspero & Andrea Schaerf, 2022. "Multi-neighborhood simulated annealing for the sports timetabling competition ITC2021," Journal of Scheduling, Springer, vol. 25(3), pages 301-319, June.
    4. David Van Bulck & Dries Goossens & Jo¨rn Scho¨nberger & Mario Guajardo, 2020. "An Instance Data Repository for the Round-robin Sports Timetabling Problem," Management and Labour Studies, XLRI Jamshedpur, School of Business Management & Human Resources, vol. 45(2), pages 184-200, May.
    5. van Doornmalen, Jasper & Hojny, Christopher & Lambers, Roel & Spieksma, Frits C.R., 2023. "Integer programming models for round robin tournaments," European Journal of Operational Research, Elsevier, vol. 310(1), pages 24-33.
    6. Roel Lambers & Dries Goossens & Frits C. R. Spieksma, 2023. "The flexibility of home away pattern sets," Journal of Scheduling, Springer, vol. 26(5), pages 413-423, October.
    7. Goller, Daniel & Krumer, Alex, 2020. "Let's meet as usual: Do games played on non-frequent days differ? Evidence from top European soccer leagues," European Journal of Operational Research, Elsevier, vol. 286(2), pages 740-754.
    8. Guillermo Durán & Mario Guajardo & Facundo Gutiérrez & Javier Marenco & Denis Sauré & Gonzalo Zamorano, 2021. "Scheduling the Main Professional Football League of Argentina," Interfaces, INFORMS, vol. 51(5), pages 361-372, September.
    9. Yi, Xiajie & Goossens, Dries & Nobibon, Fabrice Talla, 2020. "Proactive and reactive strategies for football league timetabling," European Journal of Operational Research, Elsevier, vol. 282(2), pages 772-785.
    10. Christian Ackermann & Felix Hahne & Julia Rieck, 2022. "Matching and Scheduling of Student-Company-Talks for a University IT-Speed Dating Event," SN Operations Research Forum, Springer, vol. 3(3), pages 1-29, September.
    11. Martin Mariusz Lester, 2022. "Pseudo-Boolean optimisation for RobinX sports timetabling," Journal of Scheduling, Springer, vol. 25(3), pages 287-299, June.
    12. Xiajie Yi & Dries Goossens, 2023. "Strategies for dealing with uncertainty in time-relaxed sports timetabling," Annals of Operations Research, Springer, vol. 320(1), pages 473-492, January.
    13. Van Bulck, David & Goossens, Dries, 2023. "The international timetabling competition on sports timetabling (ITC2021)," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1249-1267.
    14. Tasbih Tuffaha & Burak Çavdaroğlu & Tankut Atan, 2023. "Round-robin scheduling with regard to rest differences," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 31(2), pages 269-301, July.
    15. Bergantiños, Gustavo & Moreno-Ternero, Juan D., 2022. "Monotonicity in sharing the revenues from broadcasting sports leagues," European Journal of Operational Research, Elsevier, vol. 297(1), pages 338-346.
    16. Briskorn, Dirk & Horbach, Andrei, 2009. "A Lagrangian approach for minimum cost tournaments," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 647, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    17. Jaeseob Han & Seung-Hyun Jeon & Gyeong-Ho Lee & Sangdon Park & Jun-Kyun Choi, 2023. "Power and Frequency Band Allocation Mechanisms for WPT System with Logarithmic-Based Nonlinear Energy Harvesting Model," Sustainability, MDPI, vol. 15(13), pages 1-27, July.
    18. Michael A. Trick & Hakan Yildiz & Tallys Yunes, 2012. "Scheduling Major League Baseball Umpires and the Traveling Umpire Problem," Interfaces, INFORMS, vol. 42(3), pages 232-244, June.
    19. Jari Kyngäs & Kimmo Nurmi & Nico Kyngäs & George Lilley & Thea Salter & Dries Goossens, 2017. "Scheduling the Australian Football League," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(8), pages 973-982, August.
    20. Sara Ceschia & Rosita Guido & Andrea Schaerf, 2020. "Solving the static INRC-II nurse rostering problem by simulated annealing based on large neighborhoods," Annals of Operations Research, Springer, vol. 288(1), pages 95-113, May.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jsched:v:25:y:2022:i:3:d:10.1007_s10951-022-00738-6. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.