第十四章 車輛路徑問題

第14章車輛路徑問題（VehiclePathProblem）車輛路徑問題，又稱運輸調(diào)度問題，簡記VRP&VSP,包括兩部分，其一是行車路線的設(shè)計，其二是出行時間表的安排。該問題1959年由Dantzig和Ramser提出的，是指在客戶需求位置已知的情況下，確定車輛在各個客戶間的行程路線，使得運輸路線最短或運輸成本最低，通過研究VRP可以合理使用調(diào)運工具，優(yōu)化運輸路線，降低企業(yè)物流成本。第14章車輛路徑問題（VehiclePathProblem）14.1物流配送車輛優(yōu)化調(diào)度的概述（IntroductionofVRPforLogisticsDistribution）14.1.1概述（Introduction）14.1.2路徑特性（TheRouteCharacteristic）14.1.3常用的基本問題（TheBasicProblems）14.1.4車輛路徑問題的求解方法（TheMethodofSolvingRouteProblem）14.2單中心非滿載送貨車輛路徑問題啟發(fā)式算法（HeuristicMethodsforOneCenterVRPwithNon-fullyLoaded） 14.2.1禁忌搜尋法簡介（Tabu-ResearchAlgorithm）14.2.2問題描述與符號表示（TheProblemandSymbol）14.2.3求解過程（Arithmetic）第14章車輛路徑問題（VehiclePathProblem）14.3車輛調(diào)度的其他算法簡介（SomeOtherAlgorithmsforVRP）14.3.1遺傳算法（GeneticAlgorithm）14.3.2神經(jīng)網(wǎng)絡(luò)算法（NeuralNetworksAlgorithm）14.1物流配送車輛優(yōu)化調(diào)度的概述14.1.1概述車輛路徑問題一般定義為：對一系列裝貨點和(或)卸貨點，組織適當(dāng)?shù)男熊嚲€路，使車輛有序地通過它們，在滿足一定的約束條件(如：貨物需求量、發(fā)送量、交發(fā)貨時間、車輛容量限制、行駛里程限制、時間限制等)下，達(dá)到一定的目標(biāo)(如：路程最短、費用最少、時間盡量少、使用車輛數(shù)盡量少等)。14.1物流配送車輛優(yōu)化調(diào)度的概述14.1.1概述目前有關(guān)VRP的研究已經(jīng)可以表示為：給定一個或多個中心（中心車庫）一個車輛集合和一個顧客集合，車輛和顧客各有自己的屬性，每輛車都有容量，所載的貨物不能超過它的容量。配送中心14.1物流配送車輛優(yōu)化調(diào)度的概述14.1.2路徑特性車輛路徑問題的特性比較復(fù)雜，總的來說包含四個方面的屬性：（1）地址特性包括：車場數(shù)目、需求類型、作業(yè)要求。（2）車輛特性包括：車輛數(shù)量、載重量約束、可運載品種約束、運行路線約束、工作時間約束。（3）問題的其他特性。（4）目標(biāo)函數(shù)可能是總成本極小化，或者極小化最大作業(yè)成本，或者最大化準(zhǔn)時作業(yè)。14.1物流配送車輛優(yōu)化調(diào)度的概述14.1.2路徑特性車輛路徑問題的特性導(dǎo)致了算法的多樣性和復(fù)雜性。為簡化問題的求解，常常應(yīng)用一些技術(shù)將問題分解或轉(zhuǎn)化成一個或幾個已經(jīng)研究過的基本問題，再用相應(yīng)比較成熟的基本理論和方法，以得到原滿意解。14.1物流配送車輛優(yōu)化調(diào)度的概述14.1.3常用的基本問題（1）旅行商問題（2）帶容量約束的車輛路線問題（3）帶時間窗的車輛路線問題（4）收集和分發(fā)問題（5）多車型車輛路線問題（6）優(yōu)先約束車輛路線問題（7）相容性約束車輛路線問題（8）隨機需求車輛路線問題14.1物流配送車輛優(yōu)化調(diào)度的概述14.1.4車輛路徑問題的求解方法由于車輛路徑問題是個NP難題，為了找到滿足約束條件的最優(yōu)解，就必須檢查很大的設(shè)計空間，而設(shè)計空間又是多維的非連續(xù)空間，很難找到一個規(guī)范的搜索集來系統(tǒng)地搜尋整個空間，所以很難得到全局的最優(yōu)解或滿意解。現(xiàn)代研究針對以上問題，現(xiàn)在已有很多方法。14.1物流配送車輛優(yōu)化調(diào)度的概述14.1.4車輛路徑問題的求解方法1.數(shù)學(xué)解析法此法以動態(tài)規(guī)劃法、整數(shù)規(guī)劃法、樹狀搜尋法等方式為主來進(jìn)行求解，對于配送點數(shù)較少的情形能求得一個最優(yōu)解，但若求解的節(jié)點數(shù)增加，則其結(jié)果相對變差，與實際配送的情相差較大。14.1物流配送車輛優(yōu)化調(diào)度的概述14.1.4車輛路徑問題的求解方法2.人機互動法提供使用者借由人機互動的方式，結(jié)合使用者過去的經(jīng)驗，調(diào)整該模型的參數(shù)，以作為配送路線規(guī)劃決策的依據(jù)。14.1物流配送車輛優(yōu)化調(diào)度的概述14.1.4車輛路徑問題的求解方法3.先分組再排路線法先將所有配送點分成數(shù)個群組，再分別對各個群組進(jìn)行路線規(guī)劃，如掃描法，根據(jù)所有配送點的分布，以極坐標(biāo)的表示方法來呈現(xiàn)各配送點的位置，然后任意選取一配送點為起始點，依順時針或逆時針的方向選取尚未指派的配送點，并以貨車的容量或其他條件作為限制，進(jìn)行車輛配送的分組作業(yè)，再以求解旅行商問題的算法進(jìn)行最優(yōu)化的操作。14.1物流配送車輛優(yōu)化調(diào)度的概述14.1.4車輛路徑問題的求解方法abdcefijghlkmnopqrtsuwvxyz掃描方向D14.1物流配送車輛優(yōu)化調(diào)度的概述14.1.4車輛路徑問題的求解方法4.先排線路再分組法（RoutFirst—ClusterSecond）與前一種方法相反，這種方法是先進(jìn)行路線的規(guī)劃，然后再進(jìn)行分割，如巨集分割法，此方法又因切割方式的差異，可分為單巨集切割法及多巨集切割法二種。14.1物流配送車輛優(yōu)化調(diào)度的概述14.1.4車輛路徑問題的求解方法（1）單巨集切割法取所有配送點進(jìn)行旅行商問題的求解，建立一個自原點出發(fā)，經(jīng)過所有結(jié)點，最后回到原點的巡回路線，然后以最短路徑解法對此路線進(jìn)行分割，求得所需要的結(jié)果。（2）多巨集切割法與單巨集切割法相似，最大的差異在于建立巡回路線時并不包含原點，因此在切割路線時，可以有較多的切割方式。14.1物流配送車輛優(yōu)化調(diào)度的概述14.1.4車輛路徑問題的求解方法5.節(jié)省或插入法（SavingorInsertion）由于數(shù)學(xué)解析法具有先天上的限制，對于大規(guī)模求解問題的效率與結(jié)果較為不佳，因此，求得一個近似的最優(yōu)解，是本論文研究的目標(biāo)，為克服這個問題，許多學(xué)者提出了各種求解方法，其優(yōu)點在于能夠改善以往數(shù)學(xué)方法的求解效率，但并不一定保證所求出的解是最優(yōu)解。節(jié)省與插入法即為此一范疇的求解方法。14.1物流配送車輛優(yōu)化調(diào)度的概述14.1.4車輛路徑問題的求解方法（1）節(jié)省法此方法以三角不等式為基礎(chǔ)，一部車只一個配送點為起始條件，如此若有N個配送點即有N條路線，計算節(jié)省量，將較短的路線與原始路線交換，縮短配送距離。假設(shè)配送點i與j分別由不同的車輛來服務(wù)，如將兩個配送點由一輛車服務(wù)，即可得到一個節(jié)省值，而后依據(jù)節(jié)省值的大小決定需求點是否可以相互連接，連接的方法有連結(jié)、并入、合并等三種。14.1物流配送車輛優(yōu)化調(diào)度的概述14.1.4車輛路徑問題的求解方法連結(jié)并入合并abcbbbbaaaaabcccddddee14.1物流配送車輛優(yōu)化調(diào)度的概述14.1.4車輛路徑問題的求解方法（2）插入法將節(jié)省法中節(jié)省值的觀念應(yīng)用于循序路線構(gòu)建上，并以距離物流中心最遠(yuǎn)的配送點作為起始點，再以最臨近的一點作為下一個插入點的配送點，求其節(jié)省值，取值最大者以決定插入的位置并進(jìn)行插入，重復(fù)進(jìn)行選取與插入的步驟，直到所有配送點均被服務(wù)到為止。14.1物流配送車輛優(yōu)化調(diào)度的概述14.1.4車輛路徑問題的求解方法6.改善或交換法常見的改善方法有2-opt、3-opt方法，與k-opt方法等，是先以其他方法產(chǎn)生初始解，再利用節(jié)點或節(jié)線交換的方式，對求出的路線解進(jìn)行改善，達(dá)到更好的目標(biāo)函數(shù)值。14.1物流配送車輛優(yōu)化調(diào)度的概述14.1.4車輛路徑問題的求解方法7.數(shù)學(xué)規(guī)劃近似法此方法針對放松后的數(shù)學(xué)模式進(jìn)行最優(yōu)化處理。如車輛路線問題，轉(zhuǎn)換成由兩個相關(guān)子問題組成的數(shù)學(xué)規(guī)劃，其中一個為一般化配送點的指派問題，另一個則為旅行商問題，并提出一些準(zhǔn)則用來產(chǎn)生路徑種子點，再利用節(jié)省值產(chǎn)生一個指派問題的目標(biāo)函數(shù)，然后先解指派問題，再針對每輛車的旅行商問題求解。14.2單中心非滿載送貨車輛路徑問題啟發(fā)式算法14.2.1禁忌搜尋法簡介禁忌搜尋法的概念首先由Glover于1977年提出，當(dāng)時是將其應(yīng)用于整數(shù)規(guī)劃的求解問題上，直到1989、1990年Glover才將禁忌搜尋法的結(jié)構(gòu)與方法完整提出。其主要內(nèi)容是使用移步的方式，運用具有彈性的記憶結(jié)構(gòu)，以迭代的方式從目前的解出發(fā)展開對鄰近解的搜尋，而其記憶結(jié)構(gòu)可分為長期記憶結(jié)構(gòu)和短期記憶結(jié)構(gòu)兩種。記憶的目的在于使尋求解的過程能越過局部最優(yōu)解而找到更好的解。14.2單中心非滿載送貨車輛路徑問題啟發(fā)式算法14.2.1禁忌搜尋法簡介禁忌搜尋法的演算過程是先在問題中找到一組可行解，再依使用者所做的定義找出所有的鄰近解N()，在N()中找出最優(yōu)解，若F()優(yōu)于F()時，即將現(xiàn)在解移步至，為了避免尋求解的范圍落入某一區(qū)域中，禁忌搜尋法允許當(dāng)F()未能優(yōu)于F()時，仍然接受為新的現(xiàn)在解，使尋解的過程能跳離某一區(qū)域，找到更佳的解。14.2單中心非滿載送貨車輛路徑問題啟發(fā)式算法14.2.1禁忌搜尋法簡介1.初始解如果沒有特殊限制條件，可以任選一可行解作為該問題的初始解，以本論文研究的車輛路線問題為例，初始解的限制條件為“車輛的載重”，因此必須考慮滿足所有配送點及車輛載重的限制，并建立適當(dāng)?shù)某跏冀?。禁忌搜尋法的主要步驟14.2單中心非滿載送貨車輛路徑問題啟發(fā)式算法14.2.1禁忌搜尋法簡介2.移步每次迭代的過程中，在所有合法的鄰近解里，選擇其一進(jìn)行變動的行為，稱之為移步。禁忌搜尋法的主要步驟14.2單中心非滿載送貨車輛路徑問題啟發(fā)式算法14.2.1禁忌搜尋法簡介3.禁忌名單為了避免重復(fù)選取已經(jīng)選取過的解，禁忌搜尋法會將最近幾次移步的屬性記錄在禁忌名單中，作為禁忌限制的參考指標(biāo)，來防止重復(fù)搜尋的現(xiàn)象。禁忌名單的長度會影響到求解尋優(yōu)過程的結(jié)果，當(dāng)禁忌名單長度太短時，搜尋過程可能會落入局部解的限制；若禁忌名單太長，除了要花費較多的時間檢查移步是否被禁忌外，還可能導(dǎo)致搜尋過程遠(yuǎn)離最優(yōu)解位置的可能性。禁忌搜尋法的主要步驟14.2單中心非滿載送貨車輛路徑問題啟發(fā)式算法14.2.1禁忌搜尋法簡介4.免禁準(zhǔn)則當(dāng)一個移步為禁忌，但是若此一移步被允許，可以使得目前所搜尋到的目標(biāo)函數(shù)值得以改善時，則接受此一移步，免禁準(zhǔn)則的目的就是用來釋放原本禁忌的狀態(tài)，在求解過程中能逃脫局部最優(yōu)解的局限。禁忌搜尋法的主要步驟14.2單中心非滿載送貨車輛路徑問題啟發(fā)式算法14.2.1禁忌搜尋法簡介5.停止準(zhǔn)則停止準(zhǔn)則是整個演算過程結(jié)束的條件，通常使用以下四種準(zhǔn)則：（1）預(yù)設(shè)最大迭代次數(shù)；（2）目標(biāo)函數(shù)值持續(xù)未改善的次數(shù)；（3）預(yù)設(shè)允許CPU最長的執(zhí)行時間；（4）預(yù)設(shè)可接受的目標(biāo)函數(shù)值。禁忌搜尋法的主要步驟14.2單中心非滿載送貨車輛路徑問題啟發(fā)式算法14.2.2問題描述與符號表示所求單中心非滿載送貨車輛路徑問題具有以下特點：（1）物流配送中心的位置為已知并且唯一；（2）需求點的位置及需求量為已知；（3）需求點與需求點間的路線與距離為已知且確定；（4）貨車經(jīng)過需求點時只有卸貨而無裝貨，貨物配送完畢以空車返回配送中心；（5）物流中心只有一種貨車。所求的目標(biāo)函數(shù)為：使貨車配送路線的總成本最小，在本文中體現(xiàn)為配送路線距離最短。14.2單中心非滿載送貨車輛路徑問題啟發(fā)式算法14.2.2問題描述與符號表示問題中的參數(shù)做以下定義：V：需求點集合O：物流配送中心K：貨車的容量qi：配送點i的需求量cij：配送點i到配送點j的距離1如果配送點i由貨車k服務(wù)時；yik=0其他情形時1如果貨車k經(jīng)由配送點i到配送點j時，且i≠jxijk=0其他情形時14.2單中心非滿載送貨車輛路徑問題啟發(fā)式算法14.2.2問題描述與符號表示數(shù)學(xué)模型建立及公式所代表的意義如下：求路線距離總和的最小值。貨車經(jīng)過每一條路線的總載貨容量不能超過貨車的容量。上式是物流配送中心的總車輛數(shù)，下式是各需求點只能由一部貨車服務(wù)的限制。流量守恒限制。貨車k的配送點指派。貨車k的路線指派。流量守恒限制。14.2單中心非滿載送貨車輛路徑問題啟發(fā)式算法14.2.3求解過程本文擬采用“先分組再排線路”的二階段求解方法，進(jìn)行配送線路的安排，也就是先將所有的配送點進(jìn)行分組，然后再對每一組集中的配送點做最優(yōu)化路線的處理，換句話說，是將車輛路線問題（VRP）轉(zhuǎn)換成多個旅行商問題（TSP）進(jìn)行求解。14.2單中心非滿載送貨車輛路徑問題啟發(fā)式算法14.2.3求解過程為了使每輛貨車所負(fù)責(zé)的配送點盡量相鄰，滿足物流業(yè)者單一區(qū)域配送上的需要，本論文以掃描法為基礎(chǔ)，修改其演算方法進(jìn)行初始解的構(gòu)造，此方法可以達(dá)到先分組的目標(biāo)，而且此方法在選擇配送點進(jìn)行求解時，可以將鄰近的點選入同一群組中，滿足初始解的基本需求。而在車輛路線規(guī)劃方面，在構(gòu)造初始解路線時，加入“車輛載重限制”的條件，使得初始解的每一群組均能滿足此限制。1.構(gòu)造初始解14.2單中心非滿載送貨車輛路徑問題啟發(fā)式算法14.2.3求解過程（1）配送點數(shù)據(jù)的輸入進(jìn)行禁忌搜索之前，必須先建立配送點的相關(guān)數(shù)據(jù)，而配送點數(shù)據(jù)應(yīng)包括坐標(biāo)及配送量。為配送點設(shè)計數(shù)據(jù)表。2.禁忌搜索字段名稱數(shù)據(jù)類型描述備注ID整型（Integer）配送點的編號設(shè)為主鍵X_position雙精度型（Double）配送點的X坐標(biāo)Y_position雙精度型（Double）配送點的Y坐標(biāo)Weight雙精度型（Double）配送點的配送量14.2單中心非滿載送貨車輛路徑問題啟發(fā)式算法14.2.3求解過程（2）設(shè)定參數(shù)禁忌名單（TabuList）的長度：文獻(xiàn)中大多建議使用7作為禁忌名單的長度。最大重復(fù)搜尋次數(shù)：本文假設(shè)