Very Large-scale Neighborhood Search

In mathematical optimization, Neighborhood Search is a technique that tries to find good or near-optimal solutions to a mathematical optimization problem by repeatedly trying to improve the current solution by looking for a better solution which is in the neighborhood of the current solution. In that sense, the neighborhood of the current solution includes a possibly large number of solutions which are near to the current solution. Obviously, there is a degree of looseness in that definition in that the neighborhood might include just those solutions that require a single change from the current solution, or it might include the larger set of solutions that differ in two or more values from the current solution. A very large-scale neighborhood search is a local search algorithm which makes use of a neighborhood definition, which is large and possibly exponentially sized.

The resulting algorithms are often far superior to algorithms using small neighborhoods because the local improvements are larger. If the neighborhood searched is limited to just one or a very small number of changes from the current solution, then it is often very difficult to escape from local minima and additional meta-heuristic techniques may need to be used such as Simulated Annealing or Tabu Search to allow the search process to escape from a local minimum. In large neighborhood search techniques, the possible changes from one solution to its neighbor may allow tens or hundreds of values to change, and this means that the size of the neighborhood may itself be sufficient to allow the search process to avoid or escape local minima. As a result, it is often unnecessary to introduce additional meta-heuristic techniques.