Groupe d’études et de recherche en analyse des décisions

G-2002-21

Convergence of Variable Neighborhood Search

, et

This paper examines the convergence properties of two well-known heuristics: variable neighborhood search (VNS) and random multistart local search (MLS). Both methods are shown to be globally convergent under general conditions. A multistart variable neighborhood search is introduced as a hybrid combination of VNS and MLS. The finite time performance of the three heuristics is compared on a well-known continuous location problem, the multisource Weber problem. This study also attempts to explain why the structured approach of VNS obtains superior results to multistart local search.

, 15 pages

Ce cahier a été révisé en janvier 2004