Planar Maximum Coverage Location Problem with Partial Coverage and Rectangular Demand and Service Zones

摘要

We study the planar maximum coverage location problem (MCLP) with rectilinear distance and rectangular demand zones in the case where "partial coverage" is allowed in its true sense, i.e., when covering part of a demand zone is allowed and the coverage accrued as a result of this is proportional to the demand of the covered part only. We pose the problem in a slightly more general form by allowing service zones to be rectangular instead of squares, thereby addressing applications in camera view-frame selection as well. More specifically, our problem, referred to as PMCLP-PCR (planar MCLP with partial coverage and rectangular demand and service zones), is to position a given number of rectangular service zones (SZs) on the two-dimensional plane to (partially) cover a set of existing (possibly overlapping) rectangular demand zones (DZs) such that the total covered demand is maximized. Previous studies on (planar) MCLP have assumed binary coverage, even when nonpoint objects such as lines or polygons have been used to represent demand. Under the binary coverage assumption, the problem can be readily formulated and solved as a binary linear program; whereas, partial coverage, although much more realistic, cannot be efficiently handled by binary linear programming, making PMCLP-PCR much more challenging to solve. In this paper, we first prove that PMCLP-PCR is NP-hard if the number of SZs is part of the input. We then present an improved algorithm for the single-SZ PMCLP-PCR, which is at least two times faster than the existing exact plateau vertex traversal algorithm. Next, we study multi-SZ PMCLP-PCR for the first time and prove theoretical properties that significantly reduce the search space for solving this problem, and we present a customized branch-and-bound exact algorithm to solve it. Our computational experiments show that this algorithm can solve relatively large instances of multi-SZ PMCLP-PCR in a short time. We also propose a fast polynomial time heuristic algorithm. Having optimal solutions from our exact algorithm, we benchmark the quality of solutions obtained from our heuristic algorithm. Our results show that for all the random instances solved to optimality by our exact algorithm, our heuristic algorithm finds a solution in a fraction of a second, where its objective value is at least 91% of the optimal objective in 90% of the instances (and at least 69% of the optimal objective in all the instances).