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 optimization problems. We will review briefly the metaheuristics ILS method and describe two relevant extensions:  the hybrid ILS approach that combines ILS with other metaheuristics and/or exact methods (MathILS) and the SimILS, that combines Simulation with ILS, to solve Stochastic Combinatorial Optimization Problems. We will discuss the advantages and disadvantages of these extensions and present some real applications in areas like Supply Chain Management, Logistics, Production, Marketing and Health and Social Care.