一種加權距離連續K中心選址問題求解方法

黃書強,江秀美,范人勝

1(暨南大學 理工學院光電工程系,廣州 510632)2(廣東省農村信用社聯合社,廣州 510000)

1 引 言

選址問題是運籌學中經典的一種決策問題,有著非常廣泛的應用,主要研究如何選擇設施的數目和確定最優位置從而為用戶提供相應的服務,有著巨大的經濟和社會意義.自1964年Hakimi提出了K中心選址問題[1]之后,許多學者加入到研究這個問題的隊伍中,紛紛提出自己的解決辦法并且有了較大的進展.K中心選址問題是指在網絡平面上選定K個建立服務站的最優位置,也就是在全局范圍內尋找使得所有需求點到最近服務站的最大距離值最小的部署方案.K中心選址問題是研究其他選址問題的基礎,在工廠、倉庫、加油站、物流中心等的部署中都有應用.將中心選址問題以選取服務站方式進行分類可分為:離散和連續兩種中心選址問題.離散K中心選址問題是指在給定的網絡節點上選取K個最優位置建立服務站,而連續K中心選址問題則是在整個網絡平面上選取最優的部署方案.連續K中心選址問題相對于基于節點的離散K中心選址問題,其服務站部署位置的選取對于環境的適應性更強,并且選取位置更具有一般性,但是求解過程的復雜度也更大[2].

對于K中心選址問題,目前大多數研究都是以離散中心選址為主,對于離散K中心選址問題的研究相對比較成熟.文獻[3]提出先求得最大距離,之后再求最大覆蓋問題,得到離散K中心選址問題最優解的方法.Mladenovi等人[4]提出基于可變鄰域搜索和兩種禁忌搜索啟發式算法來求解無三角不等式的離散K中心選址問題.文獻[5]提出一個新的整數線性規劃公式獲得邊界值,從而獲得更優解.Ilhan[6]提出算法迭代方式分配所有客戶端的最大距離值,從而解決整數可行性的問題.文獻[7]在文獻[6]的基礎上進行改進并獲得了更優解.文獻[8]基于最小頂點覆蓋，通過改進貪心算法得到選址問題的最優解.

對于連續K中心選址問題的研究,國外的研究較為豐富.Chen[9]提出了一種求解歐氏距離的minimax和minisum位置分配問題的新方法.該方法基于為目標函數提供可微分近似,對于大規模網絡有較好的效果但是不適用于小規模網絡.文獻[10]提出了Slab劃分方法有效的求解歐幾里得K中心問題.Suzuki等人[11]提出了Voronoi圖啟發式方法,給出了方形最優解的上界,得到方形區域特殊情況的計算結果.Handler 等人[12]用松弛算法解決連續中心選址問題.本質上是選擇要服務的n個點的子集.利用集合覆蓋算法獲取K個可將網絡節點覆蓋的覆蓋圓,調整最大圓的半徑得到最優解.文獻[13]在文獻[11]的基礎上減少松弛算法迭代次數以及子問題的數目,使得算法具有更好的性能.文獻[14]以需求最大化為目標，設計基于矩陣編碼與小生境技術的非支配排序多目標遺傳算法對定位-分配問題進行求解.文獻[15,16]分別利用自適應學習能力啟發式算法和近似魯棒優化啟發式算法,來解決連續空間最大歐式距離P中心問題.上述文獻中都是以服務站到最遠客戶節點的歐式距離作為優化目標來對連續K中心問題進行研究,本文主要研究服務站到客戶點的最大加權距離最小.

智能算法已成為解決組合優化問題的重要方法,如粒子群優化算法和差分進化算法作為經典的群智能隨機優化算法,非常適合求解連續K中心選址問題.文獻[17-19]分別利用改進的粒子群算法、遺傳算法和差分進化算法求解跳數距離的幾何K中心選址問題,取得較好效果.受上述方法思想啟發,針對加權歐式距離的K中心連續選址問題,本文提出改進的模擬退火粒子群優化算法(SA-PSO)進行解決.

2 連續K中心選址問題的模型

本文采用了幾何的方式,將連續中心選址問題轉化為圖論問題來進行研究.上文中提到連續K中心問題可在除節點外的整個網絡平面內選擇合適位置建造服務站.給定網絡圖G(V,E).其中V={v1,v2,…,vn},表示的是n個網絡節點的集合,E表示網絡中所有節點邊的集合.如圖1(a)所示,給定固定半徑r,如果兩個節點之間的距離d小于半徑r,則稱這兩個節點為鄰接節點,且這兩節點之間有邊相連.

圖1 連續K中心選址問題Fig.1 Continuous K-center location problem

如圖1所示,d1表示的是客戶點到部署服務站位置的最大歐式距離,d1+d2為最大加權距離.之前對于連續K中心問題是以d1作為其優化目標,也就是使得d1最小;本文考慮到實用性以及成本問題,主要以 服務站到客戶點的最大加權距離作為優化目標,也就是求解使得d1+d2最小.

s.t.|U|=k

(1)

xij≤yj,1≤i≤n,1≤j≤n

(2)

(3)

xij,yj∈{0,1}, 1≤i≤n, 1≤j≤n

(4)

式(1)表明在網絡范圍內一個節點受且僅受一個服務站管轄;式(2)表示不是服務站的節點間關系是平等的,即節點i不會接受非服務站節點j的管制;式(3)表明總的有k個服務站,式(4)表明xij,yj都為二進制變量.

3 K中心選址問題的分類

離散K中心選址問題是指在給定的網絡節點上選取K個服務站的最優位置,而連續K中心選址問題則是在整個網絡平面上選取最優的部署方案.連續K中心選址問題相對于基于節點的K中心選址問題對于服務站部署位置的選取對環境的適應性更強,并且選取位置更具有一般性,但是求解過程的復雜度也更大.

圖2 6個客戶節點服務站部署示意圖Fig.2 Customer nodes service station deployment diagram

圖2是以節點度為2的正六邊形構成的6節點網絡圖,其構成了一個連通的閉環.六邊形的邊長為2,以一個固定半徑的圓作為節點的最大覆蓋范圍.規定服務站到其他客戶節點的距離用無向邊上的權重表示.如圖2(b)所示,根據離散K中心的方法選取服務站時,其覆蓋半徑為6;圖2(c)中選取幾何中心的位置設置服務站,將覆蓋半徑減少到2.

圖3是由最鄰近邊距離為2的9個節點構成的網絡圖.服務站數目固定為2.以兩種方式選取位置設置服務站,一是如圖3(b)所示的服務站在已有的網絡節點上選取,可得網絡的覆蓋半徑為4;二是如圖3(c)所示在網絡平面的任意位置建立服務站,添加之前沒有的10號節點,以2號與10號節點的位置建立服務站,網絡的覆蓋半徑可降到2.

圖3 9個客戶節點網絡服務站部署示意圖Fig.3 Schematic diagram of 9 customer nodes network service station deployment

由以上對比可知,連續K中心選址問題更具有普遍性.相對于離散K中心選址問題受到網絡拓撲結構制約較大,連續K中心選址問題具有更高的靈活性.為了使得最大加權距離最小、增加網絡拓撲的連通性,可以在網絡平面適當的添加服務站節點,從而使整個網絡的覆蓋半徑減小.近年來,智能算法已成為解決組合優化問題的重要方法,與其它智能算法相比,PSO算法具有方便實現、不易陷入局部最優等特點,再加上其具有連續搜索的特性,因此PSO算法比較適合求解連續K中心選址問題.

4 加權距離連續K中心問題的SA-PSO算法

粒子群優化算法(PSO)是一種模擬鳥群的覓食過程的進化算法.該算法在連續高維空間搜索極值,快速計算得到最優解,具有方便實現、易編程、設置參數少的優點,適用于大規模的并行計算.由于網絡拓撲結構不確定,與進化演化類算法、貪心算法以及其它一些微粒群算法相比,粒子群算法能夠根據目標特點,不斷調整迭代來適應目標特性,找到全局最優解,從而具有空間局域探索和廣域開發均衡的能力.但是傳統粒子群算法在求解過程中,收斂速度較慢,搜索結果的魯棒性也比較差.為了提升算法性能,將模擬退火算法引入到PSO中.模擬退火算法(SA)模擬固體退火降溫過程,是一種在大型離散搜索空間中尋找最優的元啟發式算法.該算法采用Metropolis重要性采樣準則,在搜素過程中接收好的解的同時也接收一定概率的差的解,因此在求解過程中能有效避免陷入局部最優.將模擬退火思想引入粒子群算法,主要是將模擬退火的過程引入到粒子群算法迭代過程中,而PSO算法只產生和更新粒子.這樣不僅使得算法的全局搜索能力有所提高,還能保證粒子群的收斂性.基于此,本文提出基于模擬退火的粒子群優化算法(PSO with Simulated Annealing,SA-PSO).

SA-PSO算法中每一個粒子表示的是選址問題中的一組可能解,也就是在R2上編碼方式為k個服務站的坐標位置的組合.例如,xi=(xi,1,xi,2,…,xi,2k) 表示第i個粒子的位置,其中xi,2t-1和xi,2t(t=1,…,k)分別代表在平面R2上第t個服務站中的橫縱坐標.使用公式(5)來計算粒子i的適應值,適應值越大,選址位置越差;反之,選址的位置越好.

(5)

在SA-PSO算法的迭代過程中,粒子通過與其他粒子相互作用,根據適應度函數不斷調整飛行速度(速率和方向)以及對整個群體的狀態信息進行更新,得到全局最優解.公式(6)展示了粒子調整飛行速度和更新位置的方法.其中:w為慣性權重,c1和c2分別為自我學習因子和社會學習因子,都是非負數.vi=(si,1,si,2,…,si,2k)為第i個粒子的飛行速度,pi=(pi,1,pi,2,…,pi,2k)為第i個粒子搜索到的最優位置,pg=(pg1,pg2,…,pg2k)為粒子群搜索到的最優位置.在迭代過程中,xnew將以某一概率取代原來的最優位置x,這一概率采用溫度T來控制.溫度T的變化Tt=α·Tt-1,會隨著算法的執行緩慢下降.其中α∈(0.95,0.99),Tt為粒子群第t次迭代的次數,r為退火常數.公式(7)為概率p的計算公式,其中:ΔE=F(xnew)-F(x).

(6)

(7)

上文提到PSO算法是模擬鳥類覓食等群體行為,那么SA-PSO算法則是一群具有更高“智商”的“鳥”,它是以某種概率“試探”后再決定其覓食方向,而不是盲目地直接撲向下一個位置.因此,當溫度下降足夠慢時,粒子不會輕易跳出有可能的搜索區域,使得粒子的局部搜索能力增強.根據上述思想,可采用SA-PSO算法解決連續型的K中心選址問題,其步驟描述如下:

Step 1.構建節點的網絡圖,隨機產生粒子數目為PopSize的種群,設置c1和c2的值,確定w和T的計算方式.

Step 2.在搜索范圍內初始化粒子的位置x和速度vi.

Step 3.根據設定的參數計算每個粒子的適應值F(xi).

Step 4.每次迭代過后,更新粒子和種群的最優位置pbest以及gbest.

Step 5.由公式(6)對位置x和速度vi進行更新.

Step 7.當粒子的適應值收斂或者達到了最大迭代次數時,算法結束運行;否則返回Step 3.

SA-PSO算法求解連續K中心選址問題的描述為:

算法1.求解連續K中心選址問題的SA-PSO算法輸入:節點網絡G,服務站數目k輸出:服務站的部署位置1. Initialize Population,T0,α,Maxgen,r,pbest=x,and so on 2. form=0 to Maxgen-1 3. Tm+1=α×Tm; 4. gbest=min(pbest);5. for i=1 to PopSize6. if f(xi)Vmax12. Vij=Vmax13. else if |Vij|rand then 19. xi=xnew;20. end if21. end for22. end for

5 仿真分析

本節的實驗環境是:Matlab2012a,內存4GB,CPU主頻為3.4GHz的雙核計算機.實驗分別采用50、100、300和500節點的網絡規模仿真連續K中心選址問題,網絡為節點度屬于集合[1,11]的隨機網絡.實驗以最小覆蓋半徑作為優化目標,將SA-PSO算法與K-means算法和GA算法進行實驗對比.

圖4 4種規模的網絡拓撲圖Fig.4 Different scale network topology diagrams

5.1 算法實驗結果分析

表1為在固定服務站數目為5的情況下SA-PSO算法、GA算法、K-means算法3種算法在50、100、300、500節點網絡規模中的優化結果.表1為20次獨立試驗結果.

觀察表1可知,對網絡的覆蓋半徑而言,SA-PSO算法在不同網絡規模情況下的整體優化效果要優于其他兩種算法.K-means算法一般將服務站的位置設置在R2-V(G)中,但由于其網絡拓撲結構的關聯較低,容易陷入局部最優,這會導致服務站的選取位置較差,因此K-means算法的優化效果整體上比SA-PSO算法和GA算法要略為遜色.SA-PSO算法有較小的標準差,其穩定性強于其他算法.由于SA-PSO算法在粒子群優化算法中引入了模擬退火機制,這使得算法能夠更加快速的收斂于全局最優解,提高全局搜索精度,穩定性也有所增強.

表1 3種算法在4種不同規模網絡的優化結果
Table 1 Optimization results of four algorithms on networks
of different sizes

網絡規模 算 法最優值最劣值平均值標準差50SA-PSOGAKmeans19.362925.358622.947523.856930.356832.352321.617527.485626.60561.46141.58341.8801100SA-PSOGAKmeans28.456133.902931.313232.860739.597547.371831.582936.472638.21571.35621.89263.7078300SA-PSOGAKmeans57.024959.027462.240663.617266.601281.535058.155162.731669.57811.54921.90084.4747500SA-PSOGAKmeans73.891879.131080.194678.814786.446089.965776.043681.205184.39771.44882.02613.6975

5.2 算法收斂過程及時間復雜度分析

圖5表示的是不同網絡規模下SA-PSO算法、GA算法和K-means算法的迭代收斂過程,圖A-D的分別為50,100,300,500節點的網絡規模.

觀察圖5可知,在4種網絡規模中,3種算法收斂過程較為明顯;K-means算法得初始值大于SA-PSO算法和GA算法;而SA-PSO算法與另外兩種算法的收斂值有較大差異.初始值大其效果較差,因此K-means算法的整體效果要劣于GA算法與SA-PSO算法.K-means算法初始值大的原因主要是由于其初始位置是在稀疏的隨機網絡平面R2內生成,這使得客戶節點與服務站的連接度低.從收斂過程可以看出,GA算法收斂最慢;SA-PSO算法收斂速度較快,K-means算法收斂速度最快,但是容易陷入局部最優.但是SA-PSO算法具有空間局域探索和廣域開發均衡能力,可以較快的收斂于全局最優解.

從算法理論分析,K-means算法的時間復雜度為O(n.k.t),遺傳算法GA的時間復雜度為O((n-k)2kt.NP),SA-PSO的算法時間復雜度為O(n.k.t.IP).其中,n表示網絡節點數,k表示部署的網關數目,t為算法的迭代次數,NP為遺傳算法的種群規模,IP為粒子群算法初始化種群數量.

5.3 服務站部署效果分析

如果固定服務站的數目,其部署效果并不會隨網絡規模的增加而產生特別明顯的效果.因此,如圖6所示,實驗以3種算法在服務站固定為5的50節點和100節點的兩種隨機網絡規模進行效果對比.

由圖6觀察各算法的網關位置可知,SA-PSO算法與K-means算法在網絡平面R2中設置服務站,而GA算法則直接在客戶節點中設置網關.SA-PSO算法選取幾個非鄰接節點的幾何中心位置設置服務站,其節點度較大,并且客戶節點之間的距離也能夠有效的減少.所以相對于K-means算法,SA-PSO算法設置的網關位置更為合理,簇的規模差異大會使得網絡拓撲結合零散化,對于減小網絡覆蓋半徑不利.由圖6觀察3種算法的簇可知,GA算法和K-means算法的簇規模相差較大,而SA-PSO算法中的簇簇規模幾乎相等.因此SA-PSO算法不僅使得網絡覆蓋半徑最小還能兼顧各個網關,讓其負載均衡,提高服務站的效率.在相同服務站數目情況下,SA-PSO算法求解的網絡覆蓋半徑均比GA算法和K-means算法都要小.因此具有較小的初始值以及穩定性較強的SA-PSO算法更適合用于求解連續K中心選址問題.

圖5 3種算法的收斂過程對比Fig.5 Comparison of the convergence process of the three algorithms

6 結 論

本文研究的是連續K中心選址問題,降低客戶節點到服務站節點之間的加權距離.本文以最小加權距離作為優化目標,通過將模擬退火機制引入PSO算法并且加入慣性權重等改進策略,本文提出改進的粒子群優化算法(SA-PSO).通過

圖6 3種算法的服務站部署效果Fig.6 Service station deployment effect of three algorithms

對比其他算法,SA-PSO算法可以較快的收斂于全局最優解.本文的研究對設施連續K中心選址問題具有重要的應用價值,也為選址問題提供了一種新穎的思路和解法.