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

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

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

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

4、是 中心倉庫。求滿足需求的距離最小的車輛行駛路徑。問題假設(shè)表1倉庫中心坐標(biāo)和需求點(diǎn)坐標(biāo)及需求量序號01234567坐標(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.571 現(xiàn)實(shí)生活中中心倉庫以及各個(gè)需求點(diǎn)之間軍事直線連接，兩點(diǎn)之間距離即為 坐標(biāo)系中兩點(diǎn)坐標(biāo)間距離。2 不因天氣及失火等原因車輛停止運(yùn)輸。3 每個(gè)需求點(diǎn)由一輛車供應(yīng)貨物。三、符號說明k配送貨物車輛數(shù)l需求點(diǎn)個(gè)數(shù)g貨物需求量qk配送貨物車輛的容量q從點(diǎn)i到j(luò)的距離yki需求點(diǎn)i由k車配送Xijk車k

5、從i行駛到j(luò)四、問題分析4.1算法分析車輛路徑問題(VRP可以描述為有一個(gè)中心倉庫，擁有K輛車，容量分別為q'k =1,2,，K)，負(fù)責(zé)向L個(gè)需求點(diǎn)配送貨物，貨物需求量為gi (i =1,2,，L)，且maxgi - maxqk ； cj表示從點(diǎn)i至U j的距離。求滿足需求的 距離最小的車輛行駛路徑。將中心倉庫編號為0，需求點(diǎn)編號為1，2，L。數(shù)學(xué)模型為：min Z =、 CjXjki j ks.t.giYki Xk,ki- yki 1, i 1,2, Lk' Xjk 二丫“ j =0,1,丄；“i' Xjk =yki,i =0,1,丄；kX 二（Xjk） SXjk =

6、0或 1,i, j =0,1,丄;-k yki =0 或 1,i =0,1,丄;-k其中,需求點(diǎn)i由k車配送1 車k從i行駛駛j否則，Xijk »0 否則k = 3,qi = q2 = q3 = 1,1 = 7.貨 物 需 求 量。"朋禺“鳥=0.289 = 0.33,g 0.21,g 0.41,g 0.57，利用粒子群優(yōu)化算法，經(jīng)過初始化粒子群，將初始的適應(yīng)值作為每個(gè)粒子的個(gè)體最優(yōu)解，并尋找子群內(nèi)的最優(yōu)解以及全局的最優(yōu)解。重復(fù)以上步驟，直到滿足終止條件。4.2舉例具體演算分析例如，設(shè)VRP問題中發(fā)貨點(diǎn)任務(wù)數(shù)為7,車輛數(shù)為3,若某粒子的位置向量X 為：發(fā)貨點(diǎn)任務(wù)號：1 2

7、3 4 5 6 7X v: 1 2 2 2 2 3 3 X r : 1 4 3 1 2 2 1則該粒子對應(yīng)解路徑為：車 1: 0 1 0車 2: 0 4 5 3 2 0車 3: 0 7 6 0粒子速度向量V與之對應(yīng)表示為V v和V r該表示方法的最大優(yōu)點(diǎn)是使每個(gè)發(fā)貨點(diǎn)都得到車輛的配送服務(wù)，并限制每個(gè)發(fā) 貨點(diǎn)的需求僅能由某一車輛來完成，使解的可行化過程計(jì)算大大減少Z雖然該表 示方法的維數(shù)較高，但由于PSO算法在多維尋優(yōu)問題有著非常好的特性，維數(shù) 的增加并未增加計(jì)算的復(fù)雜性，這一點(diǎn)在實(shí)驗(yàn)結(jié)果中可以看到五、模型的建立與求解在本題中，需要分別計(jì)算以下幾個(gè)內(nèi)容，計(jì)算需求點(diǎn)與中心倉庫及各需求 點(diǎn)間距離，利

8、用粒子群優(yōu)化算法，求出函數(shù)的全局最優(yōu)位置和最后得到的優(yōu)化極 值。5.1需求點(diǎn)與中心倉庫及各需求點(diǎn)間距離利用直角三角形勾股定理，求斜邊長度。A（x,yJ，B（x2, y2），直角坐標(biāo)系中求A,B兩點(diǎn)之間距離 AB二,（y2 -力）2 （X2-xJ2距離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.

9、4962.58633.97127.731011.31459.13565.276574.73372.42245.27738.58811.314067.11973.027613.41618.11143.41755.22759.13567.11906.324671420.39649.40661.465.27673.0276.324605.2粒子群優(yōu)化算法算法實(shí)現(xiàn)過程步驟1初始化粒子群 粒子群劃分成若干個(gè)兩兩相互重疊的相鄰子群； 每個(gè)粒子位置向量X v的每一維隨機(jī)取1K （車輛數(shù)）之間的整數(shù)，Xr 的每一維隨機(jī)取1L（發(fā)貨點(diǎn)任務(wù)數(shù)）之間的實(shí)數(shù)； 每個(gè)速度向量V v的每一維隨機(jī)取-（K - 1）（K -

10、 1）（車輛數(shù)）之間 的整數(shù),V r的每一維隨機(jī)取-（L - 1）（L - 1）之間的實(shí)數(shù)； 用評價(jià)函數(shù)Eval評價(jià)所有粒子； 將初始評價(jià)值作為個(gè)體歷史最優(yōu)解P i ,并尋找各子群內(nèi)的最優(yōu)解P l和總?cè)后w內(nèi)最優(yōu)解P g步驟2重復(fù)執(zhí)行以下步驟，直到滿足終止條件或達(dá)到最大迭代次數(shù) 對每一個(gè)粒子，計(jì)算V v、V r；計(jì)算X v、X r,其中X v向上取整；當(dāng)V、X超過其范圍時(shí)按邊界取值 用評價(jià)函數(shù)E va I評價(jià)所有粒子； 若某個(gè)粒子的當(dāng)前評價(jià)值優(yōu)于其歷史最優(yōu)評價(jià)值，則記當(dāng)前評價(jià)值為該歷史最優(yōu)評價(jià)值，同時(shí)將當(dāng)前位置向量記為該粒子歷史最優(yōu)位置Pi ; 尋找當(dāng)前各相鄰子群內(nèi)最優(yōu)和總?cè)后w內(nèi)最優(yōu)解，若優(yōu)于歷

11、史最優(yōu)解則更新P I、P g針對本題0表示中心倉庫,設(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ù)及所得到的最優(yōu)解，預(yù)計(jì)迭代次數(shù)50,共進(jìn)行20次運(yùn)算運(yùn)算次數(shù)12345678910總距離217.81230.41217.81217.81 3Q3.04217.81303.04217.81217.81230.41運(yùn)算次數(shù)11121314151617181920總距離217.81217.81230.41217

12、.81 2*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 對應(yīng)的行車路線為：車輛一：0760車輛二：010車輛三:0 > 2 > 3 > 4 > 5 > 0行車總距離217.81粒子群優(yōu)化算法達(dá)到最優(yōu)路徑50次的代數(shù)723217717137411928113314212311718224135836201038565359215762567305592921638943148129379六、模型的評價(jià)粒子群優(yōu)化算法結(jié)果

13、分析方法達(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è)粒子能直接獲取群體歷史經(jīng)驗(yàn)和個(gè)體歷史經(jīng)驗(yàn)，比在其他方法中使用精英集（elit ism ）的方法更有效；3）整個(gè)粒子群被劃分為幾個(gè)的子群，且子群之間有一定重疊，從而使收斂于局 部最優(yōu)解的幾率大大減少L正因?yàn)槿绱?，本文將PSO應(yīng)用于帶時(shí)間窗車輛路徑問題求解中，取得了很好的 效果，有著運(yùn)算速度快、解的質(zhì)量與個(gè)體數(shù)目相關(guān)性小、所獲得的解質(zhì)量高等諸 多優(yōu)點(diǎn)七、模型的改進(jìn)和推廣

14、7.1模型的改進(jìn)針對粒子群優(yōu)化算法存在的問題，提出了一種新的改進(jìn)算法基于粒子進(jìn) 化的多粒子群優(yōu)化算法。該算法采用局部版的粒子群優(yōu)化方法，從“粒子進(jìn)化” 和“多種群” 兩個(gè)方面對標(biāo)準(zhǔn)粒子群算法進(jìn)行改進(jìn)。 多個(gè)粒子群彼此獨(dú)立地搜索 解空間， 保持了粒子種群的多樣性， 從而增強(qiáng)了全局搜索能力而適當(dāng)?shù)?“粒子進(jìn) 化”可以使陷入局部最優(yōu)的粒子迅速跳出，有效的避免了算法“早熟” ，提高了 算法的穩(wěn)定性。將基于粒子進(jìn)化的多粒子群優(yōu)化算法用于求解非線性方程組。該算法求解 精度高、收斂速度快，而且克服了一些算法對初值的敏感和需要函數(shù)可導(dǎo)的困難， 能較快地求出復(fù)雜非線性方程組的最優(yōu)解。 數(shù)值仿真結(jié)果顯示了該算法的

15、有效性 和可行性，為求解非線性方程組提供了一種實(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)。本文的 研究表明，改進(jìn)局部辦粒子群算法，能過有效地解決車輛路徑問題。八、參考文獻(xiàn)1李軍 , 郭耀煌 . 物流配送車輛優(yōu)化調(diào)度理論與方法M . 北京 : 中國物資出版社 , 2001.計(jì)2 馬炫，彭芃，劉慶 . 求解帶時(shí)間窗車輛路徑問題的改進(jìn)粒子群算法 算機(jī)工程與應(yīng)用， 2009，45（27）： 200-2023 姜

16、啟源，數(shù)學(xué)建模 ，高教出版社， 2000 年附錄需求點(diǎn)與中心倉庫及各需求點(diǎn)間距離c=; zuobiao=18 5422 6058 6971 7183 4691 3824 4218 40;for i=1:8for j=1:8 c(i,j)=sqrt(zuobiao(j,2)-zuobiao(i,2)A2+(zuobiao(j,1)-zuobiao(i,1)A2);endendc粒子群優(yōu)化算法求解主算法clear all;clc;format long;% 給定初始化條件 -c1=1.4962;%學(xué)習(xí)因子 1c2=1.4962;%學(xué)習(xí)因子 2w=0.7298;%慣性權(quán)重MaxDT=50;%最大迭代

17、次數(shù)D=7;%搜索空間維數(shù)（未知數(shù)個(gè)數(shù)）N=40;%初始化群體個(gè)體數(shù)目% 初始化種群的個(gè)體（ 可以在這里限定位置和速度的范圍)for i=1:Nfor j=1:Dx1(i,j)=ceil(3*rand(); %隨機(jī)初始化位置ceil 是向離它最近的大整數(shù)圓整x2(i,j)=ceil(7*rand();v1(i,j)=2*(2*rand()-1); %隨機(jī)初始化速度%v2(i,j)=6*(2*rand()-1);end end% 先計(jì)算各個(gè)粒子的適應(yīng)度，并初始化 Pbest 和 gbestfor i=1:N y1(i,:)=x1(i,:); y2(i,:)=x2(i,:);pbest(i)=fi

18、tness(y1(i,:),y2(i,:),D);endpg1=x1(1,:); %Pg 為全局最優(yōu)pg2=x2(1,:);for i=2:Nif fitness(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 t=1:MaxDTfor i=1:N v1(i,:)=w*v1(i,:)+c1*rand*(y1(i,:)-x1(i,:)+c2*rand*(pg1-x1(i,:); x1(i,:

19、)=x1(i,:)+v1(i,:);x1(i,:)=ceil(x1(i,:);for j=1:D if x1(i,j)<1 x1(i,j)=1;endif x1(i,j)>3x1(i,j)=3;endendfor j=1:D x2(i,j)=ceil(7*rand();endif fitness(x1(i,:),x2(i,:),D)<pbest(i) y1(i,:)=x1(i,:); y2(i,:)=x2(i,:); pbest(i)=fitness(y1(i,:),y2(i,:),D);endif pbest(i)<fitness(pg1,pg2,D)pg1=x1(i,:);pg2=x2(i,:);endendend最