Some heuristic methods for solving p-median problems with a coverage constraint

► p-Median problems with an additional coverage constraint (CONPMP) are studied. ► Local search procedures, as well as a multistart GRASP heuristic, are developed. ► A Lagrangean relaxation based heuristic is designed for CONPMP. ► Computational results show that these procedures are efficient to solve CONPMP. ► The model allows to studying the trade off between distance and coverage.