A survey of very large-scale neighborhood search techniques

Many discrete optimization problems of practical interest cannot be solved to optimality in the available time. A practical approach to these problems is to use heuristic algorithms, which do not guarantee the optimality of the solution but which, for many problems, can find nearly optimal solutions within a reasonable amount of computational time. The literature on heuristic algorithms often distinguishes between two broad classes: constructive algorithms and improvement algorithms. A constructive algorithm builds a solution from scratch by assigning values to one or more decision variables at a time. An improvement algorithm starts with a feasible solution and iteratively tries to improve it. Neighborhood search algorithms, also called local search algorithms, are a wide class of improvement algorithms that at each iteration search the “neighborhood ” of the current solution to find an improved solution. A neighborhood search algorithm for a discrete optimization problem P (where we wish to minimize an objective function over a finite discrete set of objects) starts with a feasible solution x 1 of the problem. For each feasible solution x, an associated neighborhood of x, denoted N(x), is a set of feasible solutions that can be obtained by perturbing the solution x using some prespecified scheme. The elements of N(x) are called neighbors of x. The neighborhood search iteratively obtains a sequence x 1, x 2, x 3,... of feasible solutions. At the kth iteration, the algorithm determines a solution x k+1 with a lower objective function value than x k, if one exists. The algorithm terminates when it finds a solution that is at least as good as any of its neighbors; such a solution is called a locally optimal solution. Typically, multiple run