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