Efficient optimization of maximal covering location problems using extreme value estimation

Facility location decision is a critical element in strategic planning for a wide range of public sectors and business world. Maximal Covering Location Problem is one of the well-known models for facility location problems. Considering its NP-hard nature, numerous efforts have been devoted to the development of intelligent algorithms for this problem. In order to evaluate the quality of a given solution, we integrate k-interchange heuristic and extreme value theory to statistically estimate the upper bound of the global optimal objective value. Based on this statistical bound, a new simulated annealing algorithm is proposed to solve the maximal covering location problems. Computational results show that the proposed algorithm can obtain better near optimal solutions than the existing algorithms. ©2009 IEEE.