A New Meta-Heuristic for Improving General Multi-Start Procedures

Abstract In this paper we propose a new and effective meta-heuristic, named POST, that improves the performance of multi-start improvement algorithms. It is a general follow-up (or post-optimizing) procedure that attempts to find a better final solution than the best one found by any multi-start approach. The additional required effort and run time is negligible.The meta-heuristic is tested on the planar p-median multi-facility location problem which is known to have many (perhaps millions for the instances tested in this paper) local optima. Forty-eight well researched instances were tested, and the meta-heuristic improved the best known solution for all of them, in about the same run time required by the multi-start approach.