A Lagrangean/surrogate heuristic for the maximal covering location problem using Hillsman's edition

The Maximal Covering Location Problem (MCLP) deals with the location of the facilities in order to attend the largest subset of a population within a service distance. Many successful heuristic approaches have been developed to solve this problem. In this work we use the Unified Linear Model developed by Hillsman to adapt the distance coefficients of a p-median problem to reflect the demand information of a population. This transformation permits the application of a Lagrangean/surrogate heuristic developed for solving p-median problems to solve the MCLP. In previous works this heuristic proved to be very affordable, providing good quality solutions in reduced computational times. Computational tests for random generated scenarios ranging from 100 to 900 vertices and GIS-referenced instances of São José dos Campos city (Brazil) were conducted, showing the effectiveness of the combined approach.