《車輛路徑問題》PPT課件.ppt

1、第14章 車輛路徑問題 （Vehicle Path Problem）,車輛路徑問題，又稱運(yùn)輸調(diào)度問題，簡記VRP&VSP,包括兩部分，其一是行車路線的設(shè)計(jì)，其二是出行時(shí)間表的安排。該問題1959年由Dantzig和Ramser提出的，是指在客戶需求位置已知的情況下，確定車輛在各個(gè)客戶間的行程路線，使得運(yùn)輸路線最短或運(yùn)輸成本最低，通過研究VRP可以合理使用調(diào)運(yùn)工具，優(yōu)化運(yùn)輸路線，降低企業(yè)物流成本。,第14章 車輛路徑問題（Vehicle Path Problem） 14.1 物流配送車輛優(yōu)化調(diào)度的概述 （Introduction of VRP for Logistics Distribution

2、） 14.1.1 概述（Introduction） 14.1.2 路徑特性（The Route Characteristic） 14.1.3 常用的基本問題（The Basic Problems） 14.1.4 車輛路徑問題的求解方法（The Method of Solving Route Problem） 14.2 單中心非滿載送貨車輛路徑問題啟發(fā)式算法 （Heuristic Methods for One Center VRP with Non-fully Loaded） 14.2.1 禁忌搜尋法簡介（Tabu-Research Algorithm） 14.2.2 問題描述與符號表示（Th

3、e Problem and Symbol） 14.2.3 求解過程（Arithmetic）,第14章 車輛路徑問題（Vehicle Path Problem） 14.3 車輛調(diào)度的其他算法簡介（Some Other Algorithms for VRP） 14.3.1 遺傳算法（Genetic Algorithm） 14.3.2 神經(jīng)網(wǎng)絡(luò)算法（Neural Networks Algorithm）,14.1 物流配送車輛優(yōu)化調(diào)度的概述,14.1.1 概述,車輛路徑問題一般定義為：對一系列裝貨點(diǎn)和(或)卸貨點(diǎn)，組織適當(dāng)?shù)男熊嚲€路，使車輛有序地通過它們，在滿足一定的約束條件(如：貨物需求量、發(fā)送量、

4、交發(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è)中心（中心車庫）一個(gè)車輛集合和一個(gè)顧客集合，車輛和顧客各有自己的屬性，每輛車都有容量，所載的貨物不能超過它的容量。,14.1 物流配送車輛優(yōu)化調(diào)度的概述,14.1.2 路徑特性,車輛路徑問題的特性比較復(fù)雜，總的來說包含四個(gè)方面的屬性： （1）地址特性包括：車場數(shù)目、需求類型、作業(yè)要求。 （2）車輛特性包括：車輛數(shù)量、載重量約束、可運(yùn)載品種約束、運(yùn)行路線約束、

5、工作時(shí)間約束。 （3）問題的其他特性。 （4）目標(biāo)函數(shù)可能是總成本極小化，或者極小化最大作業(yè)成本，或者最大化準(zhǔn)時(shí)作業(yè)。,14.1 物流配送車輛優(yōu)化調(diào)度的概述,14.1.2 路徑特性,車輛路徑問題的特性導(dǎo)致了算法的多樣性和復(fù)雜性。為簡化問題的求解，常常應(yīng)用一些技術(shù)將問題分解或轉(zhuǎn)化成一個(gè)或幾個(gè)已經(jīng)研究過的基本問題，再用相應(yīng)比較成熟的基本理論和方法，以得到原滿意解。,14.1 物流配送車輛優(yōu)化調(diào)度的概述,14.1.3 常用的基本問題,（1）旅行商問題 （2）帶容量約束的車輛路線問題 （3）帶時(shí)間窗的車輛路線問題 （4）收集和分發(fā)問題 （5）多車型車輛路線問題 （6）優(yōu)先約束車輛路線問題 （7）相容性

6、約束車輛路線問題 （8）隨機(jī)需求車輛路線問題,14.1 物流配送車輛優(yōu)化調(diào)度的概述,14.1.4 車輛路徑問題的求解方法,由于車輛路徑問題是個(gè)NP難題，為了找到滿足約束條件的最優(yōu)解，就必須檢查很大的設(shè)計(jì)空間，而設(shè)計(jì)空間又是多維的非連續(xù)空間，很難找到一個(gè)規(guī)范的搜索集來系統(tǒng)地搜尋整個(gè)空間，所以很難得到全局的最優(yōu)解或滿意解?，F(xiàn)代研究針對以上問題，現(xiàn)在已有很多方法。,14.1 物流配送車輛優(yōu)化調(diào)度的概述,14.1.4 車輛路徑問題的求解方法,1. 數(shù)學(xué)解析法 此法以動(dòng)態(tài)規(guī)劃法、整數(shù)規(guī)劃法、樹狀搜尋法等方式為主來進(jìn)行求解，對于配送點(diǎn)數(shù)較少的情形能求得一個(gè)最優(yōu)解，但若求解的節(jié)點(diǎn)數(shù)增加，則其結(jié)果相對變差，與

7、實(shí)際配送的情相差較大。,14.1 物流配送車輛優(yōu)化調(diào)度的概述,14.1.4 車輛路徑問題的求解方法,2. 人機(jī)互動(dòng)法 提供使用者借由人機(jī)互動(dòng)的方式，結(jié)合使用者過去的經(jīng)驗(yàn)，調(diào)整該模型的參數(shù)，以作為配送路線規(guī)劃決策的依據(jù)。,14.1 物流配送車輛優(yōu)化調(diào)度的概述,14.1.4 車輛路徑問題的求解方法,3. 先分組再排路線法 先將所有配送點(diǎn)分成數(shù)個(gè)群組，再分別對各個(gè)群組進(jìn)行路線規(guī)劃，如掃描法，根據(jù)所有配送點(diǎn)的分布，以極坐標(biāo)的表示方法來呈現(xiàn)各配送點(diǎn)的位置，然后任意選取一配送點(diǎn)為起始點(diǎn)，依順時(shí)針或逆時(shí)針的方向選取尚未指派的配送點(diǎn)，并以貨車的容量或其他條件作為限制，進(jìn)行車輛配送的分組作業(yè)，再以求解旅行商問題

8、的算法進(jìn)行最優(yōu)化的操作。,14.1 物流配送車輛優(yōu)化調(diào)度的概述,14.1.4 車輛路徑問題的求解方法,14.1 物流配送車輛優(yōu)化調(diào)度的概述,14.1.4 車輛路徑問題的求解方法,4. 先排線路再分組法（Rout FirstCluster Second） 與前一種方法相反，這種方法是先進(jìn)行路線的規(guī)劃，然后再進(jìn)行分割，如巨集分割法，此方法又因切割方式的差異，可分為單巨集切割法及多巨集切割法二種。,14.1 物流配送車輛優(yōu)化調(diào)度的概述,14.1.4 車輛路徑問題的求解方法,（1）單巨集切割法 取所有配送點(diǎn)進(jìn)行旅行商問題的求解，建立一個(gè)自原點(diǎn)出發(fā)，經(jīng)過所有結(jié)點(diǎn)，最后回到原點(diǎn)的巡回路線，然后以最短路徑解

9、法對此路線進(jìn)行分割，求得所需要的結(jié)果。 （2）多巨集切割法 與單巨集切割法相似，最大的差異在于建立巡回路線時(shí)并不包含原點(diǎn)，因此在切割路線時(shí)，可以有較多的切割方式。,14.1 物流配送車輛優(yōu)化調(diào)度的概述,14.1.4 車輛路徑問題的求解方法,5. 節(jié)省或插入法（Saving or Insertion） 由于數(shù)學(xué)解析法具有先天上的限制，對于大規(guī)模求解問題的效率與結(jié)果較為不佳，因此，求得一個(gè)近似的最優(yōu)解，是本論文研究的目標(biāo)，為克服這個(gè)問題，許多學(xué)者提出了各種求解方法，其優(yōu)點(diǎn)在于能夠改善以往數(shù)學(xué)方法的求解效率，但并不一定保證所求出的解是最優(yōu)解。節(jié)省與插入法即為此一范疇的求解方法。,14.1 物流配送車

10、輛優(yōu)化調(diào)度的概述,14.1.4 車輛路徑問題的求解方法,（1）節(jié)省法 此方法以三角不等式為基礎(chǔ)，一部車只一個(gè)配送點(diǎn)為起始條件，如此若有N個(gè)配送點(diǎn)即有N條路線，計(jì)算節(jié)省量，將較短的路線與原始路線交換，縮短配送距離。假設(shè)配送點(diǎn)i與j分別由不同的車輛來服務(wù)，如將兩個(gè)配送點(diǎn)由一輛車服務(wù)，即可得到一個(gè)節(jié)省值，而后依據(jù)節(jié)省值的大小決定需求點(diǎn)是否可以相互連接，連接的方法有連結(jié)、并入、合并等三種。,14.1 物流配送車輛優(yōu)化調(diào)度的概述,14.1.4 車輛路徑問題的求解方法,14.1 物流配送車輛優(yōu)化調(diào)度的概述,14.1.4 車輛路徑問題的求解方法,（2）插入法 將節(jié)省法中節(jié)省值的觀念應(yīng)用于循序路線構(gòu)建上，并以

11、距離物流中心最遠(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 車輛路徑問題的求解方法,6. 改善或交換法 常見的改善方法有2-opt、3-opt方法，與k-opt方法等，是先以其他方法產(chǎn)生初始解，再利用節(jié)點(diǎn)或節(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)化處理。如車輛路線問

12、題，轉(zhuǎn)換成由兩個(gè)相關(guān)子問題組成的數(shù)學(xué)規(guī)劃，其中一個(gè)為一般化配送點(diǎn)的指派問題，另一個(gè)則為旅行商問題，并提出一些準(zhǔn)則用來產(chǎn)生路徑種子點(diǎn)，再利用節(jié)省值產(chǎn)生一個(gè)指派問題的目標(biāo)函數(shù)，然后先解指派問題，再針對每輛車的旅行商問題求解。,14.2 單中心非滿載送貨車輛路徑問題啟發(fā)式算法,14.2.1 禁忌搜尋法簡介,禁忌搜尋法的概念首先由Glover于1977年提出，當(dāng)時(shí)是將其應(yīng)用于整數(shù)規(guī)劃的求解問題上，直到1989、1990年Glover才將禁忌搜尋法的結(jié)構(gòu)與方法完整提出。其主要內(nèi)容是使用移步的方式，運(yùn)用具有彈性的記憶結(jié)構(gòu)，以迭代的方式從目前的解出發(fā)展開對鄰近解的搜尋，而其記憶結(jié)構(gòu)可分為長期記憶結(jié)構(gòu)和短期記

13、憶結(jié)構(gòu)兩種。記憶的目的在于使尋求解的過程能越過局部最優(yōu)解而找到更好的解。,14.2 單中心非滿載送貨車輛路徑問題啟發(fā)式算法,14.2.1 禁忌搜尋法簡介,禁忌搜尋法的演算過程是先在問題中找到一組可行解 ，再依使用者所做的定義找出所有的鄰近解N( )，在N( )中找出最優(yōu)解 ，若F( )優(yōu)于F( )時(shí)，即將現(xiàn)在解移步至 ，為了避免尋求解的范圍落入某一區(qū)域中，禁忌搜尋法允許當(dāng)F( )未能優(yōu)于F( )時(shí)，仍然接受 為新的現(xiàn)在解，使尋解的過程能跳離某一區(qū)域，找到更佳的解。,14.2 單中心非滿載送貨車輛路徑問題啟發(fā)式算法,14.2.1 禁忌搜尋法簡介,1. 初始解 如果沒有特殊限制條件，可以任選一可行

14、解作為該問題的初始解，以本論文研究的車輛路線問題為例，初始解的限制條件為“車輛的載重”，因此必須考慮滿足所有配送點(diǎn)及車輛載重的限制，并建立適當(dāng)?shù)某跏冀狻?禁忌搜尋法的主要步驟,14.2 單中心非滿載送貨車輛路徑問題啟發(fā)式算法,14.2.1 禁忌搜尋法簡介,2. 移步 每次迭代的過程中，在所有合法的鄰近解里，選擇其一進(jìn)行變動(dòng)的行為，稱之為移步。,禁忌搜尋法的主要步驟,14.2 單中心非滿載送貨車輛路徑問題啟發(fā)式算法,14.2.1 禁忌搜尋法簡介,3. 禁忌名單 為了避免重復(fù)選取已經(jīng)選取過的解，禁忌搜尋法會(huì)將最近幾次移步的屬性記錄在禁忌名單中，作為禁忌限制的參考指標(biāo)，來防止重復(fù)搜尋的現(xiàn)象。 禁忌名

15、單的長度會(huì)影響到求解尋優(yōu)過程的結(jié)果，當(dāng)禁忌名單長度太短時(shí)，搜尋過程可能會(huì)落入局部解的限制；若禁忌名單太長，除了要花費(fèi)較多的時(shí)間檢查移步是否被禁忌外，還可能導(dǎo)致搜尋過程遠(yuǎn)離最優(yōu)解位置的可能性。,禁忌搜尋法的主要步驟,14.2 單中心非滿載送貨車輛路徑問題啟發(fā)式算法,14.2.1 禁忌搜尋法簡介,4. 免禁準(zhǔn)則 當(dāng)一個(gè)移步為禁忌，但是若此一移步被允許，可以使得目前所搜尋到的目標(biāo)函數(shù)值得以改善時(shí)，則接受此一移步，免禁準(zhǔn)則的目的就是用來釋放原本禁忌的狀態(tài)，在求解過程中能逃脫局部最優(yōu)解的局限。,禁忌搜尋法的主要步驟,14.2 單中心非滿載送貨車輛路徑問題啟發(fā)式算法,14.2.1 禁忌搜尋法簡介,5. 停

16、止準(zhǔn)則 停止準(zhǔn)則是整個(gè)演算過程結(jié)束的條件，通常使用以下四種準(zhǔn)則： （1）預(yù)設(shè)最大迭代次數(shù)； （2）目標(biāo)函數(shù)值持續(xù)未改善的次數(shù)； （3）預(yù)設(shè)允許CPU最長的執(zhí)行時(shí)間； （4）預(yù)設(shè)可接受的目標(biāo)函數(shù)值。,禁忌搜尋法的主要步驟,14.2 單中心非滿載送貨車輛路徑問題啟發(fā)式算法,14.2.2 問題描述與符號表示,所求單中心非滿載送貨車輛路徑問題具有以下特點(diǎn)： （1）物流配送中心的位置為已知并且唯一； （2）需求點(diǎn)的位置及需求量為已知； （3）需求點(diǎn)與需求點(diǎn)間的路線與距離為已知且確定； （4）貨車經(jīng)過需求點(diǎn)時(shí)只有卸貨而無裝貨，貨物配送完畢以空車返回配送中心； （5）物流中心只有一種貨車。 所求的目標(biāo)函數(shù)為

17、：使貨車配送路線的總成本最小，在本文中體現(xiàn)為配送路線距離最短。,14.2 單中心非滿載送貨車輛路徑問題啟發(fā)式算法,14.2.2 問題描述與符號表示,14.2 單中心非滿載送貨車輛路徑問題啟發(fā)式算法,14.2.2 問題描述與符號表示,數(shù)學(xué)模型建立及公式所代表的意義如下：,14.2 單中心非滿載送貨車輛路徑問題啟發(fā)式算法,14.2.3 求解過程,本文擬采用“先分組再排線路”的二階段求解方法，進(jìn)行配送線路的安排，也就是先將所有的配送點(diǎn)進(jìn)行分組，然后再對每一組集中的配送點(diǎn)做最優(yōu)化路線的處理，換句話說，是將車輛路線問題（VRP）轉(zhuǎn)換成多個(gè)旅行商問題（TSP）進(jìn)行求解。,14.2 單中心非滿載送貨車輛路徑

18、問題啟發(fā)式算法,14.2.3 求解過程,為了使每輛貨車所負(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 單中心非滿載送貨車輛路徑問題啟發(fā)式算法,14.2.3 求解過程,（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ù)表

19、。,2. 禁忌搜索,14.2 單中心非滿載送貨車輛路徑問題啟發(fā)式算法,14.2.3 求解過程,（2）設(shè)定參數(shù) 禁忌名單（Tabu List）的長度： 文獻(xiàn)中大多建議使用7作為禁忌名單的長度。 最大重復(fù)搜尋次數(shù)： 本文假設(shè)其值為100，意即重復(fù)搜尋100次。,2. 禁忌搜索,14.2 單中心非滿載送貨車輛路徑問題啟發(fā)式算法,14.2.3 求解過程,（3）目標(biāo)函數(shù)與移步 在計(jì)算目標(biāo)函數(shù)值之前，首先建立一個(gè)對稱矩陣，目的是為了存放兩兩配送點(diǎn)之間的距離。,2. 禁忌搜索,14.2 單中心非滿載送貨車輛路徑問題啟發(fā)式算法,14.2.3 求解過程,（3）目標(biāo)函數(shù)與移步 計(jì)算目標(biāo)函數(shù)值時(shí)，使用點(diǎn)對交換（ P

20、air Swap ）的節(jié)點(diǎn)交換法作為禁忌搜尋法的移步方法，來達(dá)到展開鄰近解搜尋的目的。Pair Swap 有兩種可能的形式，第一種可能的形式是針對彼此相鄰的兩個(gè)配送點(diǎn)；第二種形式是任選配送路線中的二點(diǎn)進(jìn)行交換。由以上這種節(jié)點(diǎn)交換方法來判斷是否有出現(xiàn)較佳的解，來獲得較好的目標(biāo)函數(shù)值。,2. 禁忌搜索,14.2 單中心非滿載送貨車輛路徑問題啟發(fā)式算法,14.2.3 求解過程,本文建立初始解所使用的掃描法，對車輛路線問題而言是一種先分組的方法，因此被納入組中的配送點(diǎn)就無法在不同的路線中跳動(dòng)，得到較差的初始解結(jié)果。此處使用兩種不同路線中交換節(jié)點(diǎn)的方法來彌補(bǔ)這個(gè)缺陷，期望能在配送點(diǎn)盡量相鄰的條件下，找出

21、更好的路線規(guī)劃。,3. 最優(yōu)解的改善,14.2 單中心非滿載送貨車輛路徑問題啟發(fā)式算法,14.2.3 求解過程,方法一：將兩不同路線中，相同順序的連續(xù)兩個(gè)配送點(diǎn)進(jìn)行交換。如果交換后的總成本較原始路線為佳，則進(jìn)行路線的變動(dòng)。,3. 最優(yōu)解的改善,交換后,交換前,14.2 單中心非滿載送貨車輛路徑問題啟發(fā)式算法,14.2.3 求解過程,方法二：將二路線中同一順序的配送點(diǎn)互換后，其后的配送點(diǎn)全部一起交換，因?yàn)榈谝稽c(diǎn)交換與原路線沒有差異，所以使用此法從第二點(diǎn)開始交換。如果交換后的總成本較原始路線為佳，則進(jìn)行路線的變動(dòng)。,3. 最優(yōu)解的改善,交換后,交換前,14.2 單中心非滿載送貨車輛路徑問題啟發(fā)式算

22、法,14.2.3 求解過程,整個(gè)求解的完整流程,3. 最優(yōu)解的改善,14.2 單中心非滿載送貨車輛路徑問題啟發(fā)式算法,14.2.3 求解過程,由上頁流程圖可知，本算法是將車輛路徑問題轉(zhuǎn)換成多個(gè)旅行商問題進(jìn)行求解。首先用改進(jìn)后的掃描法建立初始解，即根據(jù)車輛載重限制對所有配送點(diǎn)建立多輛車的配送路徑，然后對每輛車的配送路徑用旅行商算法進(jìn)行求解（即上頁圖所示的“將規(guī)劃的路線選入TS，進(jìn)行最優(yōu)化處理”一步），最后找到總成本最小的解并利用前文所述之方法進(jìn)行解的改善。,3. 最優(yōu)解的改善,14.3 車輛調(diào)度的其他算法簡介,14.3.1 遺傳算法,遺傳算法主要由選擇、交叉和變異三個(gè)算子組成，分別模仿自然界進(jìn)化

23、過程中的自然選擇和群體遺傳過程中發(fā)生的交配和突變等現(xiàn)象。采用遺傳算法求解車輛優(yōu)化調(diào)度問題時(shí)，一般按照以下步驟進(jìn)行：,14.3 車輛調(diào)度的其他算法簡介,14.3.1 遺傳算法,采用自然數(shù)對可行線路進(jìn)行編碼，如長度為lm的染色體可寫為：(0,i11,i12,i1s, 0,i21,i2t,0,0,im1,imn)。其中，ikj表示第ikj項(xiàng)任務(wù)，這樣的染色體結(jié)構(gòu)可理解為車輛從車場0出發(fā)，經(jīng)過任務(wù)i11，i12，i1s后回到車場，形成子路徑1；如此反復(fù)，直到所有的m項(xiàng)任務(wù)全部被完成為止。在子路徑1內(nèi)交換i11 和i12的位置表示行走路徑的改變，也使函數(shù)目標(biāo)改變，這樣，下面的遺傳疊代可使函數(shù)目標(biāo)最小，也

24、即趨向于最佳或較佳的路徑。,1. 確定染色體的編碼和初始群體,14.3 車輛調(diào)度的其他算法簡介,14.3.1 遺傳算法,初始群體的產(chǎn)生采用隨機(jī)方法，隨機(jī)產(chǎn)生l個(gè)城市的全排列，根據(jù)任務(wù)的源點(diǎn)和匯點(diǎn)將0標(biāo)準(zhǔn)插入排列中，形成一條初始染色體。如此反復(fù)，直到滿足群體數(shù)，群體數(shù)一般大于20個(gè)。,1. 確定染色體的編碼和初始群體,14.3 車輛調(diào)度的其他算法簡介,14.3.1 遺傳算法,2. 確定適應(yīng)度函數(shù),車輛調(diào)度的優(yōu)化目標(biāo)有多種多樣，常見的目標(biāo)有總運(yùn)費(fèi)最小，總運(yùn)輸時(shí)間最短，空載車總運(yùn)行時(shí)間最小，完成任務(wù)所需的車輛最小總運(yùn)輸時(shí)間最短，空載車總運(yùn)行時(shí)間最小，完成任務(wù)所需的車輛最小等，以總運(yùn)費(fèi)最小為例，其目標(biāo)

25、函數(shù)為： 式中，Cij為從源點(diǎn)i到匯點(diǎn)j每輛車的單位費(fèi)用，Xij為每班從源點(diǎn)i到匯點(diǎn)j的滿載車的數(shù)量。m,n為源點(diǎn)和匯點(diǎn)的數(shù)目。,14.3 車輛調(diào)度的其他算法簡介,14.3.1 遺傳算法,為保證車輛調(diào)度優(yōu)化的正確性，約束往往必不可少，常見的約束有匯點(diǎn)處理能力約束，非負(fù)約束，車流連續(xù)性約束。 一般采用懲罰的方法來處理約束，如果一個(gè)染色體對應(yīng)的解違反了某個(gè)約束，根據(jù)其違反的程度給予一定的懲罰，使其具有較小的適應(yīng)度值。這樣在不損失群體數(shù)目的基礎(chǔ)上，隨著迭代的進(jìn)行，使不可行解的數(shù)目在群體中所占比例越來越小，可行解的數(shù)目則逐漸增加，并趨向最優(yōu)解。,3. 處理約束,14.3 車輛調(diào)度的其他算法簡介,14.

26、3.1 遺傳算法,經(jīng)典的遺傳算子包括復(fù)制、交叉、變異。復(fù)制算子的目的是保留優(yōu)良個(gè)體，避免基因缺失，提高全局收斂性和效率。目前常用的復(fù)制算子有放回式隨機(jī)復(fù)制又稱輪盤賭復(fù)制，無放回式隨機(jī)復(fù)制等十幾種。,4. 遺傳算子,14.3 車輛調(diào)度的其他算法簡介,14.3.1 遺傳算法,交叉算子的作用是組合出新的個(gè)體，在染色體空間進(jìn)行有效搜索，同時(shí)降低對有效模式的破壞概率。染色體采用自然數(shù)編碼時(shí)，交叉算子一般有部分匹配交叉，順序交叉，圈交叉等。染色體采用二進(jìn)制編碼時(shí)，常采用的交叉算子有單點(diǎn)交叉，雙點(diǎn)交叉等。交叉算子中采用的交叉率一般在0.750.95之間。,4. 遺傳算子,14.3 車輛調(diào)度的其他算法簡介,1

27、4.3.1 遺傳算法,變異算子是為了克服基因缺失和不成熟收斂。目前常用的變異算子有常規(guī)位變異，均勻變異和非均勻變異等。變異算子的變異率一般為0.0050.01。 除了上述的經(jīng)典遺傳算子外，人們又研究了其他一些算子，稱為高級算子，如顯性算子、倒位算子、分離和易位算子、遷移算子等。,4. 遺傳算子,14.3 車輛調(diào)度的其他算法簡介,14.3.1 遺傳算法,通過上述的遺傳操作，產(chǎn)生性能最優(yōu)的染色體串，根據(jù)初始的編碼規(guī)定將該串解碼成最優(yōu)調(diào)度方案。 實(shí)用中，人們往往將遺傳算法與其他方法如啟發(fā)式方法和模擬退火算法雜合，以及將調(diào)度專家經(jīng)驗(yàn)融入模型和遺傳操作中，以提高求解的效果。,5. 確定調(diào)度方案,14.3

28、 車輛調(diào)度的其他算法簡介,14.3.2 神經(jīng)網(wǎng)絡(luò)算法,人們經(jīng)常采用Hopfield網(wǎng)絡(luò)和自組織特征映射神經(jīng)網(wǎng)絡(luò)來解決車輛的優(yōu)化調(diào)度問題。在Hopfield網(wǎng)絡(luò)中，系統(tǒng)能夠從初始狀態(tài)，經(jīng)過一系列的狀態(tài)轉(zhuǎn)移而逐漸收斂于平衡狀態(tài)，此平衡狀態(tài)是局部極小點(diǎn)。采用神經(jīng)網(wǎng)絡(luò)來求解車輛調(diào)度問題時(shí)，一般按下述步驟進(jìn)行。,14.3 車輛調(diào)度的其他算法簡介,14.3. 2 神經(jīng)網(wǎng)絡(luò)算法,將車輛的源點(diǎn)、所經(jīng)過的各個(gè)匯點(diǎn)和停點(diǎn)抽象成網(wǎng)絡(luò)的結(jié)點(diǎn)，它們之間的有向路徑抽象成網(wǎng)絡(luò)的邊，由此構(gòu)成一個(gè)有向圖G=(N,L,D)，其中N表示結(jié)點(diǎn)數(shù)，L表示邊數(shù)，D為NN的矩陣，稱為鄰接矩陣。如果兩個(gè)結(jié)點(diǎn)間存在路徑，則鄰接矩陣相應(yīng)元素的值為路徑的長度