基于ga和sa混合算法的車輛路徑問題研究

基于ga和sa混合算法的車輛路徑問題研究

dantzig等人提出了車輛路徑問題。旅行客問題是psp的一個特例（當(dāng)psp只包含一條路徑且沒有能力限制時，它將成為一個旅行社問題）。由于Garey和Johnson證明了TSP是NP-難問題,因此,VRP也是NP-難問題。VRP是一個困難的組合優(yōu)化問題,到目前為止,僅有一些相對較小規(guī)模的VRP能保證被求解到最優(yōu)。國內(nèi)外專家和學(xué)者對VRP及其求解方法進(jìn)行了大量的研究,提出了許多關(guān)于不同類型VRP的不同的求解算法。其中,Fishetti用分枝定界算法求解具有能力約束的VRP(CVRP),獲得較好的求解結(jié)果;Chao使用改進(jìn)啟發(fā)式求解了周期VRP(PVRP),并對幾個Windmill形狀和StarofDavid問題進(jìn)行測試,取得好的結(jié)果;Vigo用啟發(fā)式對不對稱能力約束的VRP進(jìn)行了求解;Gendreau用禁忌搜索求解VRP也是一種有效的方法;Ateahiru用3-opt和模擬退火結(jié)合求解VRP獲得滿意的結(jié)果,等等。其他求解VRP的方法還有遺傳算法、最小化K-樹算法等。從研究可知,分枝定界算法不適合求解大規(guī)模VRP問題;啟發(fā)式算法始終要求保證可行解;遺傳算法爬山能力差;禁忌搜索全局性差等?？傊?單純使用一種算法求解大規(guī)模VRP,一般都存在各種缺陷,難以獲得更為滿意的結(jié)果。因此,求解大規(guī)模VRP的方法必然向混合算法發(fā)展。另外,人們在求解VRP時,在聚類和排序之間存在矛盾,如果先排序后聚類(存在分解問題),即使排序和聚類兩個階段分別均得到最優(yōu)解,其最終結(jié)果也不一定是最優(yōu)解;而先聚類再排序,顯然不一定得到最優(yōu)解;既使使用改進(jìn)搜索算法,在排序過程中也必須使用某種處理方法對已聚類的元素進(jìn)行不斷改進(jìn),搜索的全局性受到很大限制。目前,國內(nèi)外關(guān)于VRP的研究很多,但其車輛數(shù)一般都是已經(jīng)確定的。本文提出一種車輛數(shù)不確定的車輛路徑問題(VehicleRoutingProblemwithUncertainVehicleNumber,UMVRP),并用遺傳算法和禁忌搜索算法相結(jié)合來求解UMVRP。1uvmrp模型的構(gòu)建1.1車輛數(shù)不確定考慮UMVRP可以概述如下:假設(shè)有n個城市,每個城市的位置坐標(biāo)和貨物需求已知,車輛的負(fù)載能力一定,但車輛數(shù)不確定。UMVRP是對車輛(每輛車一條路徑,開始和終止都在起始點(diǎn)(depot)所要訪問的城市進(jìn)行排序,使所有城市都滿足要求,且總旅行成本最小。假設(shè)每個城市被分配到某一輛車(除了depot被所有車輛訪問),訪問一個城市的一輛車也必須離開那個城市,每輛車所訪問的城市的需求總和不能超過車輛的能力。1.2車輛能力模型為了敘述方便,引入下面的符號:(1)城市集合,V={i},i=0,1,…,n,且i=0指depot。(2)車輛集合,M={k},k=1,…,m,m是一個待定的決策變量。(3)城市i的需求量,i∈V(i=0時,q0=0)。(4)城市i到城市j的距離,ci0=0,c0i=0,i∈V\{0},cii=∞,i∈V?城市間距離矩陣?C=(cij)。(5)每輛車的能力(每輛車的載重量相同),Q≥max{qi,i∈V}。xijk={1如果車輛k在訪問城市i之后立即訪問城市j0其他yik={1如果車輛k訪問城市i0其他由如上假設(shè),可建立UMVRP模型如下:minm(1)min∑i,jcij∑kxijk(2)約束:m∑k=1yik={1i=1,2??,nmi=0(3)n∑i=1qiyik≤Qk=1,2??,m(4)n∑j=1xijk=n∑j=1xjik=yik(5)i=1,?,n;k=1,2??,m∑i∈S∑j∈Sxijk≤|S|-1(6)對于所有S?{1,2??,n},k=1,2??,m?yik∈{0,1}(7a)xijk∈{0,1}(7b)i=0,?,n;j=0,?,n;k=1,?,m最少車輛數(shù)由下式?jīng)Q定:m=[JX-*3]-[JX*3]n∑i=1qi/Q[JX-*3]-[JX*3](8)其中:目標(biāo)式(1)是保證車輛數(shù)最少;式(2)是最小化旅行距離。約束式(3)保證每個城市被分配到某輛車(除了depot被所有車輛訪問);式(4)是車輛的能力約束;式(5)保證訪問一個城市的一輛車也離開那個城市;式(6)消除子回環(huán);式(7a)和(7b)是參數(shù)的取值范圍,2uvmp的混合算法2.1限制使用的因素盡管遺傳算法能夠勝任任意函數(shù)和高維空間的組合優(yōu)化問題,但是對于像優(yōu)化大規(guī)模神經(jīng)元網(wǎng)絡(luò)的權(quán)系數(shù),優(yōu)化網(wǎng)絡(luò)的結(jié)構(gòu)等超大規(guī)模的優(yōu)化問題,遺傳算法的應(yīng)用就受到了限制。究其原因,主要在于遺傳算法在進(jìn)化搜索過程中,每代總是要維持一個較大的種群規(guī)模,限制了遺傳算法的使用。遺傳算法的另一個不足之處是“早熟”。造成這種成熟前收斂的原因,一方面是遺傳算法中最重要的遺傳算子——交叉算子使群體中的染色體具有局部相似性,從而使搜索停滯不前;另一方面是變異概率又太小,爬山能力差,以至于不能使搜索轉(zhuǎn)向解空間的其他區(qū)域進(jìn)行搜索。2.2啟發(fā)式算法獲得初始解文獻(xiàn)闡述了禁忌搜索算法的原理和應(yīng)用。禁忌搜索算法的搜索速度比遺傳算法的搜索速度快,但是其對于初始解具有較強(qiáng)的依賴性。一個較好的初始解可使禁忌搜索算法在解空間中搜索到更好的解,而一個較差的初始解則會降低禁忌搜索算法的收斂速度。為此,人們往往使用啟發(fā)式算法來獲得一個較好的初始解,提高禁忌搜索算法的性能。禁忌搜索算法的另一不足是在搜索過程中初始解只能有一個,在每代也只是把一個解移動到另一個解,即為點(diǎn)-點(diǎn)操作,而不像遺傳算法那樣每代都是對多個解進(jìn)行操作,即為種群-種群的操作。2.3城市染色體的基于自然數(shù)編碼的新能源檢測在求解VRP時,一般使用先聚類后排序(CFRS)或先排序后聚類(RFCS)方法。CFRS最早是由G.gillettL.Miller使用兩階段啟發(fā)式算法求解VRP時使用的,它是先用啟發(fā)式把節(jié)點(diǎn)分為若干條路徑,再對各條路徑中的點(diǎn)排序。RFCS產(chǎn)生于CFRS之后,Besley首先給出了基本RFCS的思想,它是先對所有節(jié)點(diǎn)進(jìn)行TSP排序,然后對此大的路徑進(jìn)行分割聚類,其中的聚類過程描述為分割問題,處理分割問題的典型方法是最小化分割時的附加成本(具有能力約束)。如前所述,這兩種方法都存在一定的不足之處。針對上述各種方法的不足,本文提出用混合遺傳算法來求解UMVRP,如圖1所示。對遺傳算法主要要素的構(gòu)造包括:(1)染色體編碼方式。本文中,令每個染色體對應(yīng)一個解,采用自然數(shù)編碼,設(shè)計染色體V={vi}(i=1,…,n)。其中,vi表示染色體中的基因,對應(yīng)于第i個城市的城市號(用自然數(shù)編號),這種編碼方式保證了式(3)、(5)和(6)的可行性。(2)適應(yīng)值函數(shù)的確定。目標(biāo)函數(shù):f=∑i,jcij∑kxijk(9)定義染色體對式(4)的可行距離ID,用以表征染色體關(guān)于式(4)的非可行程度:ΙD=max{0,Q′m-Q}(10)式中:Qm為分配給車輛m的總負(fù)荷;Q為車輛的能力。設(shè)計適應(yīng)值函數(shù)為fitness=Cmax-f-αmax{0,Q′m-Q}(11)式中:Cmax為足夠大的常數(shù);α為式(4)的不可行懲罰系數(shù),這里,α為較大的正整數(shù)。適值函數(shù)對于式(4)的懲罰處理,只能使新一代染色體的非可行程度降低,而不能杜絕非可行染色體的存在,本算法并不局限在可行域中尋優(yōu),以圖擴(kuò)大尋優(yōu)的途徑。(3)選擇策略。本算法采用滾輪盤的方式進(jìn)行復(fù)制,復(fù)制的選擇概率由下式獲得:Ρg=fitnessg/G∑α=1fitnessα(12)式中,g=1,2,…,G,G為種群規(guī)模。(4)遺傳算子。采用CycleCrossover(CX)算子,采用禁忌搜索作為變異算子。詳細(xì)步驟如下:(1)初始化。設(shè)置最大代數(shù)max-gen、種群模型G、交叉概率pc和變異概率pm。計算所需車輛的最小值m,代數(shù)gen=0。(2)初始解。隨機(jī)產(chǎn)生n個城市的G個排列作為初始染色體,其順序聚類為初始解,初始解不一定可行。(3)選擇。按滾輪盤方式選擇出G個染色體,如果這些染色體不包括最好解best-fit,則用best-fit代替當(dāng)前代最差的染色體。(4)交叉。對每個染色體,按照交叉概率pc,判斷是否使它參加交叉(隨機(jī)產(chǎn)生一概率p,如果p≤pc,則此染色體參加交叉),如果此染色體參加交叉,則采用CX方式進(jìn)行交叉。(5)變異。對每個染色體,按照變異概率pm,判斷是否對它進(jìn)行變異(隨機(jī)產(chǎn)生一概率p,如果p≤pm,則對此染色體進(jìn)行),禁忌搜索作為變異操作算子。(6)最好解。按照順序聚類成m條路徑后,計算解的目標(biāo)函數(shù)值,并識別解的可行性,然后計算解的適應(yīng)值。記錄至當(dāng)前最好的可行解best-fit。gen加1,如果代數(shù)gen小于max-gen,則轉(zhuǎn)(3)。(7)最終解。如果已獲得可行解,退出;否則,gen=0,m=m+1,轉(zhuǎn)(3)。2.4禁忌搜索步驟若用禁忌搜索方法求解VRP時,一個解是m條路徑R1,…,Rm的集合S(對應(yīng)染色體{vi}(i=1,2,…,n)),其中路徑Rr={v0,vr1,vr2,…,vrn,v0},v0為VER中的depot,{vi}中每個元素屬于且僅屬于一條路徑。這些路徑可能是關(guān)于能力約束可行或不可行的。寫:vi∈Rr,如果vi是Rr的一個元素;(vi,vj)∈Rr,如果vi和vj是Rr的2個連續(xù)的元素。對于任何解x,搜索決定于一個參數(shù)向量:Ρ=(x0,W,Λ,θ,Τ,nmax)其中:x0為初始解;W為允許移動的元素的集合,這里包括所有的城市;Λ為移動的構(gòu)成方式,這里是W中的兩元素交換;θ為禁忌表的長度;T為最大循環(huán)次數(shù);nmax為適應(yīng)值函數(shù)沒有任何改進(jìn)時,允許循環(huán)的最大次數(shù)。禁忌搜索步驟:(1)初始化。設(shè)置循環(huán)次數(shù)t=1,沒有移動被禁忌。最好解x*=x0,最好解的目標(biāo)值f(x*),適應(yīng)值函數(shù)fitness(x*)=Cmax-f(x*)-αmax{0,Q′m-Q}(2)評價所有的候選移動?？紤]所有城市vi和vj(i,j∈W)的兩元素交換,從中找到最好的移動,產(chǎn)生的新解為x′,解的適應(yīng)值函數(shù)為fitness(x′)。(3)禁忌判斷。判斷是禁忌移動否,是轉(zhuǎn)(4);否則轉(zhuǎn)(5)。(4)改進(jìn)。判斷fitness(x′)>fitness(x*),成立,則fitness(x*)=fitness(x′),x*=x′,轉(zhuǎn)(5);否則,轉(zhuǎn)(2)。(5)修正。若城市vi和vj(i,j∈W)已做過交換,則直到循環(huán)t+θ之前禁止元素vj和vi(i,j∈W)交換,θ是一個整數(shù)。t=t+1,修正x*,f(x*)和fitness(x*)。(6)終止檢查。如果t>T或fitness(x*)在最后nmax個循環(huán)中沒有增加,則終止禁忌搜索;否則,轉(zhuǎn)(1)。3車輛損傷的檢測為了測試算法的有效性,分別采用文獻(xiàn)的5個典型問題進(jìn)行了測試,并與目前已知的最好結(jié)果進(jìn)行了比較。算法用C語言編程,在PC586兼容機(jī)上運(yùn)行,由于