论文标题
平面最大覆盖位置问题，部分覆盖范围，连续的空间需求和可调节的服务质量
Planar Maximum Coverage Location Problem with Partial Coverage, Continuous Spatial Demand, and Adjustable Quality of Service
论文作者
论文摘要
我们考虑对允许部分覆盖范围的经典平面最大覆盖位置问题（PMCLP）的概括，设施具有可调节的服务质量（QoS）或服务范围，并且每个设施的需求区域和服务区域都由二维空间对象表示，例如矩形，圆圈，Polygons，Polygons，Polygons等。这个问题的主要挑战是同时确定设施在连续的二维平面及其QoS上的位置。我们提出了一种贪婪的算法和伪绿色算法，并提供了它们的近似值。我们还研究了理论特性，并提出了解决求解的精确算法：（1）PMCLP-PC-QO，其中需求和服务区以轴平行矩形（由PMCLP-PCR-QOS表示）表示，该矩形在摄像机监测和卫星成像中也具有应用； （2）在河流清理中应用的一维PMCLP-PC-QO。这些结果扩展并加强了Bansal和Kianfar的固定和相同QoS的唯一已知的PMCLP-PCR-QO的唯一已知的精确算法[通知计算期刊29（1），152-169，2017]。我们介绍了进行计算实验的结果，以评估我们提出的精确和近似算法的性能。
We consider a generalization of the classical planar maximum coverage location problem (PMCLP) in which partial coverage is allowed, facilities have adjustable quality of service (QoS) or service range, and demand zones and service zone of each facility are represented by two-dimensional spatial objects such as rectangles, circles, polygons, etc. We denote this generalization by PMCLP-PC-QoS. A key challenge in this problem is to simultaneously decide position of the facilities on a continuous two-dimensional plane and their QoS. We present a greedy algorithm and a pseudo-greedy algorithm for it, and provide their approximation ratios. We also investigate theoretical properties and propose exact algorithms for solving: (1) PMCLP-PC-QoS where demand and service zones are represented by axis-parallel rectangles (denoted by PMCLP-PCR-QoS), which also has applications in camera surveillance and satellite imaging; and (2) one dimensional PMCLP-PC-QoS which has applications in river cleanups. These results extend and strengthen the only known exact algorithm for PMCLP-PCR-QoS with fixed and same QoS by Bansal and Kianfar [INFORMS Journal on Computing 29(1), 152-169, 2017]. We present results of our computational experiments conducted to evaluate the performance of our proposed exact and approximation algorithms.
