資源描述：
《物流車輛路徑算法的優(yōu)化與設(shè)計(jì)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、物流車輛路徑算法的優(yōu)化與設(shè)計(jì)【摘要】：隨著物流業(yè)向全球化、信息化及一體化發(fā)展，配送在整個(gè)物流系統(tǒng)中的作用變得越來(lái)越重要。運(yùn)輸系統(tǒng)是配送系統(tǒng)中最重要的一個(gè)子系統(tǒng)，運(yùn)輸費(fèi)用占整體物流費(fèi)用的50％左右，所以降低物流成本首先要從降低物流配送的運(yùn)輸成本開(kāi)始。一個(gè)車輛集合和一個(gè)顧客集合，車輛和顧客各有自己的屬性，每輛車都有容量，所裝載貨物不能超過(guò)它的容量。起初車輛都在中心點(diǎn)，顧客在空間任意分布，車把貨物從車庫(kù)運(yùn)送到每一個(gè)顧客（或從每個(gè)顧客處把貨物運(yùn)到車庫(kù)），要求滿足顧客的需求，車輛最后返回車庫(kù)，每個(gè)顧客只能被服務(wù)一次，怎樣才能使
2、運(yùn)輸費(fèi)用最小。而顧客的需求或已知、或隨機(jī)、或以時(shí)間規(guī)律變化，這正是本文要研究的課題?！娟P(guān)鍵詞】：物流配送；路徑；車輛路徑問(wèn)題(VRP)；MATLAB1??????????????????????前言1.1?????課題研究背景運(yùn)輸線路是否合理直接影響到配送速度、成本和效益，特別是多用戶配送線路的確定是一項(xiàng)復(fù)雜的系統(tǒng)工程。選取恰當(dāng)?shù)能囕v路徑，可以加快對(duì)客戶需求的響應(yīng)速度，提高服務(wù)質(zhì)量，增強(qiáng)客戶對(duì)物流環(huán)節(jié)的滿意度，降低服務(wù)商運(yùn)作成本。因此，自從1959年Danting和Ramser提出車輛路徑問(wèn)題(VehicleRout
3、ingProblem，VRP)以來(lái)，VRP便成為近年來(lái)物流領(lǐng)域中的研究熱點(diǎn)。VRP一般定義為：對(duì)一系列發(fā)貨點(diǎn)和／或收貨點(diǎn)，組織適當(dāng)?shù)男熊嚶肪€，使車輛有序地通過(guò)它們，在滿足一定的約束條件(如貨物需求量、發(fā)送量、交發(fā)貨時(shí)間、車輛容量限制、行駛里程限制、時(shí)間限制等)下，達(dá)到一定的目標(biāo)(如路程最短、費(fèi)用最小、時(shí)間盡量少、使用車輛盡量少等)。本文圍繞VRP展開(kāi)了研究，共包括五章內(nèi)容。首先，本文收集國(guó)內(nèi)外關(guān)于VRP研究的文獻(xiàn)資料并進(jìn)行整理、分類，詳細(xì)介紹了VRP園內(nèi)外研究現(xiàn)狀，尤其對(duì)經(jīng)典VRP、有時(shí)間窗的VRP(VRPTW)、動(dòng)
4、態(tài)VRP(DVRP)、帶能力約束的VRP(CVRP)國(guó)內(nèi)外研究現(xiàn)狀分別展開(kāi)了介紹：然后通過(guò)介紹物流配送在整個(gè)物流過(guò)程中具有的重要意義及我國(guó)物流配送的現(xiàn)狀，說(shuō)明了解決VRP的必要性及現(xiàn)實(shí)意義：建立了物流配送中VRP的兩種數(shù)學(xué)模型：利用回路表示的VRP模型和利用運(yùn)輸成本表示的VRP模型；通過(guò)表格詳細(xì)討論了VRP的基本算法；最后，本文使用自然數(shù)編碼、構(gòu)造表示可行線路的染色體、類PMX交叉等方法及對(duì)適值函數(shù)加入懲罰項(xiàng)對(duì)標(biāo)準(zhǔn)遺傳算法加以改進(jìn)，并用MATLAB編程實(shí)現(xiàn)了本文提出的算法，以一個(gè)VRPTW實(shí)例分析證明了該算法的有效性
5、。1.2?????車輛路徑的概念車輛路徑問(wèn)題(VRP)一般定義為：對(duì)一系列裝貨點(diǎn)和卸貨點(diǎn)，組織適當(dāng)?shù)男熊嚲€路，使車輛有序地通過(guò)它們，在滿足一定的約束條件(如貨物需求量、發(fā)送量、交發(fā)貨時(shí)間、車輛容量限制、行駛里程限制、時(shí)間限制等)下，達(dá)到一定問(wèn)題的目標(biāo)(如路程最短、費(fèi)用最少、時(shí)間盡量少、使用車輛數(shù)盡量少等)。目前有關(guān)VRP的研究已經(jīng)可以表示（如圖1）為：給定一個(gè)或多個(gè)中心點(diǎn)（中心倉(cāng)庫(kù)，centraldepot）、一個(gè)車輛集合和一個(gè)顧客集合，車輛和顧客各有自己的屬性，每輛車都有容量，所裝載貨物不能超過(guò)它的容量。起初車輛都
6、在中心點(diǎn)，顧客在空間任意分布，車把貨物從車庫(kù)運(yùn)送到每一個(gè)顧客（或從每個(gè)顧客處把貨物運(yùn)到車庫(kù)），要求滿足顧客的需求，車輛最后返回車庫(kù)，每個(gè)顧客只能被服務(wù)一次，怎樣才能使運(yùn)輸費(fèi)用最小。而顧客的需求或已知、或隨機(jī)、或以時(shí)間規(guī)律變化。圖1?VRP示意圖2??????????????????????車輛路徑問(wèn)題算法綜述目前，求解車輛路徑問(wèn)題的方法非常多，基本上可以分為精確算法和啟發(fā)式算法2大類。2.1?????精確算法精確算法是指可求出其最優(yōu)解的算法，主要運(yùn)用線性規(guī)劃、整數(shù)規(guī)劃、非線性規(guī)劃等數(shù)學(xué)規(guī)劃技術(shù)來(lái)描述物流系統(tǒng)的數(shù)量關(guān)系
7、，以便求得最優(yōu)決策。精確算法主要有：?分枝定界法(BranchandBoundApproach)?????割平面法(CuttingPlanesApproach)?????網(wǎng)絡(luò)流算法(NetworkFlowApproach)?????動(dòng)態(tài)規(guī)劃算法(DynamicProgrammingApproach)總的說(shuō)來(lái)，精確性算法基于嚴(yán)格的數(shù)學(xué)手段，在可以求解的情況下，其解通常要優(yōu)于人工智能算法。但由于引入嚴(yán)格的數(shù)學(xué)方法，計(jì)算量一般隨問(wèn)題規(guī)模的增大呈指數(shù)增長(zhǎng)，因而無(wú)法避開(kāi)指數(shù)爆炸問(wèn)題，從而使該類算法只能有效求解中小規(guī)模的確定性V
8、RP，并且通常這些算法都是針對(duì)某一特定問(wèn)題設(shè)計(jì)的,適用能力較差,因此在實(shí)際中其應(yīng)用范圍很有限。2.2?????啟發(fā)式算法由于車輛路徑優(yōu)化問(wèn)題是NP難題，高效的精確算法存在的可能性不大(除非P=NP)，所以尋找近似算法是必要和現(xiàn)實(shí)的，為此專家主要把精力花在構(gòu)造高質(zhì)量的啟發(fā)式算法上。啟發(fā)式算法是在狀態(tài)空間中的改進(jìn)搜索算法，它對(duì)每一個(gè)搜索的位置進(jìn)行評(píng)
