基于GIS技术谈谈最大化地区覆盖之连续设备选址问题
第 1章 引言
1.1 研究背景
1.1.1 课题背景
选址问题是指确定设施位置，使得需求置于设施所能提供服务范围之内。该问题有着广泛的应用，比如工业生产中工厂以及仓库的选址、物流领域中配送中心的选址。在经济活动中，财富的积累靠的是在扩大利润的同时降低成本。随着工业化进程的加快，产销分离意味着商品在流通过程中有着十分庞大的物流作业，物流成本居高不下成为现代企业快速发展的一个瓶颈。在企业的物流决策过程中，选址问题是最重要的长期决策之一，比如配送中心选址，其建设成本以及再建设成本很高，所以一旦决策短期内将不再调整，属于一次性决策；另外，选址的好坏直接影响着企业运作成本以及服务质量。选址失误将导致企业运作的高成本低效率，成为企业快速发展的桎梏甚至决定企业的命运。
选址问题不仅在各项经济活动中起着降低成本、提高效率等重要作用，还在公共服务领域有更具重要意义的应用。比如城市建设中的消防设施选址、急救中心选址、灾害预警装置选址等，此类选址问题不以获取经济利益为目标，而是提供更广泛更便捷的服务给更多的需求群体。好的公共服务设施选址意味着：病人临危时救护车能够第一时间赶到，火灾发生时消防车能够及时到达，台风等自然灾害来临之前能给全部城市居民警报，这将挽救人的生命并且避免财产损失。如果公共服务设施选址不合理，在紧急危难情况时无法为其城市居民提供救助服务，这将为社会带来巨大的财产损失甚至是灾难，而且也会降低城市居民对政府或城市建设者的信任，这种公信力的缺失将会给社会造成极其恶劣的影响，因此，公共服务领域的设施选址问题应给予高度重视。但值得注意的是，不管是选址决策的目标还是模型约束条件，公共服务领域设施选址都区别于追求利润的经济活动设施选址，它是一个相对较独立的服务设施选址问题。
基本选址问题包括P-中值问题、P-中心问题以及覆盖问题，而设施覆盖问题又主要分为最大覆盖问题和集覆盖问题。覆盖问题在公共服务设施领域应用较为广泛，其目标是将需求区域置于设施所能提供服务范围之内，此处的服务范围即为设施的覆盖半径，多以辐射距离或旅行时间来衡量。比如，对于无线网络信号发射器来说，其服务范围指的是其信号所能到达的最远有效距离；对于消防车来说，其服务范围指的是在接到报警电话后消防车能够在特定时间内所能到达的地点。由于公共服务设施领域中需求未被覆盖将产生严重的后果，故此类覆盖问题的目标是将需求区域全部覆盖为最佳。所以，覆盖问题是确定最优设施数目和最优设施位置从而实现需求区域近似完全覆盖。
1.2 本文的研究重点
通过整理设施选址问题的相关文献了解到，前人对于覆盖问题的离散化模型有较深入的研究，同时也有颇多文献指出离散覆盖模型解决需求和设施均连续分布的选址问题存在大量误差。虽然也有相关文献提出了新的解决方法来消除或最大限度减少此类误差，比如Church首先提出了连续设施最大覆盖问题，其允许设施建立在任意地方，需求以点表示，使用圆相交点集（Circle Intersect Point Set，CIPS）将设施候选位置由连续区域转化为有限点集，并证明了圆相交点集办法获得的有限点集中包含最优解；Alexandris 和Giannios使用空间对象比如多边形来表示需求，使用GIS的覆盖识别功能可将多个设施对某个需求区域的部分覆盖考虑进模型去。但此两方面的研究均只解决了需求为连续分布或设施候选位置为连续分布两者之中一方面的问题，与实际应用场景仍有较大差异。另外，纵观设施覆盖问题的文献，大多数都是基于某种覆盖模型比如集覆盖模型或者最大覆盖模型对设施选址问题进行研究的。研究内容多为分析离散问题产生的误差，以及如何来减少这些误差。很少有文献是从问题出发，给出一整套解决此类问题的完整思路，各种方法的通用性差。
基于上述对相关文献的总结，本文的研究重点是基于GIS的需求为区域的连续设施选址问题。随着地理信息系统技术的发展，其在越来越多的领域有着相当重要的应用。本文将GIS应用到设施选址领域中，使用的是GIS的空间分析功能中的多边形叠加功能以及区域面积量算功能，来获得设施对需求区域的实际覆盖率。此种方法完全区别于以点来表示需求获得的需求覆盖率，以点表示需求当全部点被完全覆盖时，整个需求区域并未被完全覆盖从而引入了误差，而使用 GIS获得的实际需求覆盖率可以很好的消除此类误差。
本文将给出完整的解决思路来实现使用合理的设施数目完成需求区域的高覆盖率。在求解过程中，我们将证明连续覆盖问题转化为离散覆盖问题是存在误差的，并深入分析误差产生的原因，然后设计出一种高效的优化算法来尽可能减少甚至是消除此种误差。本文设计的优化算法实现了设施在整个候选区域内的连续选址，同时GIS的使用可以获得实际需求覆盖率，这样将从理论上实现连续设施选址和需求连续分布这两个难以使用模型来描述的覆盖问题，最后通过实际算例分析证明本文解决此类问题的方法是切实有效的，可以最大限度的减少离散覆盖模型引入的误差。
第 2章 文献综述
本章节主要从四个方面来介绍文献综述。本文研究的是需求为区域的连续设施选址问题，首先介绍设施选址问题的相关研究，主要介绍覆盖问题；其次分析传统解决覆盖问题的方法离散覆盖模型引入的误差；针对误差，前人已做过相应的研究来消除或最大限度减少误差，所以紧接着介绍连续设施选址问题和地理信息系统在选址中的应用，这两个方向的研究是从两个角度来减少离散模型误差的。连续设施选址实现了设施在整个候选区域建设的连续性，地理信息系统可以获得实际的需求覆盖率从而实现了需求连续分布的选址问题求解。通过研读前人在此领域的相关文献，找到了仍存在的不足之处以及解决此问题可借鉴的方法，从而找到本文解决该问题的研究思路。
2.1 设施选址问题的分类概述
最初的设施选址问题是 Alfred Weber 提出的1-media 模型即著名的 Weber问题，其解决了单个仓库到多个顾客的总距离最小的问题。随着应用场景的逐渐扩大，选址模型也呈现多样化。不管模型如何变化，最终可归为三种基本选址问题：P-中值问题（p-media problems），P-中心问题（p-center problems），覆盖问题，其中覆盖问题又包括集覆盖问题和最大覆盖问题。选址问题分类如下图2.1所示。
P-中值问题与 P-中心问题是由 Haimi1964 年提出的，这两类模型在网络选址问题中有较广泛的应用。P-中值问题是指给定设施数 P，确定设施的位置使得需求点到其分配设施的距离与相应的需求量乘积之和最小。这其中网络中的节点既是需求点也是设施候选点，且至少存在一个最优解使得目标函数最小。Garey和ohnson证明了此类问题是NP-难问题。之后，Chen和Handler 研究了条件中值问题，即网络中已有 M个设施存在的情况下，新增N个同类设施使得网络设施规划更加完善的问题。P-中心问题是指在网络中给定 P 个设施，使得全部需求点到与其最近设施的距离之中最大值最小化的问题。ariv和 Haimi证明P-中心问题是NP-难问题，Yuri Levin，AdiBen-Israel给出了大规模P-中心问题的启发式算法。
覆盖问题是选址理论的重要组成部分，首先明确设施的覆盖半径。假设顾客并不一定总是到距他最近的服务站接受服务，而是在一定距离以内的服务站都可以为其提供服务，那么这个距离就是设施的覆盖半径。例如一个消防部门在接到火灾报警电话之后能够在少于某个规定时间之内赶到事故现场则表明该区域已被覆盖。这实际上是应急服务设施提供紧急服务的一个普遍标准，大城市中响应时间最大值通常介于5-30分钟。另一个例子是一个城镇（城市，省份等）都在紧急警报装置（比如台风警报）的声音覆盖范围之内。如果发现了台风或其他恶劣天气，报警装置就会发出声音来提醒城镇居民。但是警报声音传播也有覆盖范围限制，其中一种是全方位最大有效覆盖范围为 970 米的警报装置。如果需求点到某个候选服务站之间的最短路距离小于或等于覆盖半径，则认为该需求点被该服务站覆盖。由此可见，物理距离和技术革新在设施覆盖方面扮演着重要的角色。比如，多普勒雷达用于天气监测和预报，能提供 460 千米范围内的水分反射率信息；无线接入网络的一种服务DSL（Digital Subscriber Line）要求客户处于电话公司中心办公室一定距离范围之内才可接收到信号。
2.2 连续覆盖问题离散化引入误差的研究
在以往的研究中，覆盖问题多为离散问题，即需要被覆盖的需求和设施候选位置均为离散点集，若要获得将整个区域完全覆盖所需要设施数目，则使用集覆盖模型；若要求解在给定设施数目的情况下尽可能多的覆盖需求点集，则使用最大覆盖模型。总之，传统的模型可以解决离散的覆盖问题。但现实应用场景的覆盖问题大多是这样的：其需求为区域（比如台风预警装置的需求为整个城镇或城市），且设施候选位置为任意（比如台风预警装置可以设立在城镇的任意地方，河流、高海拔山脉除外，这可将其从地图上除掉），这种情况下使用离散覆盖模型求出的最优解对于实际问题不一定是最优解，甚至效果很差。
由于以面表示需求或在连续区域内建立设施的问题十分复杂，故多以离散的思想来考虑覆盖问题，但此番做法同时也引入了误差。设施选址问题中将需求数据聚合于一点将会导致次优解，该影响对于覆盖问题更甚因为覆盖问题的距离测度为二进制。Murray和Oelly研究了集覆盖模型下，以不同离散规则获得的点集来表示需求和设施候选位置，最终模型求解优化的结果存在较大误差和不准确性。实验分析表明，以点代替需求获得的覆盖率要高于实际覆盖率，当需求点完全被覆盖时需求区域并不一定被完全覆盖；设施位置、设施数目、计算时间以及覆盖误差均随着需求空间表示的不同而有很大变化，整个区域的覆盖误差处于 0.43%和 27%之间。但该论文也证明了当需求点密度足够大的时候，覆盖误差将会降到很低。但由于覆盖问题本身是 NP-难问题，当需求点数目很大时在有效时间内给出覆盖问题的最优解几乎是不可能的。George Alexandris 和 Ioannis Giannios 通过对希腊雅典地区进行实例分析，证明了最大覆盖模型下使用不同离散间隔的需求点对最终需求覆盖率产生很大影响。
第3章 总体思路与算法介绍.................. 16
3.1 合适设施数目范围的确定 ..................... 18
3.2 基于离散需求点获得初始最优解 .................. 20
3.3 算法设计思路 ......................... 22
第4章 算例分析 ..................33
4.1 技术路线 .............. 33
4.2 集覆盖模型获得设施数目................ 34
4.3 不同离散间隔下最大覆盖模型初始解差异...................... 36
第5章 结论 ..................... 51
第 4章 算例分析
本文实例研究的对象是美国俄亥俄州都柏林城市，其地图边界如图4.1所示，地图中间空白部分为山脉、河流等不适宜建立设施的区域，故将其从地图上删除。该城市面积大约60平方千米，有29，000城市居民（1998年估计），本文为其规划应急警报装置的布局问题。将该城市作为研究对象的原因是为与选址问题的其他文献做研究对照，诸如Current 和Oelly（1992）、Murray和Oelly（2002）、Murray，Oelly 和 Church（2002）等均使用该城市进行覆盖问题的研究。本文中的应急设施是有效传播范围为 976 米的全方位声音警报装置，当出现台风、暴风雨等灾害时给整个城市的居民以警报提示，所以整个柏林城市视为分布均匀的需求区域。由于城市预算有限，故应使用尽量合理数目的装置完成对都柏林城市尽量大范围的覆盖。
第 5章 结论
本文研究的是需求为区域的连续设施选址问题，其本质上是设施在整个区域内任意位置建立以求将需求区域最大化覆盖的覆盖问题。与前人对此类问题的研究角度不同，他们试图通过建立新模型来描述区域覆盖或在设施候选区域中找到CIPS 点集或 PIPS 点集来完成连续设施选址，但这些方法只是解决了一方面的问题，并没有真正实现与现实应用场景相匹配。本文从另外一个角度出发，不是考虑直接建立与现实应用场景相符的新模型，而是在离散模型的基础上使用优化的思想来减少将连续问题离散化而带来的误差。通过识别出离散化连续问题的误差来源，本文设计了两种贪心算法来最大限度的减少误差。算例分析证明，在相同设施数目下离散间隔不同时，使用最大覆盖模型获得的需求覆盖率存在显著差异，而本文的优化算法将大大减少这种差异，使最终结果趋于一致。另外，本文的优化算法实现了在整个区域内寻找最优设施位置，同时使用GIS的空间分析功能与量算功能来获得设施对需求区域的覆盖率，此种衡量覆盖大小的方法与传统意义上的以点代面有较严格的区别，在优化算法中设施的每一次移动都以此需求覆盖率为衡量标准，若需求覆盖率增加则接受设施的移动，否则拒绝设施的移动。本文优化算法的设计思路从理论上消除了连续覆盖问题离散化所带来的误差，同时算例分析也给出了很好的实例证明，优化算法使得离散模型获得的初始覆盖率有了较大提高。
另外，本文给出了解决需求为区域的连续设施选址问题的一种整体思路。覆盖问题首先要确定设施数目，然后是设施最优位置。首先使用集覆盖模型获得设施数目，使用GIS获得设施覆盖需求区域的图形来了解不同设施数目的覆盖中重叠部分与空白部分的多少，从而确定设施数目范围进行后续研究。其次给定设施数目和设施覆盖半径的前提下，使用最大覆盖模型给出设施最优位置，任意离散间隔下的需求点集都可以用来获得初始最优解。在初始最优解的基础上使用优化算法来获得最终需求覆盖率，由于不同离散间隔获得的初始解经过优化之后其最终结果趋于一致，所以离散间隔的选择具有任意性。当然如果离散间隔过大导致需求点集十分稀疏，使得获得的初始需求覆盖率与实际最优覆盖率有较大误差，那么接下来的优化过程将会花费较多时间。
参考文献（略）