Metaheuristics and Local Search

Combinatorial optimization, which includes sports scheduling problems as one of its areas of application, consists in finding optimal solutions to problems defined over a discrete set of feasible solutions. This chapter overviews approximate optimization methods, from greedy and semi-greedy construction algorithms to local search and from local search to metaheuristics. Some fundamental principles of metaheuristics are reviewed, and their templates are provided. Several approaches to sports scheduling problems make use of local search in the development of heuristics. We show how neighborhoods and other principles of local search can be adapted to the specific case of round-robin tournament scheduling problems. We conclude with the presentation of a collection of applications of metaheuristics to problems in sports scheduling.