基于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 Ba❥lzers 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 引言

本文引入基于质心的容量限制Power图 （Centroidal Capaci♀ty 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 应用实例

依据表2所示进行。由表3分析得知，同CCCVT相比，CCCPD中δcc非常小，容量限制更加精确，这是由于CCCPD算法将容量限制作为第一优化目标的结果。

另一方面， 同CCCPD相比，CCCVT中δcvt较小，更符合P中值要求，这是由于CCCVT更加强调服务代价更优的结果。由此，本文的CCCPD和文献[9]的CCCVT互为补充，可以适应不同的容量限制P中值问题的实际要求。

4 结语

Balzer所提试位法未实现在非常密度下的容量限制Power图的构造，本文在此基础上拓展了该试位法，并提出基于质心的容量限制Power图近似解决连续域容量限制的P中值问题，研究结果表明该算法具有效率高、容量限制精确度高、可视化效果好、需求密度函数适应性强等优点。⌛同时本文所提算法对于应急救助中心、超市或者医院的位置选址有着一定的规划和分配指导。下一步工作包括进一步加速CCCPD求解、利用CCCPD解决固定设施分配服务区问题等。

参考文献：

[16]DU Q， FABER V， GUNZBURGER M. Centroidal Voronoi tessellations： applications and algorithms [J]. SIAM Review， 1999， 41（4）： 637-676.