基于改進(jìn)粒子群優(yōu)化算法的車輛路徑問題研究

基于改進(jìn)粒子群優(yōu)化算法的車輛路徑問題研究

隨著市場(chǎng)經(jīng)濟(jì)的發(fā)展和物流技術(shù)專業(yè)化水平的提高，物流行業(yè)得到了迅速發(fā)展。其中車輛路徑問題(VRP)是亟待解決的一個(gè)重要問題。該問題由Dantzig和Ramser于1959年首次提出,它是物流決策中的關(guān)鍵環(huán)節(jié),直接影響到顧客的服務(wù)質(zhì)量與運(yùn)作成本,對(duì)提高物流經(jīng)濟(jì)效益,實(shí)現(xiàn)物流科學(xué)化起著重要作用。其任務(wù)是根據(jù)顧客的需求情況和配送中心的條件,設(shè)計(jì)運(yùn)輸工具組合、線路組合和時(shí)間組合,確定選派車輛及行駛路線,從而實(shí)現(xiàn)運(yùn)作過程的最優(yōu)化和經(jīng)濟(jì)效益的最大化。目前,利用啟發(fā)式算法如微粒群、遺傳、蟻群、仿真退火等能較好地求解VRP。其中,微粒群算法也稱為粒子群優(yōu)化(particleswarmoptimization,PSO)算法,其具有并行處理特征,且魯棒性好、易于實(shí)現(xiàn),能以較大的概率找到優(yōu)化問題的全局最優(yōu)解等優(yōu)點(diǎn),引起了廣大學(xué)者的廣泛關(guān)注。但是由于PSO算法的尋優(yōu)能力主要來自于粒子之間的相互作用和相互影響,粒子本身沒有變異機(jī)制,因而PSO算法容易陷入局部最優(yōu)。近年來,人們對(duì)粒子群算法作了許多改進(jìn)。文獻(xiàn)在PSO中引入混沌這種可以跳出局部極值的技術(shù),利用混沌具有的隨機(jī)性、遍歷性和對(duì)初始條件的極度敏感性,在一定范圍內(nèi)能夠按其資深的規(guī)律不重復(fù)地遍歷所有狀態(tài)等特點(diǎn),對(duì)PSO每次找到的全局極值進(jìn)行混沌搜索,使算法避免陷入局部最優(yōu)解,最大可能地找到全局最優(yōu)解。文獻(xiàn)提出了隨著迭代的進(jìn)行線性減小w慣性權(quán)重的策略。由PSO粒子的搜索特征不難發(fā)現(xiàn),線性減小不能滿足開始搜索速度快些,搜索后期速度慢些的要求;而且PSO在實(shí)際搜索過程中是非線性的且是高度復(fù)雜的,致使算法在求解復(fù)雜問題的后期易發(fā)生早熟收斂。本文在文獻(xiàn)的基礎(chǔ)上根據(jù)粒子群算法進(jìn)化的特點(diǎn),結(jié)合邏輯斯特函數(shù)提出一種新的粒子群優(yōu)化算法。1vrp數(shù)學(xué)模型的建立VRP的數(shù)學(xué)描述如下:已知k個(gè)客戶和1個(gè)配送中心,第i個(gè)客戶的需求為qi,從配送中心派出載重為Q的m輛車為客戶服務(wù),最后回到配送中心。已知qi≤Q,求一條最佳的服務(wù)路線(運(yùn)作費(fèi)用少)。dij表示從點(diǎn)i到點(diǎn)j的運(yùn)作成本(如時(shí)間、路程、花費(fèi)等)。配送中心編號(hào)為0,每個(gè)客戶均以點(diǎn)i(i=1,2,…,k)來表示,各輛車的編號(hào)為s(s=1,2,…,m)。定義變量為xijs={1車s從點(diǎn)i行駛到點(diǎn)j0否則(1)xijs={1車s從點(diǎn)i行駛到點(diǎn)j0否則(1)yis={1客戶i的任務(wù)由車s來服務(wù)0否則(2)yis={1客戶i的任務(wù)由車s來服務(wù)0否則(2)建立模型的目標(biāo)就是使得總運(yùn)作費(fèi)用最少。而運(yùn)作費(fèi)用與車輛的行駛路徑成正比,行駛路徑越短,車輛的耗油量就越少,司機(jī)的工作時(shí)間也越少,從而總運(yùn)作費(fèi)用就越少。因此建立以總行車路徑最短為目標(biāo)函數(shù)的VRP數(shù)學(xué)模型為minΖ=k∑i=0k∑j=0m∑s=1dijxijs(3)minZ=∑i=0k∑j=0k∑s=1mdijxijs(3)k∑i=0qiyis≤Qs=1,2,?,m(4)m∑s=1yis=1i=1,2,?,k(5)k∑i=0xijs=yisj=1,2,?,k;s=1,2,…,m(6)k∑j=0xijs=yisi=1,2,?,k;s=1,2,…,m(7)上述模型中:式(4)為車輛最大載重量約束,即每輛車的實(shí)際裝載量不能超過車輛的最大載重量;式(5)保證了每個(gè)客戶的任務(wù)僅由一輛車完成;式(6)和(7)表示車s在進(jìn)行服務(wù)時(shí),對(duì)每個(gè)客戶服務(wù)且僅服務(wù)一次,即車s確定服務(wù)范圍后,安排路線時(shí)確保經(jīng)過且僅經(jīng)過它服務(wù)范圍內(nèi)的每個(gè)客戶點(diǎn)一次。從模型中可以看出,該優(yōu)化問題中含有不等式約束,不利于啟發(fā)式搜索求解,可以通過在目標(biāo)函數(shù)中增加懲罰項(xiàng)來處理。修改后的目標(biāo)函數(shù)為minΖ=k∑i=0k∑j=0m∑s=1dijxijs+R?m∑s=1max(k∑i=1qiyis-Q)(8)式(8)中懲罰系數(shù)R為一個(gè)很大的正數(shù)(本文取1000),整個(gè)第二項(xiàng)是對(duì)車輛過載的懲罰項(xiàng),這樣賦予不可行解很大的適應(yīng)值,使搜索過程收斂于可行解。2全局最優(yōu)解pgPSO算法首先初始化一群隨機(jī)粒子,然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索,即通過迭代找到最優(yōu)解。假設(shè)d維搜索空間中的第i個(gè)粒子的位置和速度分別為xi(xi,1,xi,2,…,xi,d)和vi(vi,1,vi,2,…,vi,d),在每一次迭代中,粒子通過跟蹤兩個(gè)最優(yōu)解來更新自己。第一個(gè)就是粒子本身所找到的最優(yōu)解,即個(gè)體極值pi=(pi,1,pi,2,…,pi,d);另一種是整個(gè)種群目前找到的最優(yōu)解,即全局最優(yōu)解pg=(pg,1,pg,2,…,pg,d)。在找到這兩個(gè)最優(yōu)值時(shí),粒子根據(jù)如下公式來更新自己的速度和新的位置:vi,j(t+1)=wvi,j(t)+c1r1+c2r2(9)xi,j(t+1)=xi,j(t)+vi,j(t+1)j=1,2,…,d(10)3改進(jìn)的粒子群算法3.1改進(jìn)算法的成像混沌是存在于非線性系統(tǒng)中的一種較為普遍的現(xiàn)象,是由確定性方程得到的具有隨機(jī)性的運(yùn)動(dòng)狀態(tài)。在一定范圍內(nèi)混沌變量的變化具有隨機(jī)性、遍歷性和規(guī)律性,利用混沌變量的這些特征優(yōu)化搜索,能使算法跳出局部最優(yōu),保持群體多樣性,改善算法的全局搜優(yōu)性能。一個(gè)典型的混沌映射系統(tǒng)Logistic方程是:yn+1=4yn(1-yn)n=1,2,3,…(11)其中:yn為混沌變量,yn∈。標(biāo)準(zhǔn)PSO算法的整個(gè)迭代過程中,粒子朝全局歷史最優(yōu)解方向飛行,若遇到局部極值點(diǎn),所有粒子的速度易很快下降為零而停止飛行,導(dǎo)致算法過早收斂而陷入局部最優(yōu)點(diǎn)。判斷算法是否進(jìn)入早熟的標(biāo)準(zhǔn)為粒子的平均粒距和粒子的適應(yīng)度方差。粒子的平均粒距:D(t)=1Ν?L?Ν∑i=1√D∑j=1(pij-ˉpj)2(12)其中:L為搜索空間對(duì)角最大長(zhǎng)度;N為種群規(guī)模大小;D為解空間的維數(shù);pij表示第i個(gè)粒子的第j維坐標(biāo)適應(yīng)度值;ˉpj表示所有粒子第j維坐標(biāo)適應(yīng)度值的均值。由式(12)可知,平均粒距獨(dú)立于種群規(guī)模大小、解空間的維數(shù)以及每維搜索范圍。D(t)越小,表示種群越集中;D(t)越大,表示種群越分散。種群的適應(yīng)度方差:σ2=Ν∑i=1(fi-favgfmax)2(13)其中:fi為第i個(gè)粒子的適應(yīng)度值;favg為當(dāng)前種群的平均適應(yīng)度值;fmax為當(dāng)前粒子的最大適應(yīng)度。種群適應(yīng)度方差反映的是種群中個(gè)體的聚集程度。σ2越小,則種群中個(gè)體的聚集程度越大;反之,則聚集程度越小。隨著迭代次數(shù)的增加,種群的個(gè)體適應(yīng)度會(huì)越來越接近,因此σ2會(huì)越來越小。如果σ2?α(α為預(yù)先給定的值,本文取0.1)同時(shí)D(t)?β(β為預(yù)先給定的值,本文取2.5),認(rèn)為算法出現(xiàn)早熟收斂現(xiàn)象。在改進(jìn)算法中,當(dāng)算法陷入早熟,利用混沌的遍歷性,對(duì)粒子群最優(yōu)解pg進(jìn)行混沌優(yōu)化,方法為:將pg通過方程映射到Logistic方程的定義域上:yk1=pkg-xkminxkmax-xkmin(14)對(duì)yk1通過Logistic方程ykn+1=4ykn(1-ykn)(n=1,2,3,…)進(jìn)行T次迭代,得到混沌序列yk=(yk1,yk2,…,ykΤ)。將混沌序列通過下面的方程逆映射回原解空間:p*kg,m=xkmin+(xkmax-xkmin)ykmm=1,2,…,T(15)計(jì)算可行解序列中每個(gè)可行解矢量的適應(yīng)值,并保留適應(yīng)值最優(yōu)時(shí)對(duì)應(yīng)的可行解矢量,記做p*kg。從當(dāng)前粒子群隨機(jī)選擇一個(gè)粒子,并用p*kg的位置矢量代替選出粒子的位置矢量。3.2邏輯斯塔法乘子法邏輯石力變量法在PSO中,慣性權(quán)重因子w對(duì)算法能否收斂具有重要作用,它使粒子保持運(yùn)動(dòng)慣性,使其有擴(kuò)展搜索空間的趨勢(shì)。w值大,有利于全局搜索,收斂速度快,但不易得到精確的解;w越小,有利于局部搜索,能得到更為精確的解,但收斂的速度慢。考慮算法的速度和精度,w的變化過程應(yīng)該是在搜索的初期,快速變化以提高搜索的效率,在搜索的后期,緩慢變化以提高搜索的精度。根據(jù)這一特性,采用一種邏輯斯特函數(shù)對(duì)慣性權(quán)重因子w進(jìn)行非線性的調(diào)整,保證算法兼顧全局尋優(yōu)和局部尋優(yōu)。邏輯斯特函數(shù)又叫做s形函數(shù)或壓縮函數(shù),其一般形式為y=a+b1+e-d?x(16)邏輯斯特函數(shù)具有非線性和處處可導(dǎo)的特性,同時(shí)該函數(shù)對(duì)輸入有一個(gè)較好的增益控制,函數(shù)的值域可以由用戶根據(jù)實(shí)際需要給定。在輸入值比較小時(shí),輸出有一個(gè)較大的增益;在輸入值比較大時(shí),輸出有一個(gè)較小的增益。借鑒邏輯斯特函數(shù)的特點(diǎn),本文對(duì)慣性權(quán)重因子w采用式(1)進(jìn)行調(diào)節(jié):w(j)=wmax-(wmax-wmin)(21+e-d(j)?(iteritermax)-1)(17)其中:wmax、wmin為慣性權(quán)重最大值和最小值;iter為當(dāng)前的循環(huán)次數(shù);itermax為最大循環(huán)次數(shù);w(j)為第j個(gè)粒子的慣性權(quán)重。d(j)=c×ξ(j)ζ(j)∈(0,1)1≤j≤N(18)其中:ξ(j)為j次混沌迭代得到的混沌變量;N為粒子的個(gè)數(shù);c的大小根據(jù)具體問題的不同而采用不同的值。圖1顯示了wmax=0.9,wmin=0.4,itermax=500,c=500,粒子個(gè)數(shù)N=5,混沌初始值設(shè)計(jì)為0.01,根據(jù)式(11)構(gòu)成的混沌序列ζ(j)為(0.01,0.0396,0.152,0.52,0.99)時(shí)各粒子的慣性權(quán)重w的變化曲線。從圖1中可以看出,采用這種方法,粒子的慣性權(quán)重整體的變化趨勢(shì)是從快速到低速,同時(shí)引入混沌映射,粒子的慣性權(quán)重軌跡各不相同,從而使得各個(gè)粒子的運(yùn)動(dòng)軌跡各不相同,在兼顧全局尋優(yōu)和局部尋優(yōu)的同時(shí),還極大地?cái)U(kuò)展了解空間。3.3粒子編碼對(duì)應(yīng)的解碼針對(duì)車輛路徑問題,本文提出一種基于實(shí)數(shù)向量的編碼方式,此方法在不增加維數(shù)的前提下,將車輛和車輛中客戶的排序在編碼中表示出來。對(duì)于有k個(gè)客戶,m輛車的VRP,用k維的實(shí)數(shù)向量表示粒子的狀態(tài)。對(duì)于向量的每一維,其整數(shù)部分表示客戶所在車輛,整數(shù)部分相同的,表示在同一輛車中。小數(shù)部分表示客戶在該車輛中的配送次序。編/解碼的過程如下所示:a)隨機(jī)生成1～m+1間k個(gè)任意實(shí)數(shù)向量表示粒子的狀態(tài)。b)將k個(gè)實(shí)數(shù)向量取整數(shù)部分,整數(shù)部分相同的為一組。c)在同一組內(nèi),按照實(shí)數(shù)向量的小數(shù)部分的大小進(jìn)行排序,形成客戶的訪問順序。例如,假設(shè)八個(gè)客戶,兩輛車的VRP,采用此種編碼方式如下:客戶:12345678X:1.121.402.832.192.741.352.502.71按上述解碼方法,將x取整,整數(shù)部分相同的分在同一組,得到(1.12,1.40,1.35),(2.83,2.19,2.74,2.50,2.71)兩組;然后,在每個(gè)分組內(nèi),按照X小數(shù)部分從小到大排列,得到結(jié)果(1.12,1.35,1.40),(2.19,2.50,2.71,2.74,2.83)。將上述狀態(tài)映射成對(duì)應(yīng)的客戶,即得到這組編碼對(duì)應(yīng)的配送方案:第一輛車線路:0—1—6—2—0第二輛車線路:0—4—7—8—5—3—0此種編碼方式,粒子的維數(shù)與客戶的數(shù)目相當(dāng),解碼時(shí)只需進(jìn)行一次排序和取整運(yùn)算,當(dāng)進(jìn)行粒子狀態(tài)更新,重新調(diào)整各個(gè)粒子的狀態(tài)比較方便,對(duì)于大規(guī)模問題,可以節(jié)約計(jì)算時(shí)間。并且此種編碼方式與基本粒子群相同,可以使用基本粒子群法的已有規(guī)則,發(fā)揮粒子群算法的固有特點(diǎn)。3.4編/解碼算法b1)粒子群初始化。初始化參數(shù),設(shè)定學(xué)習(xí)因子c1和c2,最大迭代次數(shù)itermax,粒子數(shù)目N,混沌搜索迭代次數(shù)T,懲罰系數(shù)R,系數(shù)慣性權(quán)值最大和最小值wmax、wmin。隨機(jī)產(chǎn)生1～m+1間k個(gè)任意實(shí)數(shù)向量表示粒子的狀態(tài)。2)按照3.3節(jié)所提供的編/解碼方法得到對(duì)應(yīng)的配送方案。3)在0、1之間隨機(jī)產(chǎn)生一個(gè)實(shí)數(shù)作為混沌初始值,按照式(11)迭代N次。4)按照式(17)計(jì)算各個(gè)粒子的慣性權(quán)重因子w。5)根據(jù)式(8)計(jì)算粒子的適應(yīng)值,更新個(gè)體最優(yōu)值pi和全局最優(yōu)值pg。6)若滿足停止條件(通常為預(yù)設(shè)的運(yùn)算精度或迭代次數(shù)),搜索停滯,輸出結(jié)果;否則轉(zhuǎn)步驟7)。7)根據(jù)粒子的平均粒距和粒子的適應(yīng)度方差判斷算法是否進(jìn)入早熟。8)如果算法進(jìn)入早熟,對(duì)粒子群最優(yōu)解pg進(jìn)行混沌優(yōu)化;否則轉(zhuǎn)步驟9)。9)按照式(9)和(10)更新粒子的速度和位置。如果粒子位置小于1,將粒子的位置值設(shè)置為1.00;如果粒子位置大于m+1,將粒子的位置值設(shè)置為99。轉(zhuǎn)步驟4)。4實(shí)驗(yàn)結(jié)果及分析實(shí)驗(yàn)環(huán)境為:Pentium?Dual-Core3.00GHzCPU,2GBRAM,Windows7OS,MATLAB7.0編程軟件。采用文獻(xiàn)的實(shí)例進(jìn)行測(cè)試,已知八個(gè)客戶點(diǎn)和一個(gè)配送中心的配送系統(tǒng),每個(gè)客戶點(diǎn)的需求為q=(單位為t),配送中心有兩輛車進(jìn)行服務(wù),每輛車的最大載重為8噸,已知配送中心與各個(gè)客戶點(diǎn)的距離(單位為km)如表1所示(配送中心用0表示)。為了說明本文提出算法的有效性,將本文算法和文獻(xiàn)給出的基于遺傳操作的PSO算法及雙種群的遺傳算法(GA)分別用于求解該問題,已知最優(yōu)解為67.5(km),最優(yōu)解線路為:1號(hào)車輛:0—4—7—6—02號(hào)車輛:0—1—3—5—8—2—0文獻(xiàn)對(duì)該問題用標(biāo)準(zhǔn)GA(粒子數(shù)N=60,交叉概率Pc=0.8,變異概率Pe=0.05)和雙種群GA(兩個(gè)群的粒子數(shù)都為N=30,交叉概率P1c=0.7、P2c=0.8,變異概率P1e=0.05、P2e=0.1)分別進(jìn)行20次實(shí)驗(yàn),每次迭代次數(shù)均50。本文采用的算法(粒子數(shù)N=60,wmax=0.9,wmin=0.