A maximal covering location model in the presence of partial coverage

Karasakal O., Karasakal E.

COMPUTERS & OPERATIONS RESEARCH, vol.31, no.9, pp.1515-1526, 2004 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 31 Issue: 9
  • Publication Date: 2004
  • Doi Number: 10.1016/s0305-0548(03)00105-9
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.1515-1526
  • Keywords: location, maximal covering problem, partial coverage, Lagrangean relaxation
  • Middle East Technical University Affiliated: Yes


The maximal covering location problem (MCLP) addresses the issue of locating a predefined number of facilities in order to maximize the number of demand points that can be covered. In a classical sense, a demand point is assumed to be covered completely if located within the critical distance of the facility and not covered at all outside of the critical distance. Since the optimal solution to a MCLP is likely sensitive to the choice of the critical distance, determining a critical distance value when the coverage does not change in a crisp way from "fully covered" to "not covered" at a specific distance may lead to erroneous results. We allow the coverage to change from "covered" to "not-covered" within a distance range instead of a single critical distance and call this intermediate coverage level partial coverage, In this paper, we formulate the MCLP in the presence of partial coverage, develop a solution procedure based on Lagrangean relaxation and show the effect of the approach on the optimal solution by comparing it with the classical approach. (C) 2003 Elsevier Ltd. All rights reserved.