IDEAS home Printed from https://ideas.repec.org/a/ids/eujine/v6y2012i1p2-25.html
   My bibliography  Save this article

A hybrid PSO-SA algorithm for the travelling tournament problem

Author

Listed:
  • Alireza Tajbakhsh
  • Kourosh Eshghi
  • Azam Shamsi

Abstract

Sports scheduling has become an important area of applied operations research in recent years, since satisfying fans' and teams' requests and revenues of a sports league and TV networks may be affected by quality of the league schedule. While this type of scheduling problem can be solved by mathematical methods and exact solutions are accessible, it computationally leads to hard problems. The travelling tournament problem (TTP) is defined as minimising total travelling distance for all teams in a league. In this study, a new mathematical model for the TTP with the no-repeater constraint is presented. In addition, a very fast hybrid metaheuristic algorithm is proposed, which combines particle swarm optimisation (PSO) and simulated annealing (SA). Our computational experiments on standard instances show that the hybrid approach results in comparable to or even better than current best known solutions, specifically in computational time. [Received 24 August 2009; Revised 16 January 2010, 9 June 2010; Accepted 12 June 2010]

Suggested Citation

  • Alireza Tajbakhsh & Kourosh Eshghi & Azam Shamsi, 2012. "A hybrid PSO-SA algorithm for the travelling tournament problem," European Journal of Industrial Engineering, Inderscience Enterprises Ltd, vol. 6(1), pages 2-25.
    • Handle: RePEc:ids:eujine:v:6:y:2012:i:1:p:2-25
    as

    Download full text from publisher

    File URL: http://www.inderscience.com/link.php?id=44808
    Download Restriction: Access to full text is restricted to subscribers.
    ---><---

    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. James C. Bean & John R. Birge, 1980. "Reducing Travelling Costs and Player Fatigue in the National Basketball Association," Interfaces, INFORMS, vol. 10(3), pages 98-102, June.
    2. Irnich, Stefan, 2010. "A new branch-and-price algorithm for the traveling tournament problem," European Journal of Operational Research, Elsevier, vol. 204(2), pages 218-228, July.
    3. Lim, A. & Rodrigues, B. & Zhang, X., 2006. "A simulated annealing and hill-climbing algorithm for the traveling tournament problem," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1459-1478, November.
    4. 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.
    5. Charles Fleurent & Jacques A. Ferland, 1993. "Allocating Games for the NHL Using Integer Programming," Operations Research, INFORMS, vol. 41(4), pages 649-654, August.
    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. Hoshino, Richard & Kawarabayashi, Ken-ichi, 2011. "A multi-round generalization of the traveling tournament problem and its application to Japanese baseball," European Journal of Operational Research, Elsevier, vol. 215(2), pages 481-497, December.
    3. 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.
    4. Flavia Bonomo & Andrés Cardemil & Guillermo Durán & Javier Marenco & Daniela Sabán, 2012. "An Application of the Traveling Tournament Problem: The Argentine Volleyball League," Interfaces, INFORMS, vol. 42(3), pages 245-259, June.
    5. 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.
    6. Bartsch, Thomas & Kröger, Stefan, 1996. "Ein Entscheidungs-Unterstützungs-System zur Erstellung von Spielplänen für die Fußballbundesliga," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 427, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    7. Zheng, Feifeng & Cheng, Yongxi & Xu, Yinfeng & Liu, Ming, 2013. "Competitive strategies for an online generalized assignment problem with a service consecution constraint," European Journal of Operational Research, Elsevier, vol. 229(1), pages 59-66.
    8. 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.
    9. M B Wright, 2009. "50 years of OR in sport," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 161-168, May.
    10. Alex Krumer & Reut Megidish & Aner Sela, 2020. "The optimal design of round-robin tournaments with three players," Journal of Scheduling, Springer, vol. 23(3), pages 379-396, June.
    11. Kent J. Kostuk & Keith A. Willoughby, 2012. "A Decision Support System for Scheduling the Canadian Football League," Interfaces, INFORMS, vol. 42(3), pages 286-295, June.
    12. Schonberger, J. & Mattfeld, D. C. & Kopfer, H., 2004. "Memetic Algorithm timetabling for non-commercial sport leagues," European Journal of Operational Research, Elsevier, vol. 153(1), pages 102-116, February.
    13. Durán, Guillermo & Durán, Santiago & Marenco, Javier & Mascialino, Federico & Rey, Pablo A., 2019. "Scheduling Argentina’s professional basketball leagues: A variation on the Travelling Tournament Problem," European Journal of Operational Research, Elsevier, vol. 275(3), pages 1126-1138.
    14. Marc Goerigk & Stephan Westphal, 2016. "A combined local search and integer programming approach to the traveling tournament problem," Annals of Operations Research, Springer, vol. 239(1), pages 343-354, April.
    15. Stephan Westphal & Karl Noparlik, 2014. "A 5.875-approximation for the Traveling Tournament Problem," Annals of Operations Research, Springer, vol. 218(1), pages 347-360, July.
    16. Deren Çağlayan & Emin Karagözoğlu & Kerim Keskin & Çağrı Sağlam, 2022. "Effort comparisons for a class of four-player tournaments," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 59(1), pages 119-137, July.
    17. Russell, Robert A. & Urban, Timothy L., 2010. "Multicriteria models for planning power-networking events," European Journal of Operational Research, Elsevier, vol. 207(1), pages 83-91, November.
    18. 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.
    19. 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.
    20. Michal Friesl & Jan Libich & Petr Stehlík, 2020. "Fixing ice hockey’s low scoring flip side? Just flip the sides," Annals of Operations Research, Springer, vol. 292(1), pages 27-45, September.

    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:ids:eujine:v:6:y:2012:i:1:p:2-25. 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: Sarah Parker (email available below). General contact details of provider: http://www.inderscience.com/browse/index.php?journalID=210 .

    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.