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.
Paru en mai 2002 , 15 pages
Ce cahier a été révisé en janvier 2004