粒子群優(yōu)化算法車(chē)輛路徑問(wèn)題.doc

《粒子群優(yōu)化算法車(chē)輛路徑問(wèn)題.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

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

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

3、子群，將初始的適應(yīng)值作為每個(gè)粒子的個(gè)體最優(yōu)解，并尋找子群內(nèi)的最優(yōu)解以及全局的最優(yōu)解。重復(fù)以上步驟，直到滿(mǎn)足終止條件。本題的最短路徑由計(jì)算可知為。關(guān)鍵字：粒子群算法、車(chē)輛路徑、速度一、問(wèn)題的重述一個(gè)中心倉(cāng)庫(kù)序號(hào)為0，7個(gè)需求點(diǎn)序號(hào)為1~7，其位置坐標(biāo)見(jiàn)表1，中心有3輛車(chē)，容量均為1，由這三輛車(chē)向7個(gè)需求點(diǎn)配送貨物，出發(fā)點(diǎn)和收車(chē)點(diǎn)都是中心倉(cāng)庫(kù)。求滿(mǎn)足需求的距離最小的車(chē)輛行駛路徑。表1倉(cāng)庫(kù)中心坐標(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.890.140.280.330.21

4、0..410.57二、問(wèn)題假設(shè)1．現(xiàn)實(shí)生活中中心倉(cāng)庫(kù)以及各個(gè)需求點(diǎn)之間軍事直線連接，兩點(diǎn)之間距離即為坐標(biāo)系中兩點(diǎn)坐標(biāo)間距離。2．不因天氣及失火等原因車(chē)輛停止運(yùn)輸。3．每個(gè)需求點(diǎn)由一輛車(chē)供應(yīng)貨物。三、符號(hào)說(shuō)明配送貨物車(chē)輛數(shù)需求點(diǎn)個(gè)數(shù)貨物需求量配送貨物車(chē)輛的容量從點(diǎn)i到j(luò)的距離需求點(diǎn)i由k車(chē)配送車(chē)k從i行駛到j(luò)一、問(wèn)題分析4.1算法分析車(chē)輛路徑問(wèn)題（VRP）可以描述為有一個(gè)中心倉(cāng)庫(kù)，擁有K輛車(chē)，容量分別為，負(fù)責(zé)向L個(gè)需求點(diǎn)配送貨物，貨物需求量為，且；表示從點(diǎn)i到j(luò)的距離。求滿(mǎn)足需求的距離最小的車(chē)輛行駛路徑。將中心倉(cāng)庫(kù)編號(hào)為0，需求點(diǎn)編號(hào)為1，2，…，L。數(shù)學(xué)模型為:s.t.其中，，在本題中，貨物

5、需求量，利用粒子群優(yōu)化算法，經(jīng)過(guò)初始化粒子群，將初始的適應(yīng)值作為每個(gè)粒子的個(gè)體最優(yōu)解，并尋找子群內(nèi)的最優(yōu)解以及全局的最優(yōu)解。重復(fù)以上步驟，直到滿(mǎn)足終止條件。4.2舉例具體演算分析　例如,設(shè)VRP問(wèn)題中發(fā)貨點(diǎn)任務(wù)數(shù)為7,車(chē)輛數(shù)為3,若某粒子的位置向量X為:發(fā)貨點(diǎn)任務(wù)號(hào):1234567　　　　Xv:1222233　　　　Xr:1431221則該粒子對(duì)應(yīng)解路徑為:　　車(chē)1:0→1→0　　車(chē)2:0→4→5→3→2→0　　車(chē)3:0→7→6→0粒子速度向量V與之對(duì)應(yīng)表示為Vv和Vr該表示方法的最大優(yōu)點(diǎn)是使每個(gè)發(fā)貨點(diǎn)都得到車(chē)輛的配送服務(wù),并限制每個(gè)發(fā)貨點(diǎn)的需求僅能由某一車(chē)輛來(lái)完成,使解的可行化過(guò)程計(jì)算大大

6、減少Z雖然該表示方法的維數(shù)較高,但由于PSO算法在多維尋優(yōu)問(wèn)題有著非常好的特性,維數(shù)的增加并未增加計(jì)算的復(fù)雜性,這一點(diǎn)在實(shí)驗(yàn)結(jié)果中可以看到一、模型的建立與求解在本題中，需要分別計(jì)算以下幾個(gè)內(nèi)容，計(jì)算需求點(diǎn)與中心倉(cāng)庫(kù)及各需求點(diǎn)間距離，利用粒子群優(yōu)化算法，求出函數(shù)的全局最優(yōu)位置和最后得到的優(yōu)化極值。5.1需求點(diǎn)與中心倉(cāng)庫(kù)及各需求點(diǎn)間距離利用直角三角形勾股定理，求斜邊長(zhǎng)度。，直角坐標(biāo)系中求A,B兩點(diǎn)之間距離距離01234567007.211142.7255.6665.4974.73313.4161417.2111037.10850.2262.58672.42218.11120.396242.723

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