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.