  This paper investigates why it is beneficial, when solving a problem, to
search in the neighbourhood of a current solution. The paper identifies
properties of problems and neighbourhoods that support two novel proofs that
neighbourhood search is beneficial over blind search. These are: firstly a
proof that search within the neighbourhood is more likely to find an improving
solution in a single search step than blind search; and secondly a proof that a
local improvement, using a sequence of neighbourhood search steps, is likely to
achieve a greater improvement than a sequence of blind search steps. To explore
the practical impact of these properties, a range of problem sets and
neighbourhoods are generated, where these properties are satisfied to different
degrees. Experiments reveal that the benefits of neighbourhood search vary
dramatically in consequence. Random problems of a classical combinatorial
optimisation problem are analysed, in order to demonstrate that the underlying
theory is reflected in practice.
