Iterated Local Search: Applications and Extensions

Metaheuristics are general high-level procedures that coordinate heuristics and rules to find high-quality solutions to difficult optimization problems in a short computational time. They are designed to solve large-scale complex optimization problems that cannot be solved in reasonable processing time by the classic combinatorial optimization methods. Metaheuristics have been extensively applied to solve real problems in many areas from transportation to finance, sports or manufacturing, etc..

In this tutorial, we will briefly review several metaheuristics successfully applied to combinatorial optimization problems, and we will focus on the Iterated Local Search (ILS) approach, a conceptually simple and efficient well-known metaheuristic. The main idea behind ILS is to drive the search not on the full space of all candidate solutions but on the solutions that are returned by some underlying algorithm; typically, local optimal solutions obtained by the application of a local search heuristic. This method has been applied to many different…