The aim of this paper is to solve p‐median problems with an additional coverage constraint. These problems arise in location applications, when the trade‐off between distance and coverage is being calculated. Three kinds of heuristic algorithms are developed. First, local search procedures are designed both for constructing and improving feasible solutions. Second, a multistart GRASP heuristic is developed, based on the previous local search methods. Third, by employing Lagrangean relaxation methods, a very efficient Lagrangean heuristic algorithm is designed, which extends the well known algorithm of Handler and Zang, for constrained shortest path problems, to constrained p‐median problems. Finally, a comparison of the computational efficiency of the developed methods is made between a variety of problems of different sizes.
