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

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

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

3、小的車輛行駛路徑，就是求。經(jīng)過初始化粒子群，將初始的適應值作為每個粒子的個體最優(yōu)解，并尋找子群內(nèi)的最優(yōu)解以及全局的最優(yōu)解。重復以上步驟，直到滿足終止條件。本題的最短路徑由計算可知為。關鍵字：粒子群算法、車輛路徑、速度一、 問題的重述一個中心倉庫序號為0，7個需求點序號為17，其位置坐標見表1，中心有3輛車，容量均為1，由這三輛車向7個需求點配送貨物，出發(fā)點和收車點都是中心倉庫。求滿足需求的距離最小的車輛行駛路徑。表1 倉庫中心坐標和需求點坐標及需求量序號01234567坐標（18，54）（22，60）（58，69）（71，71）（83，46）（91，38）（24，42）（18，40）需求量00

4、.890.140.280.330.210.410.57二、 問題假設1現(xiàn)實生活中中心倉庫以及各個需求點之間軍事直線連接，兩點之間距離即為坐標系中兩點坐標間距離。2不因天氣及失火等原因車輛停止運輸。3每個需求點由一輛車供應貨物。三、 符號說明配送貨物車輛數(shù)需求點個數(shù)貨物需求量配送貨物車輛的容量從點i到j的距離需求點i由k車配送車k從i行駛到j四、 問題分析4.1算法分析車輛路徑問題（VRP）可以描述為有一個中心倉庫，擁有K輛車，容量分別為，負責向L個需求點配送貨物，貨物需求量為，且；表示從點i到j的距離。求滿足需求的距離最小的車輛行駛路徑。將中心倉庫編號為0，需求點編號為1，2，L。數(shù)學模型為:

5、 s.t. 其中，在本題中，貨物需求量，利用粒子群優(yōu)化算法，經(jīng)過初始化粒子群，將初始的適應值作為每個粒子的個體最優(yōu)解，并尋找子群內(nèi)的最優(yōu)解以及全局的最優(yōu)解。重復以上步驟，直到滿足終止條件。 4.2舉例具體演算分析例如, 設VRP 問題中發(fā)貨點任務數(shù)為7, 車輛數(shù)為3, 若某粒子的位置向量X 為:發(fā)貨點任務號: 1 2 3 4 5 6 7X v: 1 2 2 2 2 3 3X r: 1 4 3 1 2 2 1則該粒子對應解路徑為:車1: 0 1 0車2: 0 4 5 3 2 0車3: 0 7 6 0粒子速度向量V 與之對應表示為V v 和V r該表示方法的最大優(yōu)點是使每個發(fā)貨點都得到車輛的配送服

6、務, 并限制每個發(fā)貨點的需求僅能由某一車輛來完成, 使解的可行化過程計算大大減少Z雖然該表示方法的維數(shù)較高, 但由于PSO 算法在多維尋優(yōu)問題有著非常好的特性, 維數(shù)的增加并未增加計算的復雜性, 這一點在實驗結果中可以看到五、 模型的建立與求解在本題中，需要分別計算以下幾個內(nèi)容，計算需求點與中心倉庫及各需求點間距離，利用粒子群優(yōu)化算法，求出函數(shù)的全局最優(yōu)位置和最后得到的優(yōu)化極值。5.1需求點與中心倉庫及各需求點間距離利用直角三角形勾股定理，求斜邊長度。，直角坐標系中求A,B兩點之間距離距離01234567007.211142.7255.6665.4974.73313.4161417.21110

7、37.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

8、.1算法實現(xiàn)過程步驟1初始化粒子群粒子群劃分成若干個兩兩相互重疊的相鄰子群;每個粒子位置向量X v 的每一維隨機取1 K (車輛數(shù)) 之間的整數(shù), X r 的每一維隨機取1L(發(fā)貨點任務數(shù)) 之間的實數(shù);每個速度向量V v 的每一維隨機取- (K - 1) (K - 1) (車輛數(shù)) 之間的整數(shù),V r 的每一維隨機取- (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重復執(zhí)行以下步驟, 直到滿足終止條件或達到最大迭代次數(shù)對每一個粒子, 計算V v、V r; 計算X

9、v、X r, 其中X v 向上取整; 當V 、X 超過其范圍時按邊界取值 用評價函數(shù)E va l 評價所有粒子; 若某個粒子的當前評價值優(yōu)于其歷史最優(yōu)評價值, 則記當前評價值為該歷史最優(yōu)評價值, 同時將當前位置向量記為該粒子歷史最優(yōu)位置P i; 尋找當前各相鄰子群內(nèi)最優(yōu)和總?cè)后w內(nèi)最優(yōu)解, 若優(yōu)于歷史最優(yōu)解則更新P l、P g5.2.2針對本題0表示中心倉庫, 設車輛容量皆為q= 1. 0, 由3輛車完成所有任務，初始化群體個數(shù)n= 40; 慣性權重w = 0. 729;學習因子 c1= c2= 1. 49445; 最大代數(shù)；搜索空間維數(shù)（未知數(shù)個數(shù)）算法得到的最優(yōu)值的代數(shù)及所得到的最優(yōu)解，預計

10、迭代次數(shù)50，共進行20次運算運算次數(shù)12345678910總距離217.81230.41217.81217.81303.04217.81303.04217.81217.81230.41運算次數(shù)11121314151617181920總距離217.81217.81230.41217.81217.81217.81217.81217.81217.81217.81從實驗結果分析，15次達到已知最優(yōu)解，得到的最優(yōu)總路徑為：對應的行車路線為：車輛一：車輛二：車輛三:行車總距離 粒子群優(yōu)化算法達到最優(yōu)路徑50次的代數(shù)723217717137411928113314212311718224135836201

11、038565359215762567305592921638943148129379六、 模型的評價粒子群優(yōu)化算法結果分析方法達到最優(yōu)路徑次數(shù)未達最優(yōu)路徑次數(shù)達到最優(yōu)路徑平均代數(shù)達到最優(yōu)路徑平均時間（S）粒子群50028.363.04分析PSO 方法, 可以看出它與GA 等其他演化算法的最大不同在于1) 迭代運算中只涉及到初等運算, 且運算量非常少;2) 每個粒子能直接獲取群體歷史經(jīng)驗和個體歷史經(jīng)驗, 比在其他方法中使用精英集(elit ism ) 的方法更有效;3) 整個粒子群被劃分為幾個的子群, 且子群之間有一定重疊, 從而使收斂于局部最優(yōu)解的幾率大大減少L正因為如此, 本文將PSO 應用

12、于帶時間窗車輛路徑問題求解中, 取得了很好的效果, 有著運算速度快、解的質(zhì)量與個體數(shù)目相關性小、所獲得的解質(zhì)量高等諸多優(yōu)點七、 模型的改進和推廣7.1模型的改進針對粒子群優(yōu)化算法存在的問題，提出了一種新的改進算法基于粒子進化的多粒子群優(yōu)化算法。該算法采用局部版的粒子群優(yōu)化方法，從“粒子進化”和“多種群”兩個方面對標準粒子群算法進行改進。多個粒子群彼此獨立地搜索解空間，保持了粒子種群的多樣性，從而增強了全局搜索能力而適當?shù)摹傲Ｗ舆M化”可以使陷入局部最優(yōu)的粒子迅速跳出，有效的避免了算法“早熟”，提高了算法的穩(wěn)定性。將基于粒子進化的多粒子群優(yōu)化算法用于求解非線性方程組。該算法求解精度高、收斂速度快，

13、而且克服了一些算法對初值的敏感和需要函數(shù)可導的困難，能較快地求出復雜非線性方程組的最優(yōu)解。數(shù)值仿真結果顯示了該算法的有效性和可行性，為求解非線性方程組提供了一種實用的方法。7.2模型的推廣作為物流系統(tǒng)優(yōu)化中的重要一環(huán)，合理安排車輛路徑、進行物流車輛優(yōu)化調(diào)度可以提高物流經(jīng)濟效益、實現(xiàn)物流科學化。粒子群算法在多維尋優(yōu)中有著非常好的特性，加入“鄰居算子”的粒子群算法能使算法更好的全局尋優(yōu)。本文的研究表明，改進局部辦粒子群算法，能過有效地解決車輛路徑問題。八、 參考文獻1李軍, 郭耀煌. 物流配送車輛優(yōu)化調(diào)度理論與方法M . 北京: 中國物資出版社, 2001.2 馬炫，彭芃，劉慶. 求解帶時間窗車輛

14、路徑問題的改進粒子群算法.計算機工程與應用，2009，45（27）：200-2023姜啟源，數(shù)學建模，高教出版社，2000年附錄需求點與中心倉庫及各需求點間距離c=;zuobiao=18 5422 6058 6971 7183 4691 3824 4218 40;for i=1:8 for j=1:8 c(i,j)=sqrt(zuobiao(j,2)-zuobiao(i,2)2+(zuobiao(j,1)-zuobiao(i,1)2); endendc粒子群優(yōu)化算法求解主算法clear all;clc;format long;%-給定初始化條件-c1=1.4962; %學習因子1c2=1.49

15、62; %學習因子2w=0.7298; %慣性權重MaxDT=50; %最大迭代次數(shù)D=7; %搜索空間維數(shù)（未知數(shù)個數(shù)）N=40; %初始化群體個體數(shù)目%-初始化種群的個體(可以在這里限定位置和速度的范圍)-for i=1:N for j=1:D x1(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%-先計算各個粒子的適應度，并初始化Pbest和gbest- for i=1:

16、N y1(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:N if fitness(x1(i,:),x2(i,:),D)<fitness(pg1,pg2,D) pg1=x1(i,:); pg2=x2(i,:); gbest=fitness(pg1,pg2,D); end end%-進入主要循環(huán)，按照公式依次迭代，直到滿足精度要求- for t=1:MaxDT for i=1:N v1(i,:)=w*v1(i,:)+

17、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:D if x1(i,j)<1 x1(i,j)=1; end if x1(i,j)>3 x1(i,j)=3; end end for j=1:D x2(i,j)=ceil(7*rand(); end if fitness(x1(i,:),x2(i,:),D)<pbest(i) y1(i,:)=x1(i,:); y2(i,:)=x2(i,:); pbest(i)=fitness(

18、y1(i,:),y2(i,:),D); end if pbest(i)<fitness(pg1,pg2,D) pg1=x1(i,:); pg2=x2(i,:); end end end%-最后給出計算結果 disp('*') disp('函數(shù)的全局最優(yōu)位置為：') Solution1=pg1 Solution2=pg2disp('最后得到的優(yōu)化極值為：')Result=fitness(pg1,pg2,D)disp('*')輔助算法一function result=fitness(x1,x2,D);aa=inf inf inf inf inf inf inf;bb=inf inf inf inf inf inf inf;cc=inf inf inf inf inf inf inf;for i=1:D if x1(i)=1 aa(i)=x2(i); else if x1(i)=2 bb(i)=x2(i); else cc(i)=x2(i); end end