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