An ILS heuristic for the traveling tournament problem with predefined venues

An ILS heuristic for the traveling tournament problem with predefined venues

0.00 Avg rating0 Votes
Article ID: iaor2012870
Volume: 194
Issue: 1
Start Page Number: 137
End Page Number: 150
Publication Date: Apr 2012
Journal: Annals of Operations Research
Authors: , ,
Keywords: heuristics: local search, graphs
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.

Reviews

Required fields are marked *. Your email address will not be published.