第十四章 車輛路徑問(wèn)題

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