Local Search Heuristics for Capacitated p-Median Problems

The search for p-median vertices on a network (graph) is a classical location problem. The p facilities (medians) must be located so as to minimize the sum of the distances from each demand vertex to its nearest facility. The Capacitated p-Median Problem (CPMP) considers capacities for the service to be given by each median. The total service demanded by vertices identified by p-median clusters cannot exceed their service capacity. Primal-dual based heuristics are very competitive and provide simultaneously upper and lower bounds to optimal solutions. The Lagrangean/surrogate relaxation has been used recently to accelerate subgradient like methods. The dual lower bound have the same quality of the usual Lagrangean relaxation dual but is obtained using modest computational times. This paper explores improvements on upper bounds applying local search heuristics to solutions made feasible by the Lagrangean/surrogate optimization process. These heuristics are based on location-allocation procedures that swap medians and vertices inside the clusters, reallocate vertices, and iterate until no improvements occur. Computational results consider instances from the literature and real data obtained using a geographical information system.