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

 Overview

 Research

 Identity

 Additional Document Info

 View All

Overview
abstract

© 2017 INFORMS. 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 viewframe selection as well. More specifically, our problem, referred to as PMCLPPCR (planar MCLP with partial coverage and rectangular demand and service zones), 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 that significantly reduce the search space for solving this problem, and we 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).
published proceedings

INFORMS Journal on Computing
author list (cited authors)

Bansal, M., & Kianfar, K.
citation count
complete list of authors

Bansal, ManishKianfar, Kiavash
publication date
publisher
published in
Research
keywords

Branch And Bound

Facility Location

Nphard

Partial Coverage

Planar Maximum Covering Location Problem

Planar Pcenter Problem

Rectangle Positioning

Rectilinear Distance
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue