改進的虛擬力最大覆蓋選址算法研究

汪浩祥，李 娜，李強懿

1.南京農業大學 工學院，南京 210031

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

1 引言

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

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

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

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

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

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

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

2 問題描述與模型構建

2.1 問題描述

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

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

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

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

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

2.2 模型構建

本文相關符號說明如下：

（1）Rd：配送中心的服務半徑；

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

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

（4）Rarea：配送覆蓋率；

（5）Aarea：被經濟服務到的客戶總面積；

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

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

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

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

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

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

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

（13）pi：第i個客戶；

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

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

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

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

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

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

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

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

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

（23）m：循環次數。

為建立本文數學模型，首先給出如下定義：

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

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

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

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

根據上述定義，建立本文數學模型如式（4）所示：

目標為最大化區域覆蓋率Rarea。

3 改進的虛擬力算法

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

3.1 配送中心移動方案

在整個服務范圍區域內隨機分配N個配送中心，用dj代表配送中心網絡中的第j個配送中心，則配送中心節點集合為D={d1,d2,…,dj,…,dN}。

改進的虛擬力算法是將配送網絡假設為一個包含力、加速度和質量的虛擬物理系統，配送中心、障礙物和服務區域均可以對配送中心產生引力或斥力，配送中心移動的方向和距離取決于該配送中心自身的位置，以及所受相鄰配送中心節點的引力與斥力的合力，配送中心節點需要移動到受力平衡的位置。

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

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

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

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

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

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

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

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

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

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

沿X軸的合力：

沿Y軸的合力：

受到的合力：

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

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

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

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

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

3.2 算法步驟

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

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

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

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

步驟5如果達到設置的算法循環次數則算法退出，否則轉向步驟1，進行新的循環過程。

4 仿真結果及分析

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

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

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

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

圖1 當N=5 時基于改進的虛擬力算法

圖2 當N=6 時基于改進的虛擬力算法

圖3 當N=7 時基于改進的虛擬力算法

圖4 當N=8 時基于改進的虛擬力算法

圖5 當N=10 時基于改進的虛擬力算法

圖6 當N=12 時基于改進的虛擬力算法

圖7 當N=14 時基于改進的虛擬力算法

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

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

圖8 當N=15 時基于改進的虛擬力算法

圖9 兩種算法結果的比較

5 總結

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

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