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

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

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

3、 7. 貨物需求量g1 0.89,g2 0.14,g3 0.28,g4 0.33,g5 0.21,g6 0.41,g7 0.57， 且m gi aqxk 。利用matlab 編程，求出需求點和中心倉庫、需求點之間的各個 距 離 ， 用cij 表 示 。 求 滿 足 需 求 的 最 小 的 車 輛 行 駛 路 徑 ， 就 是 求m i nZci j xi j。經(jīng)過初始化粒子群，將初始的適應(yīng)值作為每個粒子的個 kijk體最優(yōu)解，并尋找子群內(nèi)的最優(yōu)解以及全局的最優(yōu)解。重復(fù)以上步驟，直到滿足終止條件。本題的最短路徑由計算可知為217.81關(guān)鍵字：粒子群算法、車輛路徑、速度一、 問題的重述一個中心倉庫序

4、號為0， 7 個需求點序號為17， 其位置坐標(biāo)見表1， 中心有3 輛車，容量均為1，由這三輛車向7 個需求點配送貨物，出發(fā)點和收車點都是中心倉庫。求滿足需求的距離最小的車輛行駛路徑。表 1 倉庫中心坐標(biāo)和需求點坐標(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)實生活中中心倉庫以及各個需求點之間軍事直線連接，兩點之間距離即為 坐標(biāo)系中兩點坐標(biāo)間距離。2不因天氣及失火等原因車輛停止運輸。3每個需求點由

5、一輛車供應(yīng)貨物。三、 符號說明k配送貨物車輛數(shù)l需求點個數(shù)gi貨物需求量qk配送貨物車輛的容量cij從點i 到 j 的距離yki需求點i 由 k 車配送xijk車 k 從 i 行駛到j(luò)問題分析4.1 算法分析車輛路徑問題(VRP)可以描述為有一個中心倉庫，擁有K 輛車，容量分 別 為qk(k 1,2, ,K) ， 負(fù) 責(zé) 向 L 個 需 求 點 配 送 貨 物 ， 貨 物 需 求 量 為gi(i 1,2, ,L)，且maxgi maxqk； cij 表示從點i 到 j 的距離。求滿足需求的距離最小的車輛行駛路徑。將中心倉庫編號為0，需求點編號為1 ， 2，L。數(shù)學(xué)模型為:min Zcijxij

6、ki jks.t.gi yki qk, kyki1,i 1,2, ,Lkxijkykj, j 0,1,L; kxijkyki,i 0,1,L; kX(xijk)Sxijk0或 1,i, j 0,1,L; kyki0或1,i 0,1, , L; k其中，1 yki0需求點 i 由 k車配送 ，1 車k從i行 駛駛 j否則xijk0 否 則在 本 題 中 ， k 3,q1q2q3 1,l 7. 貨 物 需 求 量g1 0.89,g2 0.14,g3 0.28,g4 0.33, g5 0.21,g6 0.41,g7 0.57，利用粒子群優(yōu)化算法，經(jīng)過初始化粒子群，將初始的適應(yīng)值作為每個粒子的個體最優(yōu)

7、解，并尋找子群內(nèi)的最優(yōu)解以及全局的最優(yōu)解。重復(fù)以上步驟，直到滿足終止條件。4.2 舉例具體演算分析例如 , 設(shè) VRP 問題中發(fā)貨點任務(wù)數(shù)為7, 車輛數(shù)為 3, 若某粒子的位置向量X為:發(fā)貨點任務(wù)號: 1 2 3 4 5 6 7X v: 1 2 2 2 2 3 3X 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)點是使每個發(fā)貨點都得到車輛的配送服務(wù), 并限制每個發(fā)貨點的需求僅能由某一車輛來完成, 使解的可行化過程計算大大減少Z雖然該表示方法的維數(shù)

8、較高, 但由于 PSO 算法在多維尋優(yōu)問題有著非常好的特性, 維數(shù)的增加并未增加計算的復(fù)雜性, 這一點在實驗結(jié)果中可以看到五、 模型的建立與求解在本題中，需要分別計算以下幾個內(nèi)容，計算需求點與中心倉庫及各需求點間距離，利用粒子群優(yōu)化算法，求出函數(shù)的全局最優(yōu)位置和最后得到的優(yōu)化極值。需求點與中心倉庫及各需求點間距離利用直角三角形勾股定理，求斜邊長度。A(x1,y1)， B(x2, y2)，直角坐標(biāo)系中求 A,B 兩點之間距離AB(y2 y1)2 (x2 x1)2距離01234567007.211142.7255.6665.4974.73313.4161417.2111037.10850.2262

9、.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.13567.11906.324671420.39649.40661.465.27673.0276.32460粒子群優(yōu)化算法算法實現(xiàn)過程步驟 1 初始化粒子群 T

10、OC o 1-5 h z 粒子群劃分成若干個兩兩相互重疊的相鄰子群;每個粒子位置向量X v 的每一維隨機(jī)取1 K ( 車輛數(shù) ) 之間的整數(shù), X r的每一維隨機(jī)取1 L(發(fā)貨點任務(wù)數(shù)) 之間的實數(shù);每個速度向量V v 的每一維隨機(jī)取- ( K - 1) ( K - 1) ( 車輛數(shù) ) 之間的整數(shù) , V r 的每一維隨機(jī)取- ( L - 1) ( L - 1) 之間的實數(shù);用評價函數(shù)Eval 評價所有粒子;將初始評價值作為個體歷史最優(yōu)解P i , 并尋找各子群內(nèi)的最優(yōu)解P l 和總?cè)后w內(nèi)最優(yōu)解P g步驟 2 重復(fù)執(zhí)行以下步驟, 直到滿足終止條件或達(dá)到最大迭代次數(shù)對每一個粒子, 計算 V v

11、、 V r ; 計算X v、 X r , 其中 X v 向上取整 ; 當(dāng) V 、X 超過其范圍時按邊界取值用評價函數(shù)E va l 評價所有粒子;若某個粒子的當(dāng)前評價值優(yōu)于其歷史最優(yōu)評價值, 則記當(dāng)前評價值為該歷史最優(yōu)評價值, 同時將當(dāng)前位置向量記為該粒子歷史最優(yōu)位置P i ;尋找當(dāng)前各相鄰子群內(nèi)最優(yōu)和總?cè)后w內(nèi)最優(yōu)解, 若優(yōu)于歷史最優(yōu)解則更新P l、 P g針對本題0表示中心倉庫, 設(shè)車輛容量皆為q= 1. 0, 由 3輛車完成所有任務(wù)，初始化群體個數(shù)n= 40; 慣性權(quán)重w = 0. 729; 學(xué)習(xí)因子c1= c2= 1. 49445; 最大代數(shù) TOC o 1-5 h z MaxDT 50

12、；搜索空間維數(shù)（未知數(shù)個數(shù)）D 7;算法得到的最優(yōu)值的代數(shù)及所得到的最優(yōu)解，預(yù)計迭代次數(shù)50， 共進(jìn)行 20次運算運算次數(shù)12345678910總距離217.81230.41217.81217.81 303.04217.81303.04217.81217.81230.41運算次數(shù)11121314151617181920總距離217.81217.81230.41217.81 217.81217.81217.81217.81217.81217.81 TOC o 1-5 h z 從實驗結(jié)果分析，15次達(dá)到已知最優(yōu)解，得到的最優(yōu)總路徑為：07601023450對應(yīng)的行車路線為：車輛一：0760車輛二：

13、010車輛三 : 023450行車總距離217.81粒子群優(yōu)化算法達(dá)到最優(yōu)路徑50次的代數(shù)7232177171374119 7.1 模型的改進(jìn) 28113314212311718224135836201038565359215762567305592921638943148129379六、 模型的評價粒子群優(yōu)化算法結(jié)果分析方法達(dá)到最優(yōu) 路徑次數(shù)未達(dá)最優(yōu) 路徑次數(shù)達(dá)到最優(yōu)路 徑平均代數(shù)達(dá)到最優(yōu)路徑平均時間(S)粒子群50028.363.04分析PSO 方法, 可以看出它與GA 等其他演化算法的最大不同在于 TOC o 1-5 h z 迭代運算中只涉及到初等運算, 且運算量非常少;每個粒子能直接獲

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

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

16、尋優(yōu)。本文的研究表明，改進(jìn)局部辦粒子群算法，能過有效地解決車輛路徑問題。八、 參考文獻(xiàn)李軍 , 郭耀煌 . 物流配送車輛優(yōu)化調(diào)度理論與方法M . 北京 : 中國物資出版社, 2001.馬炫，彭芃，劉慶. 求解帶時間窗車輛路徑問題的改進(jìn)粒子群算法. 計算機(jī)工程與應(yīng)用，2009， 45（ 27） ： 200-202姜啟源， 數(shù)學(xué)建模，高教出版社，2000 年附錄需求點與中心倉庫及各需求點間距離c=;zuobiao=18 5422 6058 6971 7183 4691 3824 4218 40;for i=1:8for j=1:8c(i,j)=sqrt(zuobiao(j,2)-zuobiao(i

17、,2)2+(zuobiao(j,1)-zuobiao(i,1) 2);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;%最大迭代次數(shù)D=7;%搜索空間維數(shù)(未知數(shù)個數(shù))N=40;%初始化群體個體數(shù)目% 初始化種群的個體( 可以在這里限定位置和速度的范圍)for i=1:Nfor j=1:D是向離它最近的大整數(shù)圓整x1(i,j)=ceil(3*rand(); %隨機(jī)初始化位置ceilx2(i,j)=ceil(7*rand();v

18、1(i,j)=2*(2*rand()-1); %隨機(jī)初始化速度%v2(i,j)=6*(2*rand()-1);endend% 先計算各個粒子的適應(yīng)度，并初始化Pbest 和 gbestfor i=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,:);for i=2:Nif fitness(x1(i,:),x2(i,:),D)fitness(pg1,pg2,D)pg1=x1(i,:);pg2=x2(i,:);gbest=fitness(p

19、g1,pg2,D);endend% 進(jìn)入主要循環(huán)，按照公式依次迭代，直到滿足精度要求for t=1:MaxDTfor i=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,:);for j=1:Dif x1(i,j)3 x1(i,j)=3;endendfor j=1:Dx2(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(pg