汪浩祥，李 娜，李強懿

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

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

1 引言

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

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

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

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

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

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

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

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

2.1 問題描述

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

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

（2）配送中心位置移動過程中不考慮其他因素。

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

（4）各個客戶點pi的需求都是相同的。

2.2 模型構(gòu)建

本文相關(guān)符號說明如下：

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

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

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

（4）Rarea：配送覆蓋率；

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

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

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

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

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

（10）j：配送中心的編號，每個配送中心有唯一編號；

（11）i：客戶的編號，每個客戶也有唯一編號；

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

（13）pi：第i個客戶；

（14）dj：第j個配送中心；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 改進的虛擬力算法

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

3.1 配送中心移動方案

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

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

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

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

配送中心之間的距離過遠時，引力不起作用；距離過近時，兩個配送中心不可能同時錨定在同一個位置，所以在配送中心之間的作用力只考慮斥力。

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

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

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

（3）配送中心受到來自障礙物的斥力

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

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

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

沿X軸的合力：

沿Y軸的合力：

受到的合力：

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

（5）配送中心的移動方案

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

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

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

3.2 算法步驟

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 總結(jié)

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

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