改進(jìn)的虛擬力最大覆蓋選址算法研究

汪浩祥，李 娜，李強(qiáng)懿

1.南京農(nóng)業(yè)大學(xué) 工學(xué)院，南京 210031

2.南京航空航天大學(xué) 計(jì)算機(jī)與科技學(xué)院，南京 211106

1 引言

選址問(wèn)題（CLP）一直都是供應(yīng)鏈中十分重要的一環(huán)，配送中心的位置不僅關(guān)系到客戶的服務(wù)水平高低還直接影響到整個(gè)配送過(guò)程的成本高低，所以一直以來(lái)都十分受學(xué)者們的重視?？偟恼f(shuō)來(lái)，目前選址模型的研究多集中在最大覆蓋位置問(wèn)題（MCLP）和集合覆蓋位置問(wèn)題（SCLP）。覆蓋問(wèn)題是傳統(tǒng)選址模型的一個(gè)經(jīng)典問(wèn)題，最早是由Church和ReVelle[1]在1974年提出的，并被廣泛應(yīng)用于各個(gè)領(lǐng)域，尤其是針對(duì)公共設(shè)施比如醫(yī)院、郵局、公園、學(xué)校的選址上有著許多應(yīng)用。

Zarandi 等人[2]利用模擬退火算法對(duì)大規(guī)模動(dòng)態(tài)覆蓋選址進(jìn)行了詳細(xì)的求解，所提出的算法能滿足2 500個(gè)節(jié)點(diǎn)和200個(gè)配送樞紐的服務(wù)需求，同時(shí)也填補(bǔ)了之前的研究對(duì)大規(guī)模動(dòng)態(tài)覆蓋問(wèn)題關(guān)注不足的問(wèn)題。Araz等人[3]提出了多目標(biāo)的最大覆蓋選址，考慮了基于覆蓋的應(yīng)急車輛定位模型的多目標(biāo)模糊目標(biāo)規(guī)劃。最終的目標(biāo)在于以更短的總運(yùn)輸距離來(lái)提高服務(wù)覆蓋面積和服務(wù)水平。Erdemir 等人[4]提出了在節(jié)點(diǎn)和路徑都產(chǎn)生需求情況下的最大覆蓋問(wèn)題，針對(duì)兩種需求開(kāi)發(fā)了兩個(gè)不同的模型；針對(duì)節(jié)點(diǎn)的需求用通過(guò)基于模擬退火算法的貪婪算法對(duì)二次最大覆蓋位置問(wèn)題進(jìn)行計(jì)算，針對(duì)路徑的需求通過(guò)幾何數(shù)學(xué)來(lái)進(jìn)行計(jì)算；最后通過(guò)對(duì)移動(dòng)手機(jī)用戶和處于移動(dòng)狀態(tài)的手機(jī)用戶的追蹤數(shù)據(jù)確定了紐約州伊利縣移動(dòng)服務(wù)站的位置。Berman 等人[5]討論了網(wǎng)絡(luò)中存在負(fù)權(quán)情況下的最大覆蓋問(wèn)題，提出了該問(wèn)題整數(shù)規(guī)劃算法，并基于ILOG CPLEX 軟件進(jìn)行了算法實(shí)現(xiàn)；針對(duì)包含40個(gè)最大覆蓋問(wèn)題的數(shù)據(jù)集，分別采用上升算法和模擬退火算法這兩種啟發(fā)式算法進(jìn)行求解與測(cè)試，最終表明模擬退火算法能夠獲得更好的結(jié)果。Alexandris 等人[6]通過(guò)對(duì)地理信息系統(tǒng)的使用和對(duì)部分覆蓋思想的闡述對(duì)傳統(tǒng)的覆蓋模型進(jìn)行了一定的擴(kuò)展，得出相比較傳統(tǒng)覆蓋模型而言新模型對(duì)需求節(jié)點(diǎn)有了更大比例的覆蓋。Corrêa等人[7]提出用列生成和覆蓋圖的方法解決最大概率覆蓋問(wèn)題，將圖論引入到了覆蓋問(wèn)題中。

Church 和ReVelle[8]證明了最大覆蓋問(wèn)題在加入強(qiáng)制性覆蓋范圍的情況下可以等價(jià)于p中值問(wèn)題，進(jìn)而討論了適用于p中值問(wèn)題的方法也適用于最大覆蓋問(wèn)題，例如Maranzana[9]所提出的帶權(quán)重的頂點(diǎn)中位數(shù)的啟發(fā)式算法，在合理地選擇初始值的情況下該算法可以得到很不錯(cuò)的結(jié)果，由于該算法是將服務(wù)點(diǎn)分配給最近的節(jié)點(diǎn)來(lái)服務(wù)，若同等距離則優(yōu)先分配給更小的節(jié)點(diǎn)，所以在出現(xiàn)零權(quán)重時(shí)會(huì)出現(xiàn)算法無(wú)法收斂的情況?；诖薚eitz 和Bart[10]提出了基于加權(quán)圖廣義頂點(diǎn)中位數(shù)估計(jì)的啟發(fā)式方法，很好地解決了Maranzana算法不可收斂的問(wèn)題，該算法通過(guò)遍歷未被選定的潛在點(diǎn)，一旦該點(diǎn)產(chǎn)生更好的結(jié)果，則當(dāng)前節(jié)點(diǎn)被替換，但遍歷的結(jié)果導(dǎo)致該算法的復(fù)雜度極高。Chiyoshi等人[11]在Teitz和Bart的頂點(diǎn)替換方法的基礎(chǔ)上結(jié)合了模擬退火算法，提出了應(yīng)用于p中值問(wèn)題的模擬退火的方法，該算法先通過(guò)模擬退火算法尋找出最適合的可能會(huì)用于交換的頂點(diǎn)，在該頂點(diǎn)產(chǎn)生更優(yōu)結(jié)果的情況下進(jìn)行替換，模擬退火算法的使用極大地提高了該算法的效率，但同時(shí)一個(gè)點(diǎn)也可能會(huì)存在被多次選中的情況，但與Teitz 和Bart 的算法相比，該算法的復(fù)雜度降低了50%以上。

Church 和ReVelle[8]提出的在最大覆蓋選址加入強(qiáng)制的封閉性約束，將最大覆蓋問(wèn)題轉(zhuǎn)化成p中值問(wèn)題來(lái)求解，這一轉(zhuǎn)化的確使得問(wèn)題簡(jiǎn)化，但是p中值問(wèn)題所圍繞的解決目標(biāo)都是最小化（路徑，成本，時(shí)間）問(wèn)題，這一求解特性使得該模型與最大覆蓋問(wèn)題有最原始的背反；同時(shí)在實(shí)際中存在更多的是非線性的情況，也就是說(shuō)并非每一個(gè)最大覆蓋選址模型都可以通過(guò)加入強(qiáng)制性范圍約束轉(zhuǎn)化成一個(gè)純線性的p中值問(wèn)題來(lái)求解?；诟倪M(jìn)的虛擬力的配送中心選址算法以最大覆蓋率為目標(biāo)，以最終迭代的最大覆蓋率節(jié)點(diǎn)所在位置為最優(yōu)點(diǎn)，不用費(fèi)力轉(zhuǎn)化從所有潛在的優(yōu)值中找到一個(gè)或者幾個(gè)更優(yōu)值；同時(shí)基于改進(jìn)的虛擬力的配送中心選址算法考慮到了配送系統(tǒng)中每一個(gè)客戶對(duì)節(jié)點(diǎn)及節(jié)點(diǎn)對(duì)節(jié)點(diǎn)之間的影響，將每一個(gè)可能的約束轉(zhuǎn)化成力的影響也能更加直觀地反映系統(tǒng)的即時(shí)狀況。

國(guó)內(nèi)對(duì)最大覆蓋選址的研究在初期主要是對(duì)所用方法的分類和對(duì)國(guó)外學(xué)者的借鑒。喬聯(lián)寶[12]在其2015年的綜述里將覆蓋選址問(wèn)題分為確定性選址模型和概率選址模型兩大類。其中確定性選址中包含了集合覆蓋和最大覆蓋問(wèn)題，概率選址模型中又包括了概率集合覆蓋模型、最大期望覆蓋模型、最大可獲得性覆蓋模型。肖建華等人[13]提出了基于非等半徑覆蓋選址的膜計(jì)算方法來(lái)對(duì)生鮮農(nóng)產(chǎn)品的配送中心進(jìn)行選址。馬云峰等人[14]考慮了基于時(shí)間滿意度來(lái)進(jìn)行的最大覆蓋問(wèn)題選址。劉慧等人[15]考慮了最低服務(wù)水平下的聯(lián)合覆蓋選址問(wèn)題的選址效益。魏延青等人[16]根據(jù)受災(zāi)區(qū)域的受災(zāi)程度進(jìn)行了分層，考慮到不同受災(zāi)區(qū)域的物品需求滿意度和救災(zāi)預(yù)算成本等因素，并以救災(zāi)物資需求滿意度為目標(biāo)建立了最大問(wèn)題覆蓋選址模型，最后，通過(guò)實(shí)際數(shù)值實(shí)驗(yàn)，討論了不同預(yù)算成本下和各受災(zāi)區(qū)域物資各不相同的滿足標(biāo)準(zhǔn)對(duì)物資分配中心的數(shù)量和地址的影響。

從以上覆蓋問(wèn)題的發(fā)展方向來(lái)看，主要的解決方法幾乎都是依靠著現(xiàn)代計(jì)算機(jī)而逐步發(fā)展起來(lái)的智能算法，同時(shí)前人對(duì)動(dòng)態(tài)覆蓋選址模型的理解并不完全是“動(dòng)態(tài)”[17]。本文為了改善配送中心部署時(shí)的不合理分布，提高服務(wù)覆蓋率，以配送中心覆蓋率為優(yōu)化目標(biāo)，設(shè)計(jì)了一種將移動(dòng)選址過(guò)程分為多個(gè)步驟的配送中心移動(dòng)方案，通過(guò)不斷比較各個(gè)配送中心之間所受虛擬力的大小，使配送中心逐漸移動(dòng)到更合理的位置，以提高配送網(wǎng)絡(luò)的覆蓋率，與文獻(xiàn)[18]所不同的是本文不需要考慮配送中心的總移動(dòng)距離，模型中的移動(dòng)對(duì)選址來(lái)說(shuō)只是一個(gè)虛擬的過(guò)程，所要求的最短移動(dòng)距離只是對(duì)移動(dòng)過(guò)程的一個(gè)約束，并不存在任何成本，本文所關(guān)注的重點(diǎn)在于最終的移動(dòng)結(jié)果。

本文將配送區(qū)域離散化成像素格子來(lái)進(jìn)行配送中心的選址，在這一抽象平均化的條件下配送中心可以在所設(shè)置的條件進(jìn)行移動(dòng)，根據(jù)虛擬力配送中心在一次次的移動(dòng)過(guò)程中逐漸到達(dá)更優(yōu)的位置，最終所抵達(dá)的位置就是使得覆蓋率最高的位置，也是最符合預(yù)期的選址位置。

2 問(wèn)題描述與模型構(gòu)建

2.1 問(wèn)題描述

本文將整個(gè)需要服務(wù)的市場(chǎng)區(qū)域覆蓋率Rarea定義為能被給定的配送中心所能經(jīng)濟(jì)服務(wù)到的（在其配送半徑以內(nèi)的稱為經(jīng)濟(jì)服務(wù)，超出服務(wù)半徑以外的則稱為不經(jīng)濟(jì)配送）客戶的面積Aarea和整個(gè)需要服務(wù)的市場(chǎng)區(qū)域總面積As之比，目標(biāo)是最大化區(qū)域覆蓋面積。為方便問(wèn)題求解，假設(shè)：

（1）各個(gè)配送中心能夠獲取自身和所有其他配送中心的位置信息。

（2）配送中心位置移動(dòng)過(guò)程中不考慮其他因素。

（3）配送中心有相同的服務(wù)半徑Rd和通信半徑Rc，其中通訊半徑為全局覆蓋半徑。

（4）各個(gè)客戶點(diǎn)pi的需求都是相同的。

2.2 模型構(gòu)建

本文相關(guān)符號(hào)說(shuō)明如下：

（1）Rd：配送中心的服務(wù)半徑；

（2）Rc：配送中心的通信半徑；

（3）Re：感知誤差范圍；

（4）Rarea：配送覆蓋率；

（5）Aarea：被經(jīng)濟(jì)服務(wù)到的客戶總面積；

（6）As：需要被服務(wù)的客戶總面積；

（7）Pmin：最低感知概率，在單個(gè)配送中心P(pi,dj)≥Pmin時(shí)，則pi被服務(wù)到；

（8）λ：pi釋放出的信息強(qiáng)度，信息越強(qiáng)則越容易被感知到，根據(jù)指數(shù)分布的特點(diǎn)和引力定律，λ的值越小則在距離越近的情況下越容易被感知到；

（9）β：配送中心的感知能力參數(shù)，本文根據(jù)萬(wàn)有引力定理將其取值為2；

（10）j：配送中心的編號(hào)，每個(gè)配送中心有唯一編號(hào)；

（11）i：客戶的編號(hào)，每個(gè)客戶也有唯一編號(hào)；

（12）Rd'：障礙物配送中心對(duì)其他配送中心的有效影響距離；

（13）pi：第i個(gè)客戶；

（14）dj：第j個(gè)配送中心；

（15）d(di,dj)：配送中心di和dj之間的距離；

（16）Mdj：第j個(gè)配送中心的質(zhì)量；

（17）F(pi,dj)：第i個(gè)客戶對(duì)第j個(gè)配送中心的作用力；

（18）di'：第i個(gè)障礙物配送中心；

（19）α：配送中心的作用能力參數(shù)，本文根據(jù)萬(wàn)有引力定理將其定為2；

（20）Fmin：虛擬力的最小起作用值；

（21）Maxstep：是配送中心dj所允許的最大移動(dòng)距離；

（22）Nj：配送中心dj的鄰居列表；

（23）m：循環(huán)次數(shù)。

為建立本文數(shù)學(xué)模型，首先給出如下定義：

定義1第i個(gè)客戶pi被第j個(gè)配送中心dj所服務(wù)到的概率定義為P(pi,dj)，即：

其中，d(pi,dj)是第i個(gè)客戶與第j個(gè)配送中心dj之間的距離，Rd是該配送中心的服務(wù)范圍。

客戶點(diǎn)pi被所有的配送中心服務(wù)的概率為：

根據(jù)上述定義，假設(shè)二維平面配送區(qū)域內(nèi)有A×B個(gè)客戶，每個(gè)客戶面積大小表示為Δx×Δy，第i個(gè)客戶點(diǎn)可以被配送網(wǎng)絡(luò)服務(wù)的概率為P(pi)，當(dāng)P(pi,dj)≤Pmin時(shí)，P(pi)=0，則該客戶點(diǎn)未被配送網(wǎng)絡(luò)中的任一個(gè)配送中心所服務(wù)到；當(dāng)P(pi,dj)≥Pmin時(shí)，P(pi)=1，該客戶點(diǎn)可視為被配送網(wǎng)絡(luò)所服務(wù)。第i個(gè)客戶點(diǎn)pi是否被配送網(wǎng)絡(luò)的配送中心所服務(wù)到用Pcov(pi)來(lái)衡量，即：

根據(jù)上述定義，建立本文數(shù)學(xué)模型如式（4）所示：

目標(biāo)為最大化區(qū)域覆蓋率Rarea。

3 改進(jìn)的虛擬力算法

基于改進(jìn)的虛擬力的最大覆蓋選址模型受啟發(fā)于物理學(xué)中的帶電微粒，帶電粒子之間互相存在引力和斥力，這一理論在無(wú)線傳感器放置領(lǐng)域已經(jīng)有了很多的應(yīng)用[19]。假設(shè)服務(wù)區(qū)域?yàn)殡妶?chǎng)，配送中心為電場(chǎng)中的帶電粒子，這樣配送中心之間存在相互作用的力，在這些力的作用下使得配送中心盡可能地分布合理提高配送中心對(duì)所服務(wù)區(qū)域的覆蓋效果。基于改進(jìn)的虛擬力的選址模型中，如果兩個(gè)配送中心之間距離較遠(yuǎn)則引力起到主要作用，如果距離過(guò)近則斥力起到主要作用。同時(shí)，如果存在障礙物，則該障礙物對(duì)其起到斥力作用，服務(wù)區(qū)的邊界對(duì)配送中心既起到引力作用又起到斥力作用，這樣可以避免服務(wù)區(qū)域邊界出現(xiàn)較大的覆蓋漏洞。

3.1 配送中心移動(dòng)方案

在整個(gè)服務(wù)范圍區(qū)域內(nèi)隨機(jī)分配N個(gè)配送中心，用dj代表配送中心網(wǎng)絡(luò)中的第j個(gè)配送中心，則配送中心節(jié)點(diǎn)集合為D={d1,d2,…,dj,…,dN}。

改進(jìn)的虛擬力算法是將配送網(wǎng)絡(luò)假設(shè)為一個(gè)包含力、加速度和質(zhì)量的虛擬物理系統(tǒng)，配送中心、障礙物和服務(wù)區(qū)域均可以對(duì)配送中心產(chǎn)生引力或斥力，配送中心移動(dòng)的方向和距離取決于該配送中心自身的位置，以及所受相鄰配送中心節(jié)點(diǎn)的引力與斥力的合力，配送中心節(jié)點(diǎn)需要移動(dòng)到受力平衡的位置。

（1）配送中心受相鄰配送中心節(jié)點(diǎn)間的斥力

任意兩個(gè)配送中心節(jié)點(diǎn)di和dj，則配送中心di受到配送中心節(jié)點(diǎn)dj的斥力可表示為：

配送中心之間的距離過(guò)遠(yuǎn)時(shí)，引力不起作用；距離過(guò)近時(shí)，兩個(gè)配送中心不可能同時(shí)錨定在同一個(gè)位置，所以在配送中心之間的作用力只考慮斥力。

（2）配送中心受到客戶pi引力

配送中心節(jié)點(diǎn)dj受到來(lái)自客戶pi的引力作用，引力可表示為：

每一個(gè)客戶都要盡可能地“吸引”更多的配送中心來(lái)服務(wù)他，不存在要把配送中心推到一邊的做法，所以客戶和配送中心之間只存在引力這一種作用力。

（3）配送中心受到來(lái)自障礙物的斥力

為防止配送中心在移動(dòng)過(guò)程中碰到不可錨定的位置，在不可錨定的位置設(shè)置障礙物，為了保證系統(tǒng)的連續(xù)性，將障礙物設(shè)置為具有固定位置的配送中心，這些配送中心對(duì)其他的配送中心只產(chǎn)生斥力，使其他配送中心不會(huì)移動(dòng)到該障礙配送中心的位置。則配送中心dj受到障礙配送中心di'的斥力可表示為：

（4）配送中心所受到的合力

對(duì)任意的配送中心dj，將客戶、配送中心節(jié)點(diǎn)和障礙物對(duì)配送中心的作用力分別建立二維坐標(biāo)軸進(jìn)行分解，則配送中心dj受到作用力可以表示為：

沿X軸的合力：

沿Y軸的合力：

受到的合力：

為了降低算法的復(fù)雜度，在本文中不設(shè)置障礙物，假設(shè)整個(gè)服務(wù)區(qū)都可以作為配送中心錨定的地點(diǎn)，同時(shí)因?yàn)榕渌椭行呐c配送中心之間的斥力存在是為了任意兩個(gè)配送中心錨定的地點(diǎn)不重合，在移動(dòng)過(guò)程中這個(gè)問(wèn)題不會(huì)發(fā)生，加上兩個(gè)質(zhì)量相同的物體所產(chǎn)生的斥力在整個(gè)系統(tǒng)中是趨于平衡的，所以式（8）和（9）中的后兩項(xiàng)作用力對(duì)配送中心的移動(dòng)過(guò)程影響很小，可以忽略不計(jì)。

（5）配送中心的移動(dòng)方案

通過(guò)計(jì)算以配送中心節(jié)點(diǎn)dj為圓心，Rd為服務(wù)半徑的圓形區(qū)域內(nèi)的客戶pi被感知的概率，決定配送中心dj的移動(dòng)，配送中心會(huì)不斷地朝著感知概率低的地方移動(dòng)，同時(shí)感知概率低的地方也是配送中心節(jié)點(diǎn)比較稀疏的地點(diǎn)。如果配送中心dj所受的虛擬力小于最小起作用值，則不需要移動(dòng)。

配送中心dj經(jīng)過(guò)受力計(jì)算后，根據(jù)所受合力的大小將配送中心節(jié)點(diǎn)從原位置(xj,yj)移動(dòng)到新位置(xj',yj')。

在整個(gè)移動(dòng)過(guò)程中，配送中心的位置可能會(huì)超出所規(guī)定的服務(wù)范圍邊界，這樣明顯是不合理的。如果在一次移動(dòng)中，新的位置位于服務(wù)范圍的外部，則這一次移動(dòng)不再進(jìn)行，也就是該配送中心的位置坐標(biāo)同上一次的移動(dòng)結(jié)果保持一致。

3.2 算法步驟

步驟1對(duì)服務(wù)區(qū)中的每一個(gè)配送中心所釋放出的信息進(jìn)行檢測(cè)，讀取每個(gè)配送中心的編號(hào)和位置信息，進(jìn)入步驟2。

步驟2如果配送中心dj收到鄰居節(jié)點(diǎn)所發(fā)出的信息，更新其鄰居列表Nj的信息，進(jìn)入步驟3。

步驟3通過(guò)定義1 中的公式計(jì)算出配送中心dj周圍半徑為Rd+Re的圓形區(qū)域中客戶pi的被感知的概率P(pi)，進(jìn)入步驟4。

步驟4通過(guò)公式（5）～（12）計(jì)算出配送中心dj需要移動(dòng)到的新位置(xj',yj')，如果需要移動(dòng)到的位置位于服務(wù)區(qū)域的外側(cè)，則該次移動(dòng)不發(fā)生，進(jìn)入步驟5，否則移動(dòng)到新位置再進(jìn)入步驟5。

步驟5如果達(dá)到設(shè)置的算法循環(huán)次數(shù)則算法退出，否則轉(zhuǎn)向步驟1，進(jìn)行新的循環(huán)過(guò)程。

4 仿真結(jié)果及分析

使用Matlab軟件對(duì)該算法進(jìn)行仿真，假設(shè)在300 km×300 km 的服務(wù)區(qū)域A 中隨機(jī)確定N個(gè)配送中心，配送中心的服務(wù)半徑Rd=60 km,β=2,λ=0.2,α=2，通信半徑300 km，感知誤差范圍Re=1 km，移動(dòng)過(guò)程m=200次，最低感知概Pmin=0.9，最低感知概率越低則客戶被服務(wù)到的概率越大，同時(shí)被重復(fù)服務(wù)的概率也越大，但是服務(wù)的穩(wěn)定性不夠，且所需要的配送中心數(shù)量也會(huì)更多些，在實(shí)驗(yàn)過(guò)后選擇在Pmin=0.9 的感知概率下更符合實(shí)際情況。隨機(jī)放置的配送中心的覆蓋率是在5 000次模擬之后取得的平均值。為了防止配送中心移出服務(wù)區(qū)域A，如果配送中心的新位置移動(dòng)到服務(wù)區(qū)域A內(nèi)部20 km 寬的邊緣區(qū)域時(shí)，配送中心節(jié)點(diǎn)將不會(huì)移動(dòng)，仍處于原位置。

令N=5，6，7，8，9，10，11，12，13，14，15，分別采用隨機(jī)部署和本文基于改進(jìn)虛擬力算法進(jìn)行仿真，兩種部署算法的覆蓋率如表1所示。

表1 兩種部署方法的覆蓋率 %

圖1 到圖8 為算法仿真的部分結(jié)果，每張圖中的圈代表每個(gè)配送中心的覆蓋范圍，圓心代表配送中心最后錨定的位置。

圖1 當(dāng)N=5 時(shí)基于改進(jìn)的虛擬力算法

圖2 當(dāng)N=6 時(shí)基于改進(jìn)的虛擬力算法

圖3 當(dāng)N=7 時(shí)基于改進(jìn)的虛擬力算法

圖4 當(dāng)N=8 時(shí)基于改進(jìn)的虛擬力算法

圖5 當(dāng)N=10 時(shí)基于改進(jìn)的虛擬力算法

圖6 當(dāng)N=12 時(shí)基于改進(jìn)的虛擬力算法

圖7 當(dāng)N=14 時(shí)基于改進(jìn)的虛擬力算法

兩種部署方法覆蓋率比較如圖9所示。

仿真結(jié)果表明，基于改進(jìn)的虛擬力算法讓覆蓋率平均提升了22.58%，這意味著可以用更少的配送中心來(lái)服務(wù)更多的客戶，極大地降低了配送的成本。從圖1到圖8 可以看出在N=10 之后配送中心覆蓋范圍的重合度越來(lái)越高，配送中心的利用效率逐漸降低。同時(shí)，從表1與圖9可以看出，當(dāng)N大于12以后，覆蓋率提升的邊際效應(yīng)就逐漸接近于0 了，出于經(jīng)濟(jì)考慮，選擇更少的配送中心來(lái)完成工作顯然會(huì)更為合理。

圖8 當(dāng)N=15 時(shí)基于改進(jìn)的虛擬力算法

圖9 兩種算法結(jié)果的比較

5 總結(jié)

基于改進(jìn)的虛擬力的配送中心選址算法根據(jù)配送中心節(jié)點(diǎn)周圍區(qū)域的被感知概率進(jìn)行移動(dòng)，使配送中心節(jié)點(diǎn)向感知概率低的區(qū)域移動(dòng)，在配送中心節(jié)點(diǎn)密集處也能實(shí)現(xiàn)理想的效果，使配送中心逐漸移動(dòng)到最佳的監(jiān)測(cè)位置，在提高覆蓋率的同時(shí)減少了每個(gè)配送中心移動(dòng)的距離，使配送中心移動(dòng)距離的總和較小，也就使得仿真所需的時(shí)間相對(duì)較少；同時(shí)基于改進(jìn)的虛擬力的覆蓋選址模型可以支持異構(gòu)的配送中心，也更符合實(shí)際的生產(chǎn)情況。

在未來(lái)的研究中可以嘗試從客戶的地理分布隨機(jī)，客戶需求情況隨機(jī)入手進(jìn)行單個(gè)或者組合考慮；還可以考慮配送中心異構(gòu)的問(wèn)題（給配送中心分類），在異構(gòu)的條件下根據(jù)配送中心的能力來(lái)確定其配送半徑，再結(jié)合客戶需求隨機(jī)的情況使得該問(wèn)題在覆蓋方面的研究更加貼近現(xiàn)實(shí)情況。