基于Power圖求解容量限制P中值問(wèn)題

1、基于Power圖求解容量限制P中值問(wèn)題摘要： 針對(duì)稠密需求下連續(xù)域上的容量P中值問(wèn)題，提出基于質(zhì)心的容量限制Power圖CCCPD理論，對(duì)連續(xù)P中值問(wèn)題進(jìn)展近似建模，并加快計(jì)算過(guò)程。擴(kuò)展Balzer試位法構(gòu)造Power圖，施加質(zhì)心限制滿足P中值要求，施加容量限制滿足需求密度下的容量要求。實(shí)驗(yàn)結(jié)果說(shuō)明所提算法可快速得到近似可行解，同Alper Murata方法相比，計(jì)算效率高；同質(zhì)心容量限制Voronoi圖CCCVT相比，具有容量限制準(zhǔn)確度高等優(yōu)點(diǎn)，并能適應(yīng)各種復(fù)雜需求密度函數(shù)。關(guān)鍵詞： P中值；連續(xù)域；容量限制；Power圖；質(zhì)心中圖分類(lèi)號(hào)： TP 391.9 文獻(xiàn)標(biāo)志碼：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.英文關(guān)鍵詞Key words： Pmedian；

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

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

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

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