基于Power图求解容量限制P中值问题
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于Power图求解容量限制P中值问题范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要： 针对稠密需求下连续域上的容量P中值问题，提出基于质心的容量限制power图（CCCPD）理论，对连续P中值问题进行近似建模，并加快计算过程。扩展Balzer试位法构造Power图，施加质心限制满足P中值要求，施加容量限制满足需求密度下的容量要求。实验结果表明所提算法可快速得到近似可行解，同Alper Murata方法相比，计算效率高；同质心容量限制Voronoi图（CCCVT）相比，具有容量限制精确度高等优点，并能适应各种复杂需求密度函数。
关键词： P中值；连续域；容量限制；Power图；质心
中图分类号： TP 391.9 文献标志码：A
英文摘要
Abstract：Aiming at the capacity Pmedian problem of continuous domains under the dense demand， the Centroidal Capacity Constrained Power Diagram （CCCPD） theory was proposed to approximately model the continuous Pmedian problem and accelerate the solving process. The Power diagram was constructed by extended Balzers method， centroid restriction was imposed to satisfy the requirements of Pmedian， and capacity constraint was imposed to meet the capacity requirements of certain demand densities. The experimental results show that the proposed algorithm can quickly obtain an approximate feasible solution， having the advantages of better computing efficiency and capacity accuracy compared to Alper Muratas method and Centroidal Capacity Constrained Voronoi Tessellation （CCCVT） respectively. Additionally， the proposed method has excellent adaptability to complex density functions.
英文关键词
Key words： Pmedian； continuous domain； capacity constraint； Power diagram； centroid
0 引言
P中值问题（Pmedian）是选址布局中的典型问题[1]。P中值选址即将一系列市场需求作为被服务区域，给每个被服务区域分配一个单独的设施，使目标函数值最小（如成本、平均距离最小等）。P中值问题可用线性规划、整数规划和松弛方法来求解。进一步，容量限制的P中值问题中对每个设施服务容量进行限制，以解决特定情况下的选址分配问题，如医疗救助站的规划和分配[2]、网络分布设计[3]等。由于容量限制P中值问题的复杂性，通常采用近似启发式算法求解，文献[4]使用改进的分散搜索算法解决容量限制P中值问题，文献[5]使用布谷鸟搜索法（Cuckoo Search，CS）和Kmeans混合算法以及文献[6]中提出数学试探算法等。
目前对于P中值问题研究主要集中在离散域，而连续域中的P中值问题大多数集中在常密度或者密度变化很小的连续近似密度情况下。连续密度下的容量限制P中值问题求解被证明是一个NPhard问题，一般采用各种优化技术以得到局部最优解。Murat在2010年[7]和2011年[8]提出的算法解决效果好但计算效率较低。郑利平等在文献[9]中使用基于质心的Voronoi图（Centroidal Voronoi Tessellation，CVT）方法来对连续P中值问题进行建模，在此基础上通过等式约束法进行容量限制，可生成非均匀容量的CVT，在首先满足P中值要求下，尽量同容量限制约束进行折中。考虑CVT总是倾向于均匀容量分布，因此该方法无法施加精确的容量限制，会存在较大误差。
考虑容量限制P中值问题中，P中值和容量限制往往难以同时优化达成全局最优，本文在文献[7]和文献[9]工作基础上，从另外一个角度，选择以容量限制为第一优化目标，然后尽量满足P中值要求。因此，由于在容量限制方面的优势，本文采用Power图作为建模方法。Power图已有大量相关研究工作，文献[10]提出Power图理论并率先证明了容量限制Power图（Capacity Constrained Power Diagram，CCPD）存在。在CCPD的计算方面，Balzer等给出了面向有限空间[11]和连续空间[12]的CCPD计算方法。目前Power图已经广泛地应用到各个领域，如信息可视化[13]、地理信息系统（Geographic Information System，GIS）[14]和图像处理[15]等。
本文引入基于质心的容量限制Power图 （Centroidal Capacity Constrained Power Diagram，CCCPD）方法，对连续域上连续密度的容量限制P中值问题进行近似建模。在Power图基础上，施加质心限制满足P中值要求，施加容量限制满足需求密度下的容量要求。
1 CCCPD模型
1.1 Power图
3 算法结果和分析
3.1 CCCPD算法时间分析
将本文CCCPD算法同Murat所提的连续分析框架（Continuous Analysis Framework，CAF）[7]进行比较，CAF算法中用任意密度函数来描述稠密需求的情况，采用梯度下降法来求解复杂的微分方程，不断迭代更新站点Voronoi区域的边界，最终为每个站点分配固定代价、容量获取代价最优区域。该算法没有考虑容量限制但采用了普通距离。
本文受CAF启发，使用Power图理论对稠密需求区域分配进行建模。其中测试密度函数采用文献[7]定义的线性分布密度给出缩略语英文全称（Linear Density，LD）和非线性密度分布（NonLinear Density，NLD），精度统一设置为1.0E-3，如下：
实验结果如表1所示。CCCPD较CAF算法时间性能上有了大幅度的提高，但是CAF中侧重于容量获取代价，同时距离的定义是欧氏距离，CCCPD算法更侧重于容量限制，这是由于Power图有着精确限制容量的特性。
3.2 连续域容量限制的P中值实例
根据CCCPD算法，实现对连续密度下容量限制P中值选址问题的求解。图2中分别给出不同形状边界和不同密度的连续域，以及每个站点的容量限制。首先进行随机放置40个站点，然后根据CCCPD优化，最后结果如图2所示：图2（b） 连续密度下均匀容量限制实例中使用的连续密度从左至右分别为（x+y-20）2、（x+y）2、x+y-20；图2（c）中灰度的不同表明该站点所辖区域的容量与其他站点容量有异。由实验结果可知，不同情况下的P中值选址布局之间存在着较大的差异。
3.3 应用实例
连续域上容量限制的P中值问题可用于解决应急中心的选址布局。城市灾害突发，每个应急救援中心救助一定数量的人口，而城市人口为应急中心的服务对象，应急中心救援能力有限，故属于连续域容量限制的P中值问题。下面以合肥市为例，文献[9]给出的合肥市人口密度为e的指数是否可用exp（）表示。可以。没问题。27931*exp（-0.003*（（x-29）2+（y-45）2）-0.001*（（x-29）2+（y-45）2）1/2），图3（a）是得到的人口密度函数分布图。在该区内设置三种类型应急中心25个，每个应急中心有不同的救援容量，并设定各个应急中心的救援能力限制。图3（b）给出了每个应急中心均匀（即相同）容量限制下的布局结果，而图3（c）则是加入如表2所示容量限制后的结果，图3（d）所表示的是在各应急中心的救援能力随机为是1万～10万人，还是1个人～10万人。是前者。1～10万人限制下的布局结果。表2给出了图3（c）情况下的各个应急中心的初始位置和容量限制，以及优化后的应急中心位置、实际人口容量和容量误差率，并同文献[9]中的容量误差率进行比较，其中CCCVT算法选取α/β为0.1，即容量限制相对占优情况[9]。设容量误差率为：
综合对比结果如表3所示。实验中，选取CCCVT算法α/β为10即相对占优情况，在同样25个站点下实验，非均匀密度采用图3（a）的密度函数，非均匀容量的设置
依据表2所示进行。由表3分析得知，同CCCVT相比，CCCPD中δcc非常小，容量限制更加精确，这是由于CCCPD算法将容量限制作为第一优化目标的结果。
另一方面， 同CCCPD相比，CCCVT中δcvt较小，更符合P中值要求，这是由于CCCVT更加强调服务代价更优的结果。由此，本文的CCCPD和文献[9]的CCCVT互为补充，可以适应不同的容量限制P中值问题的实际要求。
4 结语
Balzer所提试位法未实现在非常密度下的容量限制Power图的构造，本文在此基础上拓展了该试位法，并提出基于质心的容量限制Power图近似解决连续域容量限制的P中值问题，研究结果表明该算法具有效率高、容量限制精确度高、可视化效果好、需求密度函数适应性强等优点。同时本文所提算法对于应急救助中心、超市或者医院的位置选址有着一定的规划和分配指导。下一步工作包括进一步加速CCCPD求解、利用CCCPD解决固定设施分配服务区问题等。
参考文献：
[1]CHAN Y. Facility location： a survey of applications and methods， springer series in operations research by Z. Drezner [J]. Transportation Science， 1999， 33（4）： 429-430.
[2]KUNKEL A G， ITALLIE E S V， WU D. Optimal distribution of medical backpacks and health surveillance assistants in Malawi [J]. Health Care Management Science， 2014， 17（3）： 230-244.
[3]FLESZAR K， HINDI K S. An effective VNS for the capacitated pmedian problem [J]. European Journal of Operational Research， 2008， 191（3）： 612-622.
[4]XU X， LI X， LI X， et al. Notice of retraction an improved scatter search algorithm for capacitated pmedian problem [C]// Proceedings of the 2010 2nd International Conference on Computer Engineering and Technology. Piscataway： IEEE， 2010， 2： V2316-V2320.
[5]MAZINAN H G， AHMADI G R， KHAJI E. An efficient hybrid CS and kmeans algorithm for the capacitated pmedian problem [EB/OL]. [2014-12-08]. http：///abs/1406.7473.
[6]STEFANELLO F， de ARAUJO O C B， MLLER F M. Matheuristics for the capacitated pmedian problem [J]. International Transactions in Operational Research， 2014， 22（1）： 149-167.
[7]MURAT A， VERTER V， LAPORTE G. A continuous analysis framework for the solution of locationallocation problems with dense demand [J]. Computers and Operations Research， 2010， 37（1）：123-136.
[8]MURAT A， VERTER V， LAPORTE G. A multidimensional shooting algorithm for the twofacility locationallocation problem with dense demand [J]. Computers and Operations Research， 2011， 38（2）： 450-463.
[9]ZHENG L， LIU Y， JIANG T， et al. A layout approach of city emergency centers with dense demand [J]. Journal of ComputerAided Design & Computer Graphics， 2014， 26（6）： 948-955.（郑利平，刘玉飞，江婷，等.稠密需求下城市应急中心布局方法[J]. 计算机辅助设计与图形学学报，2014，26（6）：948-955.）
[10]AURENHAMMER F， HOFFMANN F， ARONOV B. Minkowskitype theorems and leastsquares clustering [J]. Algorithmica， 1998， 20（1）： 61-76.
[11] BALZER M and HECK D. Capacityconstrained Voronoi diagrams in finite spaces [C]// Proceedings of the 5th Annual International Symposium on Voronoi Diagrams in Science and Engineering. 跟作者核实文献要素，是否可参照文献12Piscataway： IEEE， 2008： 44-56. （Kiev， Ukraine） （Kokichi Sugihara and Deok-Soo Kim， eds.）
[12]BALZER M. Capacityconstrained Voronoi diagrams in continuous spaces [C]// ISVD09： Proceedings of the 2009 Sixth International Symposium on Voronoi Diagrams. Piscataway： IEEE， 2009： 79-88.
[13]BALZER M， DEUSSEN O. Voronoi treemaps [C]// INFOVIS05： Proceedings of the 2005 IEEE Symposium on Information Visualization. Washington， DC： IEEE Computer Society， 2005： 49-56.与文献11重复，是否应删除，若删除，文中文献引用标注要变，请作者检查核实。不重复，文献11排错了
[14]REITSMA R， TRUBIN S， MORTENSEN E. Weightproportional space partitioning using adaptive Voronoi diagrams [J]. GeoInformatica， 2007， 11（3）： 383-405.
[15]BALZER M， SCHLMER T， DEUSSEN O. Capacityconstrained point distributions： a variant of Lloyds method [EB/OL]. [2014-12-03]. http：//citeseerx.ist.psu.edu/viewdoc/summary？doi=10.1.1.177.6047.
[16]DU Q， FABER V， GUNZBURGER M. Centroidal Voronoi tessellations： applications and algorithms [J]. SIAM Review， 1999， 41（4）： 637-676.
[17]MACQUEEN J. Some methods for classification and analysis of multivariate observations [EB/OL]. [2014-12-03]. http：//citeseerx.ist.psu.edu/viewdoc/summary？doi=10.1.1.308.8619.
[18]CORTES J， MARTINEZ S， KARATAS T， et al. Coverage control for mobile sensing networks[C]// ICRA02：Proceedings of the 2002 IEEE International Conference on Robotics and Automation. Piscataway： IEEE， 2002： 1327-1332.