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

粒子群優(yōu)化算法

計算車輛路徑問題摘要粒子群優(yōu)化算法中，粒子群由多個粒子組成，每個粒子的位置代表優(yōu)化問題在□隹搜索空間中潛在的解。根據(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)化算法解決車輛路徑問題。車輛路徑問題由Dantzig和Ramser于1959年首次提出的，它是指對一系列發(fā)貨點（或收貨點），組成適當(dāng)?shù)男熊嚶窂剑管囕v有序地通過它們，在滿足一定約束條件的情況下，達(dá)到一定的目標(biāo)（諸如路程最短、費用最小，耗費時間盡量少等），屬于完全NP問題，在運籌、計算機、物流、管理等學(xué)科均有重要意義。粒子群算法是最近出現(xiàn)的一種模擬鳥群飛行的仿生算法，有著個體數(shù)目少、計算簡單、魯棒性好等優(yōu)點，在各類多維連續(xù)空間優(yōu)化問題上均取得非常好的效果。本文將PSO應(yīng)用于車輛路徑問題求解中，取得了很好的效果。針對本題，一個中心倉庫、7個需求點、中心有3輛車，容量均為1,由這三輛車向7個需求點配送貨物，出發(fā)點和收車點都是中心倉庫。k=3,q1=qA=q3=1,=7.=0.89,g2=0.14,g3=0.28,g4=0.33,g5=0.21,g6=0.41,g7=0.57mgia Xk。利用matlab編程，求出需求點和中心倉庫、需求點之間的各個距離，用q表示。求滿足需求的最小的車輛行駛路徑，就是求minz八77C.X.。經(jīng)過初始化粒子群，將初始的適應(yīng)值作為每個粒子的個ijk重復(fù)以上步驟，直到滿足體最優(yōu)解，并尋找子群內(nèi)的最優(yōu)解以及全局的最優(yōu)解。重復(fù)以上步驟，直到滿足終止條件。本題的最短路徑由計算可知為217.81。關(guān)鍵字：粒子群算法、車輛路徑、速度問題的重述一個中心倉庫序號為0，7個需求點序號為1~7,其位置坐標(biāo)見表1,中心有3輛車，容量均為1,由這三輛車向7個需求點配送貨物，出發(fā)點和收車點都是中心倉庫。求滿足需求的距離最小的車輛行駛路徑。二、問題假設(shè)表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每個需求點由一輛車供應(yīng)貨物。三、符號說明k 配送貨物車輛數(shù)l 需求點個數(shù)gi貨物需求量qk配送貨物車輛的容量Cj從點i到j(luò)的距離yki需求點i由k車配送XLijk車k從i行駛到j(luò)四、問題分析4.1算法分析車輛路徑問題(VRP可以描述為有一個中心倉庫，擁有 K輛車，容量分別為q'k=1,2,...，K)，負(fù)責(zé)向L個需求點配送貨物，貨物需求量為gi(i=1,2,...，L)，且maxgAmaxqk；c..表示從點i至uj的距離。求滿足需求的距離最小的車輛行駛路徑。將中心倉庫編號為 0,需求點編號為1,2,…，L。數(shù)學(xué)模型為：minz=、、、CjXjkijks?t. giykiXk，—ki、y/=1,2,,lk'Xijk二ykj，j=0，〔」；一ki'Xjk=yki,i=0,1,X;―kX=(Xjk)SXjk=0或1,i,j=0,1,上；-kyki=0或1,i=0,1」；-k白■擊需求點i由k車配送1車k從i行駛駛j其中，否則，部」0否則k=3q=q2=q3=1,1=7.貨物需求量g八0.89,g八0.14,g八0.28,g八0.33,g八0.21,g八0.41,g八0.57,利用粒子群優(yōu)化算法，經(jīng)過初始化粒子群，將初始的適應(yīng)值作為每個粒子的個體最優(yōu)解， 并尋找子群內(nèi)的最優(yōu)解以及全局的最優(yōu)解。重復(fù)以上步驟，直到滿足終止條件。4.2舉例具體演算分析例如，設(shè)VRP問題中發(fā)貨點任務(wù)數(shù)為7,車輛數(shù)為3,若某粒子的位置向量X為：發(fā)貨點任務(wù)號：1234567XV：1222233Xr:1431221則該粒子對應(yīng)解路徑為：車1:0—1—0車2:0—4—5—3—2—0車3:0—7—6—0粒子速度向量V與之對應(yīng)表示為Vv和Vr該表示方法的最大優(yōu)點是使每個發(fā)貨點都得到車輛的配送服務(wù)，并限制每個發(fā)貨點的需求僅能由某一車輛來完成，使解的可行化過程計算大大減少Z雖然該表示方法的維數(shù)較高，但由于PSO算法在多維尋優(yōu)問題有著非常好的特性，維數(shù)的增加并未增加計算的復(fù)雜性，這一點在實驗結(jié)果中可以看到五、模型的建立與求解在本題中，需要分別計算以下幾個內(nèi)容，計算需求點與中心倉庫及各需求點間距離，利用粒子群優(yōu)化算法，求出函數(shù)的全局最優(yōu)位置和最后得到的優(yōu)化極值。5.1需求點與中心倉庫及各需求點間距離利用直角三角形勾股定理，求斜邊長度。 AX’yJB(x2,y2)，直角坐標(biāo)系中求A,B兩點之間距離ABf(y2-yj2(x2-x「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.13567.11906.324671420.39649.40661.465.27673.0276.324605.2粒子群優(yōu)化算法5.2.1算法實現(xiàn)過程步驟1初始化粒子群粒子群劃分成若干個兩兩相互重疊的相鄰子群；每個粒子位置向量Xv的每一維隨機取1K(車輛數(shù))之間的整數(shù)，Xr的每一維隨機取1L(發(fā)貨點任務(wù)數(shù))之間的實數(shù)；每個速度向量Vv的每一維隨機取-(K-1) (K-1)(車輛數(shù))之間的整數(shù),Vr的每一維隨機取-(L-1) (L-1)之間的實數(shù)；用評價函數(shù)Eval評價所有粒子；將初始評價值作為個體歷史最優(yōu)解Pi,并尋找各子群內(nèi)的最優(yōu)解Pl和總?cè)后w內(nèi)最優(yōu)解Pg步驟2重復(fù)執(zhí)行以下步驟，直到滿足終止條件或達(dá)到最大迭代次數(shù)對每一個粒子，計算Vv、Vr；計算Xv、Xr,其中Xv向上取整；當(dāng)V、X超過其范圍時按邊界取值用評價函數(shù)EvaI評價所有粒子；若某個粒子的當(dāng)前評價值優(yōu)于其歷史最優(yōu)評價值，則記當(dāng)前評價值為該歷史最優(yōu)評價值，同時將當(dāng)前位置向量記為該粒子歷史最優(yōu)位置 Pi；尋找當(dāng)前各相鄰子群內(nèi)最優(yōu)和總?cè)后w內(nèi)最優(yōu)解，若優(yōu)于歷史最優(yōu)解則更新PI、pg5.2.2針對本題0表示中心倉庫，設(shè)車輛容量皆為q=1.0,由3輛車完成所有任務(wù)，初始化群體個數(shù)n=40;慣性權(quán)重w=0.729;學(xué)習(xí)因子c1=c2=1.49445;最大代數(shù)MaxDT=50;搜索空間維數(shù)（未知數(shù)個數(shù)） D=7;算法得到的最優(yōu)值的代數(shù)及所得到的最優(yōu)解， 預(yù)計迭代次數(shù)50,共進(jìn)行20次運算運算次數(shù)12345678910總距離217.81230.41217.81217.813￡3.04217.81303.04217.81217.81230.41運算次數(shù)11121314151617181920總距離217.81217.81230.41217.81:■>17.81217.81217.81217.81217.81217.81從實驗結(jié)果分析，15次達(dá)到已知最優(yōu)解，得到的最優(yōu)總路徑為:0r7-6_0-1-0-2-3-4-5_0對應(yīng)的行車路線為：車輛一：0》7》6》0車輛二：0》1》0車輛三:0>2>3>4>5>0行車總距離217.81粒子群優(yōu)化算法達(dá)到最優(yōu)路徑50次的代數(shù)723217717137411928113314212311718224135836201038565359215762567305592921638943148129379六、模型的評價粒子群優(yōu)化算法結(jié)果分析方法達(dá)到最優(yōu)路徑次數(shù)未達(dá)最優(yōu)路徑次數(shù)達(dá)到最優(yōu)路徑平均代數(shù)達(dá)到最優(yōu)路徑平均時間（S）粒子群50028.363.04分析PSO方法,可以看出它與GA等其他演化算法的最大不同在于1） 迭代運算中只涉及到初等運算，且運算量非常少；2） 每個粒子能直接獲取群體歷史經(jīng)驗和個體歷史經(jīng)驗，比在其他方法中使用精英集（elitism）的方法更有效；3） 整個粒子群被劃分為幾個的子群，且子群之間有一定重疊，從而使收斂于局部最優(yōu)解的幾率大大減少L正因為如此，本文將PSO應(yīng)用于帶時間窗車輛路徑問題求解中，取得了很好的效果，有著運算速度快、解的質(zhì)量與個體數(shù)目相關(guān)性小、所獲得的解質(zhì)量高等諸多優(yōu)點七、模型的改進(jìn)和推廣7.1模型的改進(jìn)針對粒子群優(yōu)化算法存在的問題，提出了一種新的改進(jìn)算法一基于粒子進(jìn)化的多粒子群優(yōu)化算法。該算法采用局部版的粒子群優(yōu)化方法，從“粒子進(jìn)化”和“多種群”兩個方面對標(biāo)準(zhǔn)粒子群算法進(jìn)行改進(jìn)。多個粒子群彼此獨立地搜索解空間，保持了粒子種群的多樣性，從而增強了全局搜索能力而適當(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)濟效益、實現(xiàn)物流科學(xué)化。粒子群算法在多維尋優(yōu)中有著非常好的特性，加入“鄰居算子”的粒子群算法能使算法更好的全局尋優(yōu)。本文的研究表明，改進(jìn)局部辦粒子群算法，能過有效地解決車輛路徑問題。八、參考文獻(xiàn)李軍，郭耀煌.物流配送車輛優(yōu)化調(diào)度理論與方法 [M].北京：中國物資出版社，2001.馬炫，彭芃，劉慶.求解帶時間窗車輛路徑問題的改進(jìn)粒子群算法算機工程與應(yīng).計用，2009，45（27）：200-202姜啟源，《數(shù)學(xué)建?！?，高教出版社，2000年附錄需求點與中心倉庫及各需求點間距離c=[];zuobiao=[18542260586971718346913824421840];fori=1:8forj=1:8c(i,j)=sqrt((zuobiao(j,2)-zuobiao(i,2))A2+(zuobiaoQ,1)-zuobiao(i,1))a2);endendc粒子群優(yōu)化算法求解主算法clearall;clc;formatlong;% 給定初始化條件 -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ù)目%-----初始化種群的個體(可以在這里限定位置和速度的范圍)fori=1:Nforj=1:Dx1(i,j)=ceil(3*rand());% 隨機初始化位置ceil 是向離它最近的大整數(shù)圓整x2(i,j)=ceil(7*rand());v1(i,j)=2*(2*rand()-1);%隨機初始化速度％v2(i,j)=6*(2*rand()-1);endend%-----先計算各個粒子的適應(yīng)度，并初始化Pbest和gbest fori=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『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)，按照公式依次迭代，直到滿足精度要求 fort=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=x2(i,:);endendend%—最后給出計算結(jié)果disp（'disp（'函數(shù)的全局最優(yōu)位置為：'）Solution1=pg1Solut