车辆路径问题课件

車輛路徑問題（VehiclePathProblem）

車輛路徑問題，又稱運輸調度問題，簡記VRP&VSP,包括兩部分，其一是行車路線的設計，其二是出行時間表的安排。該問題1959年由Dantzig和Ramser提出的，是指在客戶需求位置已知的情況下，確定車輛在各個客戶間的行程路線，使得運輸路線最短或運輸成本最低，通過研究VRP可以合理使用調運工具，優化運輸路線，降低企業物流成本。第14章車輛路徑問題（VehiclePathProblem）14.1物流配送車輛優化調度的概述（IntroductionofVRPforLogisticsDistribution）14.1.1概述（Introduction）14.1.2路徑特性（TheRouteCharacteristic）14.1.3常用的基本問題（TheBasicProblems）14.1.4車輛路徑問題的求解方法（TheMethodofSolvingRouteProblem）14.2單中心非滿載送貨車輛路徑問題啟發式演算法（HeuristicMethodsforOneCenterVRPwithNon-fullyLoaded） 14.2.1禁忌搜尋法簡介（Tabu-ResearchAlgorithm）14.2.2問題描述與符號表示（TheProblemandSymbol）14.2.3求解過程（Arithmetic）第14章車輛路徑問題（VehiclePathProblem）14.3車輛調度的其他演算法簡介（SomeOtherAlgorithmsforVRP）14.3.1遺傳演算法（GeneticAlgorithm）14.3.2神經網路演算法（NeuralNetworksAlgorithm）14.1物流配送車輛優化調度的概述14.1.1概述

車輛路徑問題一般定義為：對一系列裝貨點和(或)卸貨點，組織適當的行車線路，使車輛有序地通過它們，在滿足一定的約束條件(如：貨物需求量、發送量、交發貨時間、車輛容量限制、行駛里程限制、時間限制等)下，達到一定的目標(如：路程最短、費用最少、時間儘量少、使用車輛數儘量少等)。14.1物流配送車輛優化調度的概述14.1.1概述

目前有關VRP的研究已經可以表示為：給定一個或多個中心（中心車庫）一個車輛集合和一個顧客集合，車輛和顧客各有自己的屬性，每輛車都有容量，所載的貨物不能超過它的容量。配送中心14.1物流配送車輛優化調度的概述14.1.2路徑特性

車輛路徑問題的特性比較複雜，總的來說包含四個方面的屬性：（1）地址特性包括：車場數目、需求類型、作業要求。（2）車輛特性包括：車輛數量、載重量約束、可運載品種約束、運行路線約束、工作時間約束。（3）問題的其他特性。（4）目標函數可能是總成本極小化，或者極小化最大作業成本，或者最大化準時作業。14.1物流配送車輛優化調度的概述14.1.2路徑特性

車輛路徑問題的特性導致了演算法的多樣性和複雜性。為簡化問題的求解，常常應用一些技術將問題分解或轉化成一個或幾個已經研究過的基本問題，再用相應比較成熟的基本理論和方法，以得到原滿意解。14.1物流配送車輛優化調度的概述14.1.3常用的基本問題（1）旅行商問題（2）帶容量約束的車輛路線問題（3）帶時間窗的車輛路線問題（4）收集和分發問題（5）多車型車輛路線問題（6）優先約束車輛路線問題（7）相容性約束車輛路線問題（8）隨機需求車輛路線問題14.1物流配送車輛優化調度的概述14.1.4車輛路徑問題的求解方法

由於車輛路徑問題是個NP難題，為了找到滿足約束條件的最優解，就必須檢查很大的設計空間，而設計空間又是多維的非連續空間，很難找到一個規範的搜索集來系統地搜尋整個空間，所以很難得到全局的最優解或滿意解。現代研究針對以上問題，現在已有很多方法。14.1物流配送車輛優化調度的概述14.1.4車輛路徑問題的求解方法1.數學解析法此法以動態規劃法、整數規劃法、樹狀搜尋法等方式為主來進行求解，對於配送點數較少的情形能求得一個最優解，但若求解的節點數增加，則其結果相對變差，與實際配送的情相差較大。14.1物流配送車輛優化調度的概述14.1.4車輛路徑問題的求解方法2.人機互動法提供使用者借由人機互動的方式，結合使用者過去的經驗，調整該模型的參數，以作為配送路線規劃決策的依據。14.1物流配送車輛優化調度的概述14.1.4車輛路徑問題的求解方法3.先分組再排路線法先將所有配送點分成數個群組，再分別對各個群組進行路線規劃，如掃描法，根據所有配送點的分佈，以極座標的表示方法來呈現各配送點的位置，然後任意選取一配送點為起始點，依順時針或逆時針的方向選取尚未指派的配送點，並以貨車的容量或其他條件作為限制，進行車輛配送的分組作業，再以求解旅行商問題的演算法進行最優化的操作。14.1物流配送車輛優化調度的概述14.1.4車輛路徑問題的求解方法abdcefijghlkmnopqrtsuwvxyz掃描方向D14.1物流配送車輛優化調度的概述14.1.4車輛路徑問題的求解方法4.先排線路再分組法（RoutFirst—ClusterSecond）與前一種方法相反，這種方法是先進行路線的規劃，然後再進行分割，如巨集分割法，此方法又因切割方式的差異，可分為單巨集切割法及多巨集切割法二種。14.1物流配送車輛優化調度的概述14.1.4車輛路徑問題的求解方法（1）單巨集切割法取所有配送點進行旅行商問題的求解，建立一個自原點出發，經過所有結點，最後回到原點的巡迴路線，然後以最短路徑解法對此路線進行分割，求得所需要的結果。（2）多巨集切割法與單巨集切割法相似，最大的差異在於建立巡迴路線時並不包含原點，因此在切割路線時，可以有較多的切割方式。14.1物流配送車輛優化調度的概述14.1.4車輛路徑問題的求解方法5.節省或插入法（SavingorInsertion）由於數學解析法具有先天上的限制，對於大規模求解問題的效率與結果較為不佳，因此，求得一個近似的最優解，是本論文研究的目標，為克服這個問題，許多學者提出了各種求解方法，其優點在於能夠改善以往數學方法的求解效率，但並不一定保證所求出的解是最優解。節省與插入法即為此一範疇的求解方法。14.1物流配送車輛優化調度的概述14.1.4車輛路徑問題的求解方法

（1）節省法此方法以三角不等式為基礎，一部車只一個配送點為起始條件，如此若有N個配送點即有N條路線，計算節省量，將較短的路線與原始路線交換，縮短配送距離。假設配送點i與j分別由不同的車輛來服務，如將兩個配送點由一輛車服務，即可得到一個節省值，而後依據節省值的大小決定需求點是否可以相互連接，連接的方法有連結、併入、合併等三種。14.1物流配送車輛優化調度的概述14.1.4車輛路徑問題的求解方法連結併入合併abcbbbbaaaaabcccddddee14.1物流配送車輛優化調度的概述14.1.4車輛路徑問題的求解方法

（2）插入法將節省法中節省值的觀念應用於循序路線構建上，並以距離物流中心最遠的配送點作為起始點，再以最臨近的一點作為下一個插入點的配送點，求其節省值，取值最大者以決定插入的位置並進行插入，重複進行選取與插入的步驟，直到所有配送點均被服務到為止。14.1物流配送車輛優化調度的概述14.1.4車輛路徑問題的求解方法6.改善或交換法常見的改善方法有2-opt、3-opt方法，與k-opt方法等，是先以其他方法產生初始解，再利用節點或節線交換的方式，對求出的路線解進行改善，達到更好的目標函數值。14.1物流配送車輛優化調度的概述14.1.4車輛路徑問題的求解方法7.數學規劃近似法此方法針對放鬆後的數學模式進行最優化處理。如車輛路線問題，轉換成由兩個相關子問題組成的數學規劃，其中一個為一般化配送點的指派問題，另一個則為旅行商問題，並提出一些準則用來產生路徑種子點，再利用節省值產生一個指派問題的目標函數，然後先解指派問題，再針對每輛車的旅行商問題求解。14.2單中心非滿載送貨車輛路徑問題啟發式演算法14.2.1禁忌搜尋法簡介

禁忌搜尋法的概念首先由Glover於1977年提出，當時是將其應用於整數規劃的求解問題上，直到1989、1990年Glover才將禁忌搜尋法的結構與方法完整提出。其主要內容是使用移步的方式，運用具有彈性的記憶結構，以迭代的方式從目前的解出發展開對鄰近解的搜尋，而其記憶結構可分為長期記憶結構和短期記憶結構兩種。記憶的目的在於使尋求解的過程能越過局部最優解而找到更好的解。14.2單中心非滿載送貨車輛路徑問題啟發式演算法14.2.1禁忌搜尋法簡介

禁忌搜尋法的演算過程是先在問題中找到一組可行解，再依使用者所做的定義找出所有的鄰近解N()，在N()中找出最優解，若F()優於F()時，即將現在解移步至，為了避免尋求解的範圍落入某一區域中，禁忌搜尋法允許當F()未能優於F()時，仍然接受為新的現在解，使尋解的過程能跳離某一區域，找到更佳的解。14.2單中心非滿載送貨車輛路徑問題啟發式演算法14.2.1禁忌搜尋法簡介1.初始解如果沒有特殊限制條件，可以任選一可行解作為該問題的初始解，以本論文研究的車輛路線問題為例，初始解的限制條件為“車輛的載重”，因此必須考慮滿足所有配送點及車輛載重的限制，並建立適當的初始解。禁忌搜尋法的主要步驟14.2單中心非滿載送貨車輛路徑問題啟發式演算法14.2.1禁忌搜尋法簡介2.移步每次迭代的過程中，在所有合法的鄰近解裏，選擇其一進行變動的行為，稱之為移步。禁忌搜尋法的主要步驟14.2單中心非滿載送貨車輛路徑問題啟發式演算法14.2.1禁忌搜尋法簡介3.禁忌名單為了避免重複選取已經選取過的解，禁忌搜尋法會將最近幾次移步的屬性記錄在禁忌名單中，作為禁忌限制的參考指標，來防止重複搜尋的現象。禁忌名單的長度會影響到求解尋優過程的結果，當禁忌名單長度太短時，搜尋過程可能會落入局部解的限制；若禁忌名單太長，除了要花費較多的時間檢查移步是否被禁忌外，還可能導致搜尋過程遠離最優解位置的可能性。禁忌搜尋法的主要步驟14.2單中心非滿載送貨車輛路徑問題啟發式演算法14.2.1禁忌搜尋法簡介4.免禁準則當一個移步為禁忌，但是若此一移步被允許，可以使得目前所搜尋到的目標函數值得以改善時，則接受此一移步，免禁準則的目的就是用來釋放原本禁忌的狀態，在求解過程中能逃脫局部最優解的局限。禁忌搜尋法的主要步驟14.2單中心非滿載送貨車輛路徑問題啟發式演算法14.2.1禁忌搜尋法簡介5.停止準則停止準則是整個演算過程結束的條件，通常使用以下四種準則：（1）預設最大迭代次數；（2）目標函數值持續未改善的次數；（3）預設允許CPU最長的執行時間；（4）預設可接受的目標函數值。禁忌搜尋法的主要步驟14.2單中心非滿載送貨車輛路徑問題啟發式演算法14.2.2問題描述與符號表示

所求單中心非滿載送貨車輛路徑問題具有以下特點：（1）物流配送中心的位置為已知並且唯一；（2）需求點的位置及需求量為已知；（3）需求點與需求點間的路線與距離為已知且確定；（4）貨車經過需求點時只有卸貨而無裝貨，貨物配送完畢以空車返回配送中心；（5）物流中心只有一種貨車。所求的目標函數為：使貨車配送路線的總成本最小，在本文中體現為配送路線距離最短。14.2單中心非滿載送貨車輛路徑問題啟發式演算法14.2.2問題描述與符號表示問題中的參數做以下定義：

V：需求點集合O：物流配送中心

K：貨車的容量

qi：配送點i的需求量

cij：配送點i到配送點j的距離

1如果配送點i由貨車k服務時；yik=0其他情形時

1如果貨車k經由配送點i到配送點j時，且i≠jxijk=0其他情形時14.2單中心非滿載送貨車輛路徑問題啟發式演算法14.2.2問題描述與符號表示數學模型建立及公式所代表的意義如下：求路線距離總和的最小值。貨車經過每一條路線的總載貨容量不能超過貨車的容量。上式是物流配送中心的總車輛數，下式是各需求點只能由一部貨車服務的限制。流量守恆限制。貨車k的配送點指派。貨車k的路線指派。流量守恆限制。14.2單中心非滿載送貨車輛路徑問題啟發式演算法14.2.3求解過程

本文擬採用“先分組再排線路”的二階段求解方法，進行配送線路的安排，也就是先將所有的配送點進行分組，然後再對每一組集中的配送點做最優化路線的處理，換句話說，是將車輛路線問題（VRP）轉換成多個旅行商問題（TSP）進行求解。14.2單中心非滿載送貨車輛路徑問題啟發式演算法14.2.3求解過程

為了使每輛貨車所負責的配送點儘量相鄰，滿足物流業者單一區域配送上的需要，本論文以掃描法為基礎，修改其演算方法進行初始解的構造，此方法可以達到先分組的目標，而且此方法在選擇配送點進行求解時，可以將鄰近的點選入同一群組中，滿足初始解的基本需求。而在車輛路線規劃方面，在構造初始解路線時，加入“車輛載重限制”的條件，使得初始解的每一群組均能滿足此限制。1.構造初始解14.2單中心非滿載送貨車輛路徑問題啟發式演算法14.2.3求解過程

（1）配送點數據的輸入進行禁忌搜索之前，必須先建立配送點的相關數據，而配送點數據應包括座標及配送量。為配送點設計數據表。2.禁忌搜索字段名稱數據類型描述備註ID整型（Integer）配送點的編號設為主鍵X_position雙精度型（Double）配送點的X座標Y_position雙精度型（Double）配送點的Y座標Weight雙精度型（Double）配送點的配送量14.2單中心非滿載送貨車輛路徑問題啟發式演算法14.2.3求解過程

（2）設定參數禁忌名單（TabuList）的長度：文獻中大多建議使用7作為禁忌名單的長度。最大重複搜尋次數：本文假設其值為100，意即重複搜尋100次。2.禁忌搜索14.2單中心非滿載送貨車輛路徑問題啟發式演算法14.2.3求解過程

（3）目標函數與移步在計算目標函數值之前，首先建立一個對稱矩陣，目的是為了存放兩兩配送點之間的距離。2.禁忌搜索

配送點配送點01230058615097289033673014.2單中心非滿載送貨車輛路徑問題啟發式演算法14.2.3求解過程

（3）目標函數與移步計算目標函數值時，使用點對交換（PairSwap）的節點交換法作為禁忌搜尋法的移步方法，來達到展開鄰近解搜尋的目的。PairSwap有兩種可能的形式，第一種可能的形式是針對彼此相鄰的兩個配送點；第二種形式是任選配送路線中的二點進行交換。由以上這種節點交換方法來判斷是否有出現較佳的解，來獲得較好的目標函數值。2.禁忌搜索14.2單中心非滿載送貨車輛路徑問題啟發式演算法14.2.3求解過程

本文建立初始解所使用的掃描法，對車輛路線問題而言是一種先分組的方法，因此被納入組中的配送點就無法在不同的路線中跳動，得到較差的初始解結果。此處使用兩種不同路線中交換節點的方法來彌補這個缺陷，期望能在配送點儘量相鄰的條件下，找出更好的路線規劃。3.最優解的改善14.2單中心非滿載送貨車輛路徑問題啟發式演算法14.2.3求解過程

方法一：將兩不同路線中，相同順序的連續兩個配送點進行交換。如果交換後的總成本較原始路線為佳，則進行路線的變動。3.最優解的改善交換後交換前14.2單中心非滿載送貨車輛路徑問題啟發式演算法14.2.3求解過程

方法二：將二路線中同一順序的配送點互換後，其後的配送點全部一起交換，因為第一點交換與原路線沒有差異，所以使用此法從第二點開始交換。如果交換後的總成本較原始路線為佳，則進行路線的變動。3.最優解的改善交換後交換前14.2單中心非滿載送貨車輛路徑問題啟發式演算法14.2.3求解過程整個求解的完整流程3.最優解的改善是否計算各配送點的極座標角度值選取尚未成為第一條路線第一個配送點的點以第一個配送點為起點，計算其他配送點的相對角度值，並由大到小排列依排列順序將配送點選入路線中將規劃的路線選入TS，進行最優化處理結束找到總成本最小的解針對總成本最小的路線進行改善開啟一條新路線一路線中所有配送點的總容量是否大於一輛車的容量所有配送點是否都曾成為第一條路線的第一個配送點所有配送點是否都已納入路線規劃中開始是是否否14.2單中心非滿載送貨車輛路徑問題啟發式演算法14.2.3求解過程

由上頁流程圖可知，本演算法是將車輛路徑問題轉換成多個旅行商問題進行求解。首先用改進後的掃描法建立初始解，即根據車輛載重限制對所有配送點建立多輛車的配送路徑，然後對每輛車的配送路徑用旅行商演算法進行求解（即上頁圖所示的“將規劃的路線選入TS，進行最優化處理”一步），最後找到總成本最小的解並利用前文所述之方法進行解的改善。3.最優解的改善14.3車輛調度的其他演算法簡介14.3.1遺傳演算法

遺傳演算法主要由選擇、交叉和變異三個算子組成，分別模仿自然界進化過程中的自然選擇和群體遺傳過程中發生的交配和突變等現象。採用遺傳演算法求解車輛優化調度問題時，一般按照以下步驟進行：14.3車輛調度的其他演算法簡介14.3.1遺傳演算法

採用自然數對可行線路進行編碼，如長度為l＋m的染色體可寫為：(0,i11,i12,…,i1s,0,i21,…,i2t,0,…,0,im1,…,imn)。其中，ikj表示第ikj項任務，這樣的染色體結構可理解為車輛從車場0出發，經過任務i11，i12，…，i1s後回到車場，形成子路徑1；如此反復，直到所有的m項任務全部被完成為止。在子路徑1內交換i11

和i12的位置表示行走路徑的改變，也使函數目標改變，這樣，下麵的遺傳疊代可使函數目標最小，也即趨向於最佳或較佳的路徑。1.確定染色體的編碼和初始群體14.3車輛調度的其他演算法簡介14.3.1遺傳演算法

初始群體的產生採用隨機方法，隨機產生l個城市的全排列，根據任務的源點和匯點將0標準插入排列中，形成一條初始染色體。如此反復，直到滿足群體數，群體數一般大於20個。1.確定染色體的編碼和初始群體14.3車輛調度的其他演算法簡介14.3.1遺傳演算法2.確定適應度函數

車輛調度的優化目標有多種多樣，常見的目標有總運費最小，總運輸時間最短，空載車總運行時間最小，完成任務所需的車輛最小總運輸時間最短，空載車總運行時間最小，完成任務所需的車輛最小等，以總運費最小為例，其目標函數為：式中，Cij為從源點i到匯點j每輛車的單位費用，Xij為每班從源點i到匯點j的滿載車的數量。m,n為源點和匯點的數目。14.3車輛調度的其他演算法簡介14.3.1遺傳演算法

為保證車輛調度優化的正確性，約束往往必不可少，常見的約束有匯點處理能力約束，非負約束，車流連續性約束。一般採用懲罰的方法來處理約束，如果一個染色體對應的解違反了某個約束，根據其違反的程度給予一定的懲罰，使其具有較小的適應度值。這樣在不損失群體數目的基礎上，隨著迭代的進行，使不可行解的數目在群體中所占比例越來越小，可行解的數目則逐漸增加，並趨向最優解。3.處理約束14.3車輛調度的其他演算法簡介14.3.1遺傳演算法

經典的遺傳算子包括複製、交叉、變異。複製算子的目的是保留優良個體，避免基因缺失，提高全局收斂性和效率。目前常用的複製算子有放回式隨機複製又稱輪盤賭複製，無放回式隨機複製等十幾種。4.遺傳算子14.3車輛調度的其他演算法簡介14.3.1遺傳演算法

交叉算子的作用是組合出新的個體，在染色體空間進行有效搜索，同時降低對有效模式的破壞概率。染色體採用自然數編碼時，交叉算子一般有部分匹配交叉，順序交叉，圈交叉等。染色體採用二進位編碼時，常採用的交叉算子有單點交叉，雙點交叉等。交叉算子中採用的交叉率一般在0.75~0.95之間。4.遺傳算子14.3車輛調度的其他演算法簡介14.3.1遺傳演算法

變異算子是為了克服基因缺失和不成熟收斂。目前常用的變異算子有常規位變異，均勻變異和非均勻變異等。變異算子的變異率一般為0.005～0.01。除了上述的經典遺傳算子外，人們又研究了其他一些算子，稱為高級算子，如顯性算子、倒位算子、分離和易位算子、遷移算子等。4.遺傳算子14.3車輛調度的其他演算法簡介14.3.1遺傳演算法

通過上述的遺傳操作，產生性能最優的染色體串，根據初始的編碼規定將該串解碼成最優調度方案。實用中，人們往往將遺傳演算法與其他方法如啟發式方法和模擬退火演算法雜合，以及將調度專家經驗融入模型和遺傳操作中，以提高求解的效果。5.確定調度方案14.3車輛調度的其他演算法簡介14.3.2神經網路演算法

人們經常採用Hopfield網路和自組織特徵映射神經網路來解決車輛的優化調度問題。在Hopfield網路中，系統能夠從初始狀態，經過一系列的狀態轉移而逐漸收斂於平衡狀態，此平衡狀態是局部極小點。採用神經網路來求解車輛調度問題時，一般按下述步驟進行。14.3車輛調度的其他演算法簡介14.3.2神經網路演算法

將車輛的源點、所經過的各個匯