An empirical comparison of five efficient heuristics for Maximal Covering Location Problems

Facility location decision is a critical element in strategic planning for a wide range of public sector and business world. Maximal Covering Location Problem (MCLP) is one of the well-known models for facility location problems. Algorithms to optimally solve this kind of practical operational management problem often suffer from the combinatorial explosion when the system size increases. In these cases, heuristic methods are the only viable alternative. A lot of work has been devoted to the study of heuristics for MCLP. But there lacks a complete comparison of different methods. In this paper, we compare the relative performance of five efficient heuristic methods: Greed-Add, Interchange, Efficient Genetic Algorithm (GA), Efficient Tabu Search (TS), and Efficient Simulated Annealing (SA). The results indicate: Greedy-Add can achieve relatively good solutions in a very short time; GA-based algorithm performs not as successfully as it used to do in most combinatorial problems; and Efficient SA always gets the best solution among all the five algorithms. Thus, in general we may conclude that Efficient SA should often be tried first for this kind of problems.