粒子群優(yōu)化算法車輛路徑問(wèn)題

1、粒子群優(yōu)化算法計(jì)算車輛路徑問(wèn)題摘要粒子群優(yōu)化算法中，粒子群由多個(gè)粒子組成，每個(gè)粒子的位置代表優(yōu)化問(wèn)題在Dffi搜索空間中潛在的解。根據(jù)各自的位置，每個(gè)粒子用一個(gè)速度來(lái)決定其飛行的方向和距離,然后通過(guò)優(yōu)化函數(shù)計(jì)算出一個(gè)適應(yīng)度函數(shù)值(fitness)。粒子是根據(jù)如下三條原則來(lái)更新自身的狀態(tài)：(1)在飛行過(guò)程中始終保持自身的慣性;(2)按自身的最優(yōu)位置來(lái)改變狀態(tài);(3)按群體的最優(yōu)位置來(lái)改變狀態(tài)。本文主要運(yùn)用運(yùn)籌學(xué)中粒子群優(yōu)化算法解決車輛路徑問(wèn)題。車輛路徑問(wèn)題由Dantzig和Ramser于1959年首次提出的，它是指對(duì)一系列發(fā)貨點(diǎn)(或收貨點(diǎn))，組成適當(dāng)?shù)男熊嚶窂?，使車輛有序地通過(guò)它們，在滿足一定約

2、束條件的情況下，達(dá)到一定的目標(biāo)(諸如路程最短、費(fèi)用最小，耗費(fèi)時(shí)間盡量少等)，屬于完全NP問(wèn)題，在運(yùn)籌、計(jì)算機(jī)、物流、管理等學(xué)科均有重要意義。粒子群算法是最近出現(xiàn)的一種模擬鳥群飛行的仿生算法，有著個(gè)體數(shù)目少、計(jì)算簡(jiǎn)單、魯棒性好等優(yōu)點(diǎn)，在各類多維連續(xù)空間優(yōu)化問(wèn)題上均取得非常好的效果。本文將PSO應(yīng)用于車輛路徑問(wèn)題求解中，取得了很好的效果。針對(duì)本題，一個(gè)中心倉(cāng)庫(kù)、7個(gè)需求點(diǎn)、中心有3輛車，容量均為1,由這三輛車向7個(gè)需求點(diǎn)配送貨物，出發(fā)點(diǎn)和收車點(diǎn)都是中心倉(cāng)庫(kù)。k=3,q=q?=q3=1,l=7.貨物需求重g1=0.89,g2=0.14g=0.28必=0.33。=0.21。=0.41,g7=0.57,

3、且mgia珠。利用matlab編程，求出需求點(diǎn)和中心倉(cāng)庫(kù)、需求點(diǎn)之間的各個(gè)距離，用Cj表小。求滿足需求的最小的車輛行駛路徑，就是求minZE二匚CjXij%經(jīng)過(guò)初始化粒子群，將初始的適應(yīng)值作為每個(gè)粒子的個(gè)ijk體最優(yōu)解，并尋找子群內(nèi)的最優(yōu)解以及全局的最優(yōu)解重復(fù)以上步驟，直到滿足終止條件。本題的最短路徑由計(jì)算可知為217.81關(guān)鍵字：粒子群算法、車輛路徑、速度一、問(wèn)題的重述一個(gè)中心倉(cāng)庫(kù)序號(hào)為0,7個(gè)需求點(diǎn)序號(hào)為17,其位置坐標(biāo)見表1,中心有3輛車，容量均為1,由這三輛車向7個(gè)需求點(diǎn)配送貨物，出發(fā)點(diǎn)和收車點(diǎn)都是中心倉(cāng)庫(kù)。求滿足需求的距離最小的車輛行駛路徑。表1倉(cāng)庫(kù)中心坐標(biāo)和需求點(diǎn)坐標(biāo)及需求量序號(hào)0

4、1234567坐標(biāo)(18,54)(22,60)(58,69)(71,71)(83,46)(91,38)(24,42)(18,40)需求量00.890.140.280.330.210.410.57問(wèn)題假設(shè)1 .現(xiàn)實(shí)生活中中心倉(cāng)庫(kù)以及各個(gè)需求點(diǎn)之間軍事直線連接，兩點(diǎn)之間距離即為坐標(biāo)系中兩點(diǎn)坐標(biāo)間距離。2 .不因天氣及失火等原因車輛停止運(yùn)輸。3 .每個(gè)需求點(diǎn)由一輛車供應(yīng)貨物。三、符號(hào)說(shuō)明k配送貨物車輛數(shù)l需求點(diǎn)個(gè)數(shù)gi貨物需求量qk配送貨物車輛的容量Cj從點(diǎn)i到j(luò)的距離yki需求點(diǎn)i由k車配送xijk車k從i行駛到j(luò)四、問(wèn)題分析4.1算法分析車輛路徑問(wèn)題(VRP可以描述為有一個(gè)中心倉(cāng)庫(kù)，擁有K輛車，

5、容量分別為qk(k=1,2,，K),負(fù)責(zé)向L個(gè)需求點(diǎn)配送貨物，貨物需求量為gi(i=1,2,，L),且maxgi<maxqk;cj表示從點(diǎn)i至ijj的距離。求滿足需求的距離最小的車輛行駛路徑。將中心倉(cāng)庫(kù)編號(hào)為0,需求點(diǎn)編號(hào)為1,2,L。數(shù)學(xué)模型為：minZ='"cijxijkijks.t."giyki也,-卜、yki=1,i=1,2,LkXijk=ykj,j=0,1,L;k'、,xjk=yki,i=0,1,L;kX=(Xijk)SXjk=0或1,i,j=0,1，L;Vkyki=0或1,i-0,1,L;-k其中,f-yki=0需求點(diǎn)i由k車配送否則,1車

6、k從i行駛駛j0否則k=3,q=q2=q3=1,l=7.貨物需求量g1=0.89,g2=0.14,g3=0.28,g4=0.33,gs=0.210=0.41,g?=0.57,利用粒子群優(yōu)化算法，經(jīng)過(guò)初始化粒子群，將初始的適應(yīng)值作為每個(gè)粒子的個(gè)體最優(yōu)解，并尋找子群內(nèi)的最優(yōu)解以及全局的最優(yōu)解。重復(fù)以上步驟，直到滿足終止條件。4.2舉例具體演算分析例如，設(shè)VRP問(wèn)題中發(fā)貨點(diǎn)任務(wù)數(shù)為7,車輛數(shù)為3,若某粒子的位置向量X為：發(fā)貨點(diǎn)任務(wù)號(hào)：1234567Xv:1222233Xr:1431221則該粒子對(duì)應(yīng)解路徑為：車1:01一0車2:0一4一5一3一2一0車3:0一7一6一0粒子速度向量V與之對(duì)應(yīng)表示為V

7、v和Vr該表示方法的最大優(yōu)點(diǎn)是使每個(gè)發(fā)貨點(diǎn)都得到車輛的配送服務(wù)，并限制每個(gè)發(fā)貨點(diǎn)的需求僅能由某一車輛來(lái)完成，使解的可行化過(guò)程計(jì)算大大減少Z®然該表示方法的維數(shù)較高，但由于PSO算法在多維尋優(yōu)問(wèn)題有著非常好的特性，維數(shù)的增加并未增加計(jì)算的復(fù)雜性，這一點(diǎn)在實(shí)驗(yàn)結(jié)果中可以看到五、模型的建立與求解在本題中，需要分別計(jì)算以下幾個(gè)內(nèi)容，計(jì)算需求點(diǎn)與中心倉(cāng)庫(kù)及各需求點(diǎn)間距離，利用粒子群優(yōu)化算法，求出函數(shù)的全局最優(yōu)位置和最后得到的優(yōu)化極值。5.1 需求點(diǎn)與中心倉(cāng)庫(kù)及各需求點(diǎn)間距離利用直角三角形勾股定理，求斜邊長(zhǎng)度。A(xi,y3B(x2,y2),直角坐標(biāo)系中求A,B兩點(diǎn)之間距離AB=,J(y2-y1

8、)2+(x2-x1)2距離01234567007.211142.7255.6665.4974.73313.4161417.2111037.10850.2262.58672.42218.11120.396242.7237.108013.15333.97145.27743.41749.406355.6650.2213.153027.73138.58855.22761.4465.4962.58633.97127.731011.31459.13565.276574.73372.42245.27738.58811.314067.11973.027613.41618.11143.41755.22759.1

9、3567.11906.324671420.39649.40661.465.27673.0276.324605.2粒子群優(yōu)化算法5.2.1算法實(shí)現(xiàn)過(guò)程步驟1初始化粒子群粒子群劃分成若干個(gè)兩兩相互重疊的相鄰子群； 每個(gè)粒子位置向量Xv的每一維隨機(jī)取1K(車輛數(shù))之間的整數(shù)，Xr的每一維隨機(jī)取1L(發(fā)貨點(diǎn)任務(wù)數(shù))之間的實(shí)數(shù)； 每個(gè)速度向量Vv的每一維隨機(jī)取-(K-1)(K-1)(車輛數(shù))之間的整數(shù)，Vr的每一維隨機(jī)取-(L-1)(L-1)之間的實(shí)數(shù)； 用評(píng)價(jià)函數(shù)Eval評(píng)價(jià)所有粒子； 將初始評(píng)價(jià)值作為個(gè)體歷史最優(yōu)解Pi,并尋找各子群內(nèi)的最優(yōu)解Pl和總?cè)后w內(nèi)最優(yōu)解pg步驟2重復(fù)執(zhí)行以下步驟，直到滿足終

10、止條件或達(dá)到最大迭代次數(shù)對(duì)每一個(gè)粒子,計(jì)算Vv、Vr；計(jì)算Xv、Xr,其中Xv向上取整；當(dāng)V、X超過(guò)其范圍時(shí)按邊界取值用評(píng)價(jià)函數(shù)Eval評(píng)價(jià)所有粒子；若某個(gè)粒子的當(dāng)前評(píng)價(jià)值優(yōu)于其歷史最優(yōu)評(píng)價(jià)值,則記當(dāng)前評(píng)價(jià)值為該歷史最優(yōu)評(píng)價(jià)值,同時(shí)將當(dāng)前位置向量記為該粒子歷史最優(yōu)位置Pi;尋找當(dāng)前各相鄰子群內(nèi)最優(yōu)和總?cè)后w內(nèi)最優(yōu)解，若優(yōu)于歷史最優(yōu)解則更新Pl、Pg5.2.2針對(duì)本題0表示中心倉(cāng)庫(kù)，設(shè)車輛容量皆為q=1.0,由3輛車完成所有任務(wù)，初始化群體個(gè)數(shù)n=40;慣性權(quán)重w=0.729;學(xué)習(xí)因子c1=c2=1.49445;最大代數(shù)MaxDT=50;搜索空間維數(shù)（未知數(shù)個(gè)數(shù)）D=7;算法得到的最優(yōu)值的代數(shù)及所

11、得到的最優(yōu)解，預(yù)計(jì)迭代次數(shù)50,共進(jìn)行20次運(yùn)算運(yùn)算次數(shù)12345678910總距離217.81230.41217.81217.813；03.04217.81303.04217.81217.81230.41運(yùn)算次數(shù)11121314151617181920總距離217.81217.81230.41217.812>17.81217.81217.81217.81217.81217.81從實(shí)驗(yàn)結(jié)果分析，15次達(dá)到已知最優(yōu)解，得到的最優(yōu)總路徑為:0>7>6>0>1>0>2>3>4>5>0對(duì)應(yīng)的行車路線為：車輛一：0>7>6，0

12、車輛二：01>0車輛三:0>2>3>4>5>0行車總距離217.81粒子群優(yōu)化算法達(dá)到最優(yōu)路徑50次的代數(shù)723217717137411928113314212311718224135836201038565359215762567305592921638943148129379六、模型的評(píng)價(jià)粒子群優(yōu)化算法結(jié)果分析方法達(dá)到最優(yōu)路徑次數(shù)未達(dá)最優(yōu)路徑次數(shù)達(dá)到最優(yōu)路徑平均代數(shù)達(dá)到最優(yōu)路徑平均時(shí)間(S)粒子群50028.363.04分析PSO方法，可以看出它與GA等其他演化算法的最大不同在于1)迭代運(yùn)算中只涉及到初等運(yùn)算，且運(yùn)算量非常少；2)每個(gè)粒子能直接獲取群體歷

13、史經(jīng)驗(yàn)和個(gè)體歷史經(jīng)驗(yàn)，比在其他方法中使用精英集(elitism)的方法更有效；3)整個(gè)粒子群被劃分為幾個(gè)的子群，且子群之間有一定重疊，從而使收斂于局部最優(yōu)解的幾率大大減少L正因?yàn)槿绱?，本文將PSO應(yīng)用于帶時(shí)間窗車輛路徑問(wèn)題求解中，取得了很好的效果，有著運(yùn)算速度快、解的質(zhì)量與個(gè)體數(shù)目相關(guān)性小、所獲得的解質(zhì)量高等諸多優(yōu)點(diǎn)七、模型的改進(jìn)和推廣7.1模型的改進(jìn)針對(duì)粒子群優(yōu)化算法存在的問(wèn)題，提出了一種新的改進(jìn)算法一基于粒子進(jìn)化的多粒子群優(yōu)化算法。該算法采用局部版的粒子群優(yōu)化方法，從“粒子進(jìn)化”和“多種群”兩個(gè)方面對(duì)標(biāo)準(zhǔn)粒子群算法進(jìn)行改進(jìn)。多個(gè)粒子群彼此獨(dú)立地搜索解空間，保持了粒子種群的多樣性，從而增強(qiáng)了

14、全局搜索能力而適當(dāng)?shù)摹傲Ｗ舆M(jìn)化”可以使陷入局部最優(yōu)的粒子迅速跳出，有效的避免了算法“早熟”，提高了算法的穩(wěn)定性。將基于粒子進(jìn)化的多粒子群優(yōu)化算法用于求解非線性方程組。該算法求解精度高、收斂速度快，而且克服了一些算法對(duì)初值的敏感和需要函數(shù)可導(dǎo)的困難，能較快地求出復(fù)雜非線性方程組的最優(yōu)解。數(shù)值仿真結(jié)果顯示了該算法的有效性和可行性，為求解非線性方程組提供了一種實(shí)用的方法。7.2模型的推廣作為物流系統(tǒng)優(yōu)化中的重要一環(huán)，合理安排車輛路徑、進(jìn)行物流車輛優(yōu)化調(diào)度可以提高物流經(jīng)濟(jì)效益、實(shí)現(xiàn)物流科學(xué)化。粒子群算法在多維尋優(yōu)中有著非常好的特性，加入“鄰居算子”的粒子群算法能使算法更好的全局尋優(yōu)。本文的研究表明，改

15、進(jìn)局部辦粒子群算法，能過(guò)有效地解決車輛路徑問(wèn)題。八、參考文獻(xiàn)1李軍，郭耀煌.物流配送車輛優(yōu)化調(diào)度理論與方法M.北京：中國(guó)物資出版社,2001.2馬炫，彭蒞，劉慶.求解帶時(shí)間窗車輛路徑問(wèn)題的改進(jìn)粒子群算法.計(jì)算機(jī)工程與應(yīng)用，2009,45(27):200-2023姜啟源，數(shù)學(xué)建模，高教出版社，2000年附錄需求點(diǎn)與中心倉(cāng)庫(kù)及各需求點(diǎn)間距離c=；zuobiao=18542260586971718346913824421840;fori=1:8forj=1:8c(i,j)=sqrt(zuobiao(j,2)-zuobiao(i,2)A2+(zuobiao(j,1)-zuobiao(i,1)A2);e

16、ndendc粒子群優(yōu)化算法求解主算法clearall;cic;formatlong;%-給定初始化條件c1=1.4962;%學(xué)習(xí)因子1c2=1.4962;%學(xué)習(xí)因子2w=0.7298;%慣性權(quán)重MaxDT=50;%最大迭代次數(shù)D=7;%搜索空間維數(shù)(未知數(shù)個(gè)數(shù))N=40;%初始化群體個(gè)體數(shù)目%-初始化種群的個(gè)體(可以在這里限定位置和速度的范圍)fori=1:Nforj=1:D是向離它最近的大整數(shù)圓整x1(i,j)=ceil(3*rand();%隨機(jī)初始化位置ceilx2(i,j)=ceil(7*rand();v1(i,j)=2*(2*rand()-1);%隨機(jī)初始化速度%v2(i,j)=6*(

17、2*rand()-1);endend%-先計(jì)算各個(gè)粒子的適應(yīng)度，并初始化Pbest和gbestfori=1:Ny1(i,:)=x1(i,:);y2(i,:)=x2(i,:);pbest(i)=fitness(y1(i,:),y2(i,:),D);endpg1=x1(1,:);%Pg為全局最優(yōu)pg2=x2(1,:);fori=2:Niffitness(x1(i,:),x2(i,:),D)<fitness(pg1,pg2,D)pg1=x1(i,:);pg2=x2(i,:);gbest=fitness(pg1,pg2,D);endend%-進(jìn)入主要循環(huán)，按照公式依次迭代，直到滿足精度要求for

18、t=1:MaxDTfori=1:Nv1(i,:)=w*v1(i,:)+c1*rand*(y1(i,:)-x1(i,:)+c2*rand*(pg1-x1(i,:);x1(i,:)=x1(i,:)+v1(i,:);x1(i,:)=ceil(x1(i,:);forj=1:Difx1(i,j)<1x1(i,j)=1;endifx1(i,j)>3x1(i,j)=3;endendforj=1:Dx2(i,j)=ceil(7*rand();endiffitness(x1(i,:),x2(i,:),D)<pbest(i)y1(i,:)=x1(i,:);y2(i,:)=x2(i,:);pbest(i)=fitness(y1(i,:),y2(i,:),D);endifpbest(i)<fitness(pg1,pg2,D)pg1=x1(i,:);pg2=