Attraction probabilities in variable neighborhood search

Empirical evidence demonstrates that when the same local search operator is used, variable neighborhood search consistently outperforms random multistart local search on all types of combinatorial and global optimization problems tested. In this paper we suggest that this superiority in performance may be explained by the distribution of the attraction basins around a current solution as a function of the distance from the solution. We illustrate with a well-known instance of the multisource Weber problem that the ‘attraction probabilities’ for finding better solutions can be orders of magnitude larger in neighborhoods that are close to the current solution. The paper also discusses the global convergence properties of both general methods in the context of attraction probabilities.