  


Planar Maximum Coverage Location Problem with Partial Coverage and Rectangular Demand and Service Zones
Manish Bansal (bansalvt.edu) Abstract: 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 only 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 services zones to be rectangular instead of squares, thereby addressing applications in camera viewframe selection as well. More specifically, our problem, referred to as PMCLPPCR, is to position a given number of rectangular service zones (SZs) on the twodimensional 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 PMCLPPCR much more challenging to solve. In this paper, we first prove that PMCLPPCR is NPhard if the number of SZs is part of the input. We then present an improved algorithm for the singleSZ PMCLPPCR, which is at least two times faster than the existing exact Plateau Vertex Traversal algorithm. Next, we study multiSZ PMCLPPCR for the first time and prove theoretical properties which significantly reduce the search space for solving this problem and present a customized branchandbound exact algorithm to solve it. Our computational experiments show that this algorithm can solve relatively large instances of multiSZ PMCLPPCR 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). Keywords: partial coverage; planar maximum covering location problem; rectilinear distance; facility location; rectangle positioning; planar pcenter problem; NPhard; branchandbound Category 1: Combinatorial Optimization Citation: M. Bansal, K. Kianfar, "Planar maximum coverage location problem with partial coverage and rectangular demand and service zones," INFORMS Journal on Computing 29(1), 152169, 2017. Download: Entry Submitted: 10/01/2014 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  