Back to Search
Start Over
A metaheuristic algorithm for the carry-over effect value minimization problem in round-robin tournaments
- Source :
- Journal of Advanced Mechanical Design, Systems, and Manufacturing, Vol 16, Iss 4, Pp JAMDSM0042-JAMDSM0042 (2022)
- Publication Year :
- 2022
- Publisher :
- The Japan Society of Mechanical Engineers, 2022.
-
Abstract
- Round­robin tournaments are widely used in sports leagues such as football and baseball leagues. The round­robin tournament scheduling problem is one of the most well­known problems in sports scheduling. When creating a schedule for a round­robin tournament, various factors are considered such as travel distance of teams and the number of breaks. Among such factors, the carry­over effect is often considered to evaluate a schedule from the viewpoint of fairness. In this paper, we propose a metaheuristic algorithm for the problem of minimizing the carry-over effect value. For a complete graph whose edges describe all possible matches in a round­robin tournament, we consider a rainbow perfect matching, which we call a base matching, to describe a round of a schedule. By using the circle method, a round­robin tournament schedule can be generated from any base matching. Then we design a metaheuristic algorithm based on iterated local search to search for a “good” base matching, that is, one that generates a round­robin tournament schedule with a low carry­over effect value. We confirmed through computational experiments that our proposed algorithm obtained solutions with carry­over effect values equal to or lower than the best­known values for 15 out of the 17 tested instances with up to 40 teams. In addition, we updated the best­known records for 2 instances.
Details
- Language :
- English
- ISSN :
- 18813054
- Volume :
- 16
- Issue :
- 4
- Database :
- Directory of Open Access Journals
- Journal :
- Journal of Advanced Mechanical Design, Systems, and Manufacturing
- Publication Type :
- Academic Journal
- Accession number :
- edsdoj.48a32c0bf2c54278898c07dbcb037417
- Document Type :
- article
- Full Text :
- https://doi.org/10.1299/jamdsm.2022jamdsm0042