An ILS heuristic for the traveling tournament problem with predefined venues

Fabrício Costa (), Sebastián Urrutia () and Celso Ribeiro ()

Annals of Operations Research, 2012, vol. 194, issue 1, 137-150

Abstract: The Traveling Tournament Problem with Predefined Venues (TTPPV) is a single round robin variant of the Traveling Tournament Problem, in which the venue of each game to be played is known beforehand. We propose an Iterated Local Search (ILS) heuristic for solving real-size instances of the TTPPV, based on two types of moves. Initial solutions are derived from an edge coloring algorithm applied to complete graphs. We showed that canonical edge colorings should not be used as initial solutions in some situations. Instead, the use of Vizing’s edge coloring method lead to considerably better results. We also establish that the solution space defined by some commonly used neighborhoods in the sport scheduling literature is not connected in the case of single round robin tournaments, which explains the hardness of finding high quality solutions to some problem instances. Computational results show that the new ILS heuristic performs much better than heuristics based on integer programming and that it improves the best known solutions for benchmark instances. Copyright Springer Science+Business Media, LLC 2012

Keywords: Traveling tournament problem; Sports scheduling; Iterated local search; Metaheuristics; Neighborhoods (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-010-0719-9 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:194:y:2012:i:1:p:137-150:10.1007/s10479-010-0719-9

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-010-0719-9

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().