In this talk, we study the p-median problem with the addition of a coverage constraint which requires the total customer demand, covered at a distance greater than a prespecified coverage distance, to be smaller than or equal to a given threshold. We propose an efficient Benders decomposition (BD) approach for solving large-scale problems. We show that both Benders feasibility and optimality cuts can be separated in efficient combinatorial polynomial-time algorithms. Moreover, we enhance the BD approach by using tight initial cuts to initialize the relaxed master problem, implementing an effective two-stage algorithm to find high-quality solutions, and adding valid inequalities to strengthen the problem formulation. Computational results on benchmark instances show that the proposed BD approach outperforms the state-of-the-art general-purpose MIP solver's branch-and-cut and automatic BD algorithms by at least one order of magnitude.