基于遺傳算法的車輛路徑問題研究(編輯修改稿)

　

【文章內(nèi)容簡介】 所有的需求點建構(gòu)成一條路線，再根據(jù)車輛的容量將這一路線分割成許多適合的單獨路線。 1990 年以來，人工智能方法在解決組合優(yōu)化問題上顯示出強大功能，在各個領(lǐng)域得到充分應用，很多學者也將 人工智能 引入車輛路線問題的求解中，并構(gòu)造了大量的基于人工智能的啟發(fā)式算法 。 禁忌搜索法 （ TS）基本上是屬于一種人工智能型（ AI）的局部搜尋方法， Willard 首先將此算法用來求解 VRP ，隨后亦有許多位學者也發(fā)表了求解 VRP 的 TS 算法。 西南交通大學 的袁慶達等設(shè)計了考慮時間窗口和不同車輛類型的禁忌算法，這種算法主要采用 GENIUS 方法產(chǎn)生初始解，然后禁忌算法對初始解優(yōu)化。模擬退火方法具有收斂速度快，全局搜索的特點， Osman 對 VRP 的模擬退火算法進行了研究，他提出的模擬退火方法主要適合于解決路線分組。 遺傳算法 具有求解組合優(yōu)化問題的良好特性， Holland 首先采用遺傳算法（ GA）編碼解決 VRPTW 問題?，F(xiàn)在多數(shù)學者采用混合策略，分別采用兩種人工智能方法進行路線分組和路線優(yōu)化。 Ombuk 提出了用 遺傳算法 進行路線分組，然后用禁忌搜索方法進行路線優(yōu)化的混合算法。 Bent 和 Van Hentenryck 則首先用 模擬退火算法 將車輛路線的數(shù)量最小化，然后用大鄰域搜索法（ largneighborhood search）將運輸費用降到最低。 10 總結(jié)幾種人工智能方法可以看出， TS 算法所得到的解最接近最優(yōu)解，但其運算時間也最長，是 GA 算法的 2～ 3 倍， SA 算法的近 20 倍；由于 GA 算法也能較好的逼近最優(yōu) 解，同時使運算時間大大縮短，所以 GA 算法能兼顧運算時間和效率兩方面，是具有較好的發(fā)展前途的方法； SA 算法求解速度非常快，也能提供一定程度上的優(yōu)化方案在求解較小規(guī)模問題上具有較好效果。 11 4 遺傳算法介紹 遺傳算法簡稱 GA(Geic Algorithm)，在本質(zhì)上是一種不依賴具體問題的直接搜索方法。它是根據(jù)生物進化思想而啟發(fā)得出的一種全局優(yōu)化算法。遺傳算法的概念最早是由 Bagley 在 1967 年提出的；而開始遺傳算法的理論和方法的系統(tǒng)性研究的是 1975 年，這一開創(chuàng)性工作是由 Michigan 大學的 . Holland 所實行。當時，其主要目的是說明自然和人工系統(tǒng)的自適應過程。 遺傳算法是受生物進化學說和遺傳學說啟發(fā)而發(fā)展起來的，基于適者生存思想的一種較通用的問題求解方法。利用遺傳算法進行尋優(yōu)時，編碼、選擇、交叉、變異是四個重要步驟。遺傳算法作為一種全局優(yōu)化搜索方法，具有簡單、通用普適性強，適用于并行處理和應用范圍廣等優(yōu)點。遺傳算法在優(yōu)化領(lǐng)域表現(xiàn)出了其強大的能力，遺傳算法仿照生物進化和遺傳的規(guī)律，利用復制、交換和突變等操作，使優(yōu)勝者繁殖，劣敗 者消失，一代代重復同樣的操作，最終找出最優(yōu)解。具有如下特點： (1) 遺傳算法運算的是解集的編碼，而不是解集本身； (2) 遺傳算法的搜索始于解的一個種群，而不是單個解； (3) 遺傳算法只使用報酬信息（適值函數(shù)），不使用導數(shù)或其他輔助知識； (4) 遺傳算法采用概率的，而不是確定的狀態(tài)轉(zhuǎn)移規(guī)則。 遺傳算法特別適用于傳統(tǒng)搜索方法難以解決的復雜的和非線性的問題，可廣泛用于組合優(yōu)化、自適應控制、規(guī)劃設(shè)計和人工生命等領(lǐng)域。作為一種隨機優(yōu)化技術(shù)在解優(yōu)化問題中顯示了優(yōu)于傳統(tǒng)優(yōu)化算法的性能，遺傳算法的一個顯著優(yōu) 勢是不需要目標函數(shù)明確的數(shù)學方程和導數(shù)表達式，同時又是一種全局尋優(yōu)算法，不會象某些傳統(tǒng)算法易于陷入局部最優(yōu)解。 遺傳算法是具有 “ 生成 +檢測 ”(generate andtest)的迭代過程的搜索算法 。遺傳算法中包含了如下 5 個基本要素： 1)參數(shù)編碼； 2)初始群體的設(shè)定； 3)適應度函數(shù)的設(shè)計； 4)遺傳操作設(shè)計； 12 5） 控制參數(shù)設(shè)定 (主要是指群體大小和使用遺傳操作的概率等 )。 這 5 個要素構(gòu)成了遺傳算法的核心內(nèi)容。 遺傳算法的基本思想 遺傳算法是受生物進化學說和遺傳學說啟發(fā)而發(fā)展起來的，基于 適者生存思想的一種較通用的問題求解方法。利用遺傳算法進行尋優(yōu)時，編碼、選擇、交叉、變異是四個重要步驟。遺傳算法作為一種全局優(yōu)化搜索方法，具有簡單、通用普適性強，適用于并行處理和應用范圍廣等優(yōu)點。遺傳算法在優(yōu)化領(lǐng)域表現(xiàn)出了其強大的能力，遺傳算法仿照生物進化和遺傳的規(guī)律，利用復制、交換和突變等操作，使優(yōu)勝者繁殖，劣敗者消失，一代代重復同樣的操作，最終找出最優(yōu)解。具有如下特點： (1) 遺傳算法運算的是解集的編碼，而不是解集本身； (2) 遺傳算法的搜索始于解的一個種群，而不是單個解； (3) 遺傳算法只使用報酬 信息（適值函數(shù)），不使用導數(shù)或其他輔助知識； (4) 遺傳算法采用概率的，而不是確定的狀態(tài)轉(zhuǎn)移規(guī)則。 遺傳算法流程圖 13 圖 2 遺傳算法流程圖 14 5 模型建立求解及實例應用 車輛調(diào)度模型 根據(jù)上述對問題的描述 ， 可以采用混合整數(shù)規(guī)劃方法對車輛調(diào)度進行建模 設(shè) N為最小成本 ， 則目標函數(shù)為 滿足約束條件 1： 式中： K為所有車輛的集合， ； G為所有客戶的集合， ， ， 其中 {0}代表配送中心 ； 為由車輛 k服務(wù)的客戶的集合； 為車輛到達客戶 i的時間； 為懲罰函數(shù)，車輛在時間 到達客戶 i時所對應的懲罰成本； 為車輛從客戶 i到客戶 j的所有運輸成本； 為車輛從客戶 i到客戶 j的行車時間； 為客戶 i的需求量 ； Q為車輛 k的最大裝載量； 為車輛在客戶 i處的停留的時間。 另外 ， 變量 和 的值為 0 或 1。 若車輛 k 為客戶 i 服務(wù) ， 則 1， 否則為 0， 即 ： 此變量表示車輛分配方案 ， 可用布爾矩陣表示 ； 若車輛 k 經(jīng)由客戶 i 到客戶 j， 則 為 1， 否則為 0， 即 ：， 表示車輛路線安排 。 約束條件 2： 保證每個客戶均被服務(wù) ， 而且每輛車都從配送中心出發(fā) ； 約束條件 3： 表示每輛車負責的客戶點的貨物需求量總和不超過該車輛的最大裝載量 ； 15 約束條件 5： 表示對任一由 k服務(wù)的客戶點 j必定有另一 (而且只有一個 )由 k服務(wù)的客戶點 (包括配送中心 )I,車輛 k從客戶點 i到達客戶點 j,而對由 k服務(wù)的客戶點 i同樣存在由 k服務(wù)的另一客戶點 ,車輛 k是從該客戶點到達客戶點 i的 ,依次類推 ； 約束條件 6： 保證每輛車的行車路線的總耗時不超過一個事先定下的數(shù)值 ； 約束條件 7： 對某個客戶點 ， 車輛到達時間限制 在某一時間段內(nèi) 。 根據(jù)實際情況 ， 本文采用軟限制時間窗 ， 其懲罰函數(shù) 如圖 2所示 。 其中 ，為客戶所要求的送貨時區(qū) ， 為時間窗 ， 超過該范圍客戶將拒絕收貨 ， 因此設(shè)定一個極大的懲罰成本 以避免此情況的發(fā)生 。 圖 3 懲罰函數(shù) 帶時間窗的物流配送問題優(yōu)化問題 帶時間窗 VRP（ VRP with Time Windows， VRPTW）是帶裝載能力約束的CVRP(Capacitated VRP， CVRP)的擴展。在該類問題中，有車輛裝載能力約束，且每個客戶 i 都有一個與之相聯(lián)系的時間區(qū)間 [ai ,bi]， 稱為時間窗。客戶的服務(wù)必須在相應的時間窗內(nèi)開始，車輛必須在客戶點停留的時間長度為 si。按客戶對物流中心違反時間窗約束規(guī)定時的接受程度，可分為硬時間窗、軟時間窗和混合型時間窗。硬時間窗 (Hard Time Windows)：指配送車輛必須在特定時間區(qū)段，將貨物送達顧客手中，不論是遲到或早到都完全不予接受；軟時間窗 (Soft Time Windows)：允許服務(wù)的開始時間有所偏離時間窗，則必須按照違反時間的長短