黃書強(qiáng),江秀美,范人勝

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

1 引 言

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

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

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

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

2 連續(xù)K中心選址問(wèn)題的模型

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

圖1 連續(xù)K中心選址問(wèn)題Fig.1 Continuous K-center location problem

如圖1所示,d1表示的是客戶點(diǎn)到部署服務(wù)站位置的最大歐式距離,d1+d2為最大加權(quán)距離.之前對(duì)于連續(xù)K中心問(wèn)題是以d1作為其優(yōu)化目標(biāo),也就是使得d1最小;本文考慮到實(shí)用性以及成本問(wèn)題,主要以 服務(wù)站到客戶點(diǎn)的最大加權(quán)距離作為優(yōu)化目標(biāo),也就是求解使得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)表明在網(wǎng)絡(luò)范圍內(nèi)一個(gè)節(jié)點(diǎn)受且僅受一個(gè)服務(wù)站管轄;式(2)表示不是服務(wù)站的節(jié)點(diǎn)間關(guān)系是平等的,即節(jié)點(diǎn)i不會(huì)接受非服務(wù)站節(jié)點(diǎn)j的管制;式(3)表明總的有k個(gè)服務(wù)站,式(4)表明xij,yj都為二進(jìn)制變量.

3 K中心選址問(wèn)題的分類

離散K中心選址問(wèn)題是指在給定的網(wǎng)絡(luò)節(jié)點(diǎn)上選取K個(gè)服務(wù)站的最優(yōu)位置,而連續(xù)K中心選址問(wèn)題則是在整個(gè)網(wǎng)絡(luò)平面上選取最優(yōu)的部署方案.連續(xù)K中心選址問(wèn)題相對(duì)于基于節(jié)點(diǎn)的K中心選址問(wèn)題對(duì)于服務(wù)站部署位置的選取對(duì)環(huán)境的適應(yīng)性更強(qiáng),并且選取位置更具有一般性,但是求解過(guò)程的復(fù)雜度也更大.

圖2 6個(gè)客戶節(jié)點(diǎn)服務(wù)站部署示意圖Fig.2 Customer nodes service station deployment diagram

圖2是以節(jié)點(diǎn)度為2的正六邊形構(gòu)成的6節(jié)點(diǎn)網(wǎng)絡(luò)圖,其構(gòu)成了一個(gè)連通的閉環(huán).六邊形的邊長(zhǎng)為2,以一個(gè)固定半徑的圓作為節(jié)點(diǎn)的最大覆蓋范圍.規(guī)定服務(wù)站到其他客戶節(jié)點(diǎn)的距離用無(wú)向邊上的權(quán)重表示.如圖2(b)所示,根據(jù)離散K中心的方法選取服務(wù)站時(shí),其覆蓋半徑為6;圖2(c)中選取幾何中心的位置設(shè)置服務(wù)站,將覆蓋半徑減少到2.

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

圖3 9個(gè)客戶節(jié)點(diǎn)網(wǎng)絡(luò)服務(wù)站部署示意圖Fig.3 Schematic diagram of 9 customer nodes network service station deployment

由以上對(duì)比可知,連續(xù)K中心選址問(wèn)題更具有普遍性.相對(duì)于離散K中心選址問(wèn)題受到網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)制約較大,連續(xù)K中心選址問(wèn)題具有更高的靈活性.為了使得最大加權(quán)距離最小、增加網(wǎng)絡(luò)拓?fù)涞倪B通性,可以在網(wǎng)絡(luò)平面適當(dāng)?shù)奶砑臃?wù)站節(jié)點(diǎn),從而使整個(gè)網(wǎng)絡(luò)的覆蓋半徑減小.近年來(lái),智能算法已成為解決組合優(yōu)化問(wèn)題的重要方法,與其它智能算法相比,PSO算法具有方便實(shí)現(xiàn)、不易陷入局部最優(yōu)等特點(diǎn),再加上其具有連續(xù)搜索的特性,因此PSO算法比較適合求解連續(xù)K中心選址問(wèn)題.

4 加權(quán)距離連續(xù)K中心問(wèn)題的SA-PSO算法

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

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

(5)

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

(6)

(7)

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

Step 1.構(gòu)建節(jié)點(diǎn)的網(wǎng)絡(luò)圖,隨機(jī)產(chǎn)生粒子數(shù)目為PopSize的種群,設(shè)置c1和c2的值,確定w和T的計(jì)算方式.

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

Step 3.根據(jù)設(shè)定的參數(shù)計(jì)算每個(gè)粒子的適應(yīng)值F(xi).

Step 4.每次迭代過(guò)后,更新粒子和種群的最優(yōu)位置pbest以及gbest.

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

Step 7.當(dāng)粒子的適應(yīng)值收斂或者達(dá)到了最大迭代次數(shù)時(shí),算法結(jié)束運(yùn)行;否則返回Step 3.

SA-PSO算法求解連續(xù)K中心選址問(wèn)題的描述為:

算法1.求解連續(xù)K中心選址問(wèn)題的SA-PSO算法輸入:節(jié)點(diǎn)網(wǎng)絡(luò)G,服務(wù)站數(shù)目k輸出:服務(wù)站的部署位置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 仿真分析

本節(jié)的實(shí)驗(yàn)環(huán)境是:Matlab2012a,內(nèi)存4GB,CPU主頻為3.4GHz的雙核計(jì)算機(jī).實(shí)驗(yàn)分別采用50、100、300和500節(jié)點(diǎn)的網(wǎng)絡(luò)規(guī)模仿真連續(xù)K中心選址問(wèn)題,網(wǎng)絡(luò)為節(jié)點(diǎn)度屬于集合[1,11]的隨機(jī)網(wǎng)絡(luò).實(shí)驗(yàn)以最小覆蓋半徑作為優(yōu)化目標(biāo),將SA-PSO算法與K-means算法和GA算法進(jìn)行實(shí)驗(yàn)對(duì)比.

圖4 4種規(guī)模的網(wǎng)絡(luò)拓?fù)鋱DFig.4 Different scale network topology diagrams

5.1 算法實(shí)驗(yàn)結(jié)果分析

表1為在固定服務(wù)站數(shù)目為5的情況下SA-PSO算法、GA算法、K-means算法3種算法在50、100、300、500節(jié)點(diǎn)網(wǎng)絡(luò)規(guī)模中的優(yōu)化結(jié)果.表1為20次獨(dú)立試驗(yàn)結(jié)果.

觀察表1可知,對(duì)網(wǎng)絡(luò)的覆蓋半徑而言,SA-PSO算法在不同網(wǎng)絡(luò)規(guī)模情況下的整體優(yōu)化效果要優(yōu)于其他兩種算法.K-means算法一般將服務(wù)站的位置設(shè)置在R2-V(G)中,但由于其網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的關(guān)聯(lián)較低,容易陷入局部最優(yōu),這會(huì)導(dǎo)致服務(wù)站的選取位置較差,因此K-means算法的優(yōu)化效果整體上比SA-PSO算法和GA算法要略為遜色.SA-PSO算法有較小的標(biāo)準(zhǔn)差,其穩(wěn)定性強(qiáng)于其他算法.由于SA-PSO算法在粒子群優(yōu)化算法中引入了模擬退火機(jī)制,這使得算法能夠更加快速的收斂于全局最優(yōu)解,提高全局搜索精度,穩(wěn)定性也有所增強(qiáng).

表1 3種算法在4種不同規(guī)模網(wǎng)絡(luò)的優(yōu)化結(jié)果
Table 1 Optimization results of four algorithms on networks
of different sizes

網(wǎng)絡(luò)規(guī)模 算 法最優(yōu)值最劣值平均值標(biāo)準(zhǔn)差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 算法收斂過(guò)程及時(shí)間復(fù)雜度分析

圖5表示的是不同網(wǎng)絡(luò)規(guī)模下SA-PSO算法、GA算法和K-means算法的迭代收斂過(guò)程,圖A-D的分別為50,100,300,500節(jié)點(diǎn)的網(wǎng)絡(luò)規(guī)模.

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

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

5.3 服務(wù)站部署效果分析

如果固定服務(wù)站的數(shù)目,其部署效果并不會(huì)隨網(wǎng)絡(luò)規(guī)模的增加而產(chǎn)生特別明顯的效果.因此,如圖6所示,實(shí)驗(yàn)以3種算法在服務(wù)站固定為5的50節(jié)點(diǎn)和100節(jié)點(diǎn)的兩種隨機(jī)網(wǎng)絡(luò)規(guī)模進(jìn)行效果對(duì)比.

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

圖5 3種算法的收斂過(guò)程對(duì)比Fig.5 Comparison of the convergence process of the three algorithms

6 結(jié) 論

本文研究的是連續(xù)K中心選址問(wèn)題,降低客戶節(jié)點(diǎn)到服務(wù)站節(jié)點(diǎn)之間的加權(quán)距離.本文以最小加權(quán)距離作為優(yōu)化目標(biāo),通過(guò)將模擬退火機(jī)制引入PSO算法并且加入慣性權(quán)重等改進(jìn)策略,本文提出改進(jìn)的粒子群優(yōu)化算法(SA-PSO).通過(guò)

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

對(duì)比其他算法,SA-PSO算法可以較快的收斂于全局最優(yōu)解.本文的研究對(duì)設(shè)施連續(xù)K中心選址問(wèn)題具有重要的應(yīng)用價(jià)值,也為選址問(wèn)題提供了一種新穎的思路和解法.