基于Power圖求解容量限制P中值問題

1、基于Power圖求解容量限制P中值問題摘要： 針對稠密需求下連續(xù)域上的容量P中值問題，提出基于質(zhì)心的容量限制Power圖CCCPD理論，對連續(xù)P中值問題進展近似建模，并加快計算過程。擴展Balzer試位法構造Power圖，施加質(zhì)心限制滿足P中值要求，施加容量限制滿足需求密度下的容量要求。實驗結(jié)果說明所提算法可快速得到近似可行解，同Alper Murata方法相比，計算效率高；同質(zhì)心容量限制Voronoi圖CCCVT相比，具有容量限制準確度高等優(yōu)點，并能適應各種復雜需求密度函數(shù)。關鍵詞： P中值；連續(xù)域；容量限制；Power圖；質(zhì)心中圖分類號： TP 391.9 文獻標志碼：A英文摘要Abstr

2、act：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

3、 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，

4、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；

5、continuous domain； capacity constraint； Power diagram； centroid0 引言本文引入基于質(zhì)心的容量限制Power圖 Centroidal Capacity Constrained Power Diagram，CCCPD方法，對連續(xù)域上連續(xù)密度的容量限制P中值問題進展近似建模。在Power圖根底上，施加質(zhì)心限制滿足P中值要求，施加容量限制滿足需求密度下的容量要求。 1 CCCPD模型1.1 Power圖3 算法結(jié)果和分析3.1 CCCPD算法時間分析將本文CCCPD算法同Murat所提的連續(xù)分析框架Continuous Analysis

6、Framework，CAF7進展比較，CAF算法中用任意密度函數(shù)來描繪稠密需求的情況，采用梯度下降法來求解復雜的微分方程，不斷迭代更新站點Voronoi區(qū)域的邊界，最終為每個站點分配固定代價、容量獲取代價最優(yōu)區(qū)域。該算法沒有考慮容量限制但采用了普通間隔 。本文受CAF啟發(fā)，使用Power圖理論對稠密需求區(qū)域分配進展建模。其中測試密度函數(shù)采用文獻7定義的線性分布密度給出縮略語英文全稱Linear Density，LD和非線性密度分布NonLinear Density，NLD，精度統(tǒng)一設置為1.0E-3，如下：實驗結(jié)果如表1所示。CCCPD較CAF算法時間性能上有了大幅度的進步，但是CAF中側(cè)重于

7、容量獲取代價，同時間隔 的定義是歐氏間隔 ，CCCPD算法更側(cè)重于容量限制，這是由于Power圖有著準確限制容量的特性。3.2 連續(xù)域容量限制的P中值實例根據(jù)CCCPD算法，實現(xiàn)對連續(xù)密度下容量限制P中值選址問題的求解。圖2中分別給出不同形狀邊界和不同密度的連續(xù)域，以及每個站點的容量限制。首先進展隨機放置40個站點，然后根據(jù)CCCPD優(yōu)化，最后結(jié)果如圖2所示：圖2b 連續(xù)密度下均勻容量限制實例中使用的連續(xù)密度從左至右分別為x+y-202、x+y2、x+y-20；圖2c中灰度的不同說明該站點所轄區(qū)域的容量與其他站點容量有異。由實驗結(jié)果可知，不同情況下的P中值選址布局之間存在著較大的差異。3.3

8、應用實例根據(jù)表2所示進展。由表3分析得知，同CCCVT相比，CCCPD中cc非常小，容量限制更加準確，這是由于CCCPD算法將容量限制作為第一優(yōu)化目的的結(jié)果。另一方面， 同CCCPD相比，CCCVT中cvt較小，更符合P中值要求，這是由于CCCVT更加強調(diào)效勞代價更優(yōu)的結(jié)果。由此，本文的CCCPD和文獻9的CCCVT互為補充，可以適應不同的容量限制P中值問題的實際要求。4 結(jié)語Balzer所提試位法未實如今非常密度下的容量限制Power圖的構造，本文在此根底上拓展了該試位法，并提出基于質(zhì)心的容量限制Power圖近似解決連續(xù)域容量限制的P中值問題，研究結(jié)果說明該算法具有效率高、容量限制準確度高、可視化效果好、需求密度函數(shù)適應性強等優(yōu)點。同時本文所提算法對于應急救助中心、超市或者醫(yī)院的位置選址有著一定的規(guī)劃和分配指導。下一步工作包括進一步加速CCCPD求解、利用CCCPD解決固定設施分配效勞區(qū)問題等。參考文獻：16DU Q， FABER V， GUNZBURGER M. Centroidal Vo