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

1、粒子群優(yōu)化算法計(jì)算車輛路徑問題摘要粒子群優(yōu)化算法中,粒子群由多個(gè)粒子組成,每個(gè)粒子的位置代表優(yōu)化問題在D維搜索空間中潛在的解。根據(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 和Ram ser 于1959年首次提出的, 它是指對(duì)一系列發(fā)貨點(diǎn)(或收貨點(diǎn)) , 組成適當(dāng)?shù)男熊嚶窂? 使車輛有序地通過它們

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

3、小的車輛行駛路徑，就是求。經(jīng)過初始化粒子群，將初始的適應(yīng)值作為每個(gè)粒子的個(gè)體最優(yōu)解，并尋找子群內(nèi)的最優(yōu)解以及全局的最優(yōu)解。重復(fù)以上步驟，直到滿足終止條件。本題的最短路徑由計(jì)算可知為。關(guān)鍵字：粒子群算法、車輛路徑、速度一、 問題的重述一個(gè)中心倉庫序號(hào)為0，7個(gè)需求點(diǎn)序號(hào)為17，其位置坐標(biāo)見表1，中心有3輛車，容量均為1，由這三輛車向7個(gè)需求點(diǎn)配送貨物，出發(fā)點(diǎn)和收車點(diǎn)都是中心倉庫。求滿足需求的距離最小的車輛行駛路徑。表1 倉庫中心坐標(biāo)和需求點(diǎn)坐標(biāo)及需求量序號(hào)01234567坐標(biāo)（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二、 問題假設(shè)1現(xiàn)實(shí)生活中中心倉庫以及各個(gè)需求點(diǎn)之間軍事直線連接，兩點(diǎn)之間距離即為坐標(biāo)系中兩點(diǎn)坐標(biāo)間距離。2不因天氣及失火等原因車輛停止運(yùn)輸。3每個(gè)需求點(diǎn)由一輛車供應(yīng)貨物。三、 符號(hào)說明配送貨物車輛數(shù)需求點(diǎn)個(gè)數(shù)貨物需求量配送貨物車輛的容量從點(diǎn)i到j(luò)的距離需求點(diǎn)i由k車配送車k從i行駛到j(luò)四、 問題分析4.1算法分析車輛路徑問題（VRP）可以描述為有一個(gè)中心倉庫，擁有K輛車，容量分別為，負(fù)責(zé)向L個(gè)需求點(diǎn)配送貨物，貨物需求量為，且；表示從點(diǎn)i到j(luò)的距離。求滿足需求的距離最小的車輛行駛路徑。將中心倉庫編號(hào)為0，需求點(diǎn)編號(hào)為1，2，L。數(shù)學(xué)模型為:

5、 s.t. 其中，在本題中，貨物需求量，利用粒子群優(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ù)號(hào): 1 2 3 4 5 6 7X v: 1 2 2 2 2 3 3X r: 1 4 3 1 2 2 1則該粒子對(duì)應(yīng)解路徑為:車1: 0 1 0車2: 0 4 5 3 2 0車3: 0 7 6 0粒子速度向量V 與之對(duì)應(yīng)表示為V v 和V r該表示方法的最大優(yōu)點(diǎn)是使每個(gè)發(fā)貨點(diǎn)都得到車輛的配送服

6、務(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)間距離，利用粒子群優(yōu)化算法，求出函數(shù)的全局最優(yōu)位置和最后得到的優(yōu)化極值。5.1需求點(diǎn)與中心倉庫及各需求點(diǎn)間距離利用直角三角形勾股定理，求斜邊長度。，直角坐標(biāo)系中求A,B兩點(diǎn)之間距離距離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算法實(shí)現(xiàn)過程步驟1初始化粒子群粒子群劃分成若干個(gè)兩兩相互重疊的相鄰子群;每個(gè)粒子位置向量X v 的每一維隨機(jī)取1 K (車輛數(shù)) 之間的整數(shù), X r 的每一維隨機(jī)取1L(發(fā)貨點(diǎn)任務(wù)數(shù)) 之間的實(shí)數(shù);每個(gè)速度向量V v 的每一維隨機(jī)取- (K - 1) (K - 1) (車輛數(shù)) 之間的整數(shù),V r 的每一維隨機(jī)取- (L - 1) (L - 1) 之間的實(shí)數(shù);用評(píng)價(jià)函數(shù)Eval 評(píng)價(jià)所有粒子;將初始評(píng)價(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ù)對(duì)每一個(gè)粒子, 計(jì)算V v、V r; 計(jì)算X

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

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

11、038565359215762567305592921638943148129379六、 模型的評(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è)粒子能直接獲取群體歷史經(jīng)驗(yàn)和個(gè)體歷史經(jīng)驗(yàn), 比在其他方法中使用精英集(elit ism ) 的方法更有效;3) 整個(gè)粒子群被劃分為幾個(gè)的子群, 且子群之間有一定重疊, 從而使收斂于局部最優(yōu)解的幾率大大減少L正因?yàn)槿绱? 本文將PSO 應(yīng)用

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

13、而且克服了一些算法對(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)。本文的研究表明，改進(jìn)局部辦粒子群算法，能過有效地解決車輛路徑問題。八、 參考文獻(xiàn)1李軍, 郭耀煌. 物流配送車輛優(yōu)化調(diào)度理論與方法M . 北京: 中國物資出版社, 2001.2 馬炫，彭芃，劉慶. 求解帶時(shí)間窗車輛

14、路徑問題的改進(jìn)粒子群算法.計(jì)算機(jī)工程與應(yīng)用，2009，45（27）：200-2023姜啟源，數(shù)學(xué)建模，高教出版社，2000年附錄需求點(diǎn)與中心倉庫及各需求點(diǎn)間距離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; %學(xué)習(xí)因子1c2=1.49

15、62; %學(xué)習(xí)因子2w=0.7298; %慣性權(quán)重MaxDT=50; %最大迭代次數(shù)D=7; %搜索空間維數(shù)（未知數(shù)個(gè)數(shù)）N=40; %初始化群體個(gè)體數(shù)目%-初始化種群的個(gè)體(可以在這里限定位置和速度的范圍)-for i=1:N for j=1:D x1(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); endend%-先計(jì)算各個(gè)粒子的適應(yīng)度，并初始化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%-進(jìn)入主要循環(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%-最后給出計(jì)算結(jié)果 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