用遺傳算法解決車輛優化調度問題—免費畢業設計論文(編輯修改稿)

　

【文章內容簡介】 t 和 Miller， 1974； Christofids、Mingozzi和 Toth， 1979； Fisher 和 Jaikumar， 1981； Renaud、 Boctor 和 Laporte， 1996； Bramel和 SimchiLevi， 1995)。一般第一階段常用構造算法，在第二階段常用的改進技術有 2opt(Lin，1965)、 3opt(Lin Kernighan， 1973)和 Oropt(Or， 1976)交換法，這是一種在解的鄰域中搜索，對初始解進行某種程度優化的算法，以改進初始解。 在兩階段法求解過程中，常常采用交互式優化技術，把人的主觀能動作用結合到問題的求解過程中，其主要思想是：有經驗的決策者具有對結果和參數的某種判斷能力，并且根據知識直感，把主觀的估計加到優化模型中去。這樣做通常會增加模型最終實現并被采用的可能性。 （ 3）不完全優化算法 (Inplete Optimization Algorithm) 以 啟發式準則來代替精確算法中的決策準則，以縮小解搜索的空間 (Toth、 Christofides和 Mingozzi， 1979 等 )。 （ 4）改進算法 (Improvement Algorithm) 從一個初始解開始，通過對當前的解進行反復地局部擾亂 (Perturbations)以達到較好的解?；趩l式的并行算法和一些稱為亞啟發式算法 (Metaheuristics、 Laporte 和 Osman， 1996)的方法都屬于此類 (Cesar Rego， 1998； Gendrea、 Laporte 和 Potvin， 1994)［８ ］ 。 亞啟發式算法包括表搜索算法 (Table Search)、模擬退火算法 (Simulated Annealing)、遺傳算法 (Geic Algorithm)和神經網絡 (Neural Networks)方法。 貨運車輛優化調度問題的分類 根據任務的性質將貨物運輸分成以下幾類： 非滿載車輛優化調度問題 當貨物量小于車輛容量時，用一輛車執行任務，存在不滿載運行情況，調度時可安排一 7 輛車執行多項任務，即在一輛車上同時載有不同貨主的貨物。該類問題根據任務特征又分 為以下兩類： （ 1）集貨或送貨的車輛優化調度 所有任務全是集貨點或全是送貨點，車輛空車從車場出發，去各貨主處裝滿貨后返回車場。這種情況下，貨運量總數不超過車輛容量的任務可用一輛車來完成。 （ 2）集貨和送貨一體化的車輛優化調度 每一項貨運任務都有自己的集貨點和送貨點，車輛從車場出發，去某一任務的集貨地點裝貨后運至其送貨地點卸貨（即裝卸混合），完成所有任務后返回車場。 滿載車輛優化調度問題 當貨主的貨物量不小于車輛容量時，執行每項任務需要的車輛可能不只一輛，車輛為完成任務，需 滿載運行。根據任務特征可分為以下兩類： （ 1）集貨或送貨的車輛優化調度 載貨車輛由車場出發到幾個集貨點裝貨后返回車場（僅有裝貨），或是車輛出發到幾個送貨點卸貨（僅有卸貨）后返回車場。 （ 2）集貨和送貨一體化的車輛優化調度 每一項貨運任務都有自己的集貨點和送貨點，各項任務需要的車輛數不一致，這時需要對車輛進行優化調度，確定行車路線。 研究的意義 目前有關 VSP的研究，多致力于單一車種或多車種優化調度問題，很少涉及結合時間窗口的 VSP問題。 所謂時間窗口是指配送車輛或顧客希望服務或被服務的時間范 圍。由于消費者需求趨于多樣化，對送貨時間的要求日趨嚴格，尤其是運送有時效性的商品，例如海鮮、花卉、蔬菜、水果等講究新鮮度的貨物，除了因缺貨造成的機會成本的損失外，由于配送不及時也會造成貨物價值的大大降低。因此，在配送運輸上，時間因素是十分重要的。 有時間窗的 VSP問題也稱為 VSPTW(Vehicle Scheduling Problem with Time Windows） ，根據時間約束的嚴格與否，分為軟時間窗和硬時間窗的 VSP。由于有時間窗的 VSP是典型的NP— 難題，會隨著節點的增加出現組合爆炸的現象，因 此求解的困難度及時效性會有影響。 研究的范圍 由于有時間窗約束的車輛優化調度問題所牽涉的因素相當多，本研究僅針對具有普遍性的物流中心予以探討，就研究范圍與假設界定如下： 僅考慮區位己知的單一物流配送中心和供應商； 物流配送中心無缺貨的可能，而且商品種類單一； 物流配送中心已知顧客的基本配送資料 (需求量、地理位置、時間窗約束等 )； 8 物流配送中心擁有足夠數量的同類型配送車輛，即每輛車的載重量、時速相同。 9 第 2 章 有時間窗的車輛優化調度問題 (VSPTW) 時間窗的定義 VSPTW問題是傳統的車輛優化調度問題加上時間窗約束，時間窗約束可分為硬時間窗、軟時間窗與混合型時間窗。三者分述如下： 硬時間窗 (Hard Time Windows)：指配送車必須在特定時間區段 (如圖 21中的 ? ?le, )內將貨品送達顧客手中，不論是遲到或早到都完全不予接受。圖 21為一懲罰函數 (Penalty Function)當貨品送達時間超出 ? ?le, 時，其懲罰值 ??tP 等于一個非常大的正值， 表示硬時間窗的限制。 Desrochers (1988)曾指出硬時間窗寬度會影響尋優程序，并提出時間窗寬度評價指標，時間窗越寬則 VSPTW 問題越接近路線安排 (Routing)問題，越窄則越近似行程安排(Scheduling)問題。 圖 21 硬時間窗約束示意圖 軟時間窗 (Soft Time Windows)：指配送車輛如果無法將貨物在特定的時段 (如圖22的 ? ?le, )內送到顧客手中， 則必須按照違反時間的長短施以一定的罰金或其它懲罰法則。圖 22就是一種可能的懲罰函數。 t e l ??tP M 10 圖 22 軟時間窗約束示意圖 混合型時間窗 (Mixed Time Windows )：系統中有些顧客屬于硬時間窗，有些則屬于軟時間窗；同一顧客，往往軟、硬兩種時間窗混合使用。在實際的物流配送中，配送車輛如果能在最佳時段 (如圖 23 中的 ? ?le, 內將貨物送到顧客處，則不處罰；若在圖 23 中的（ ? ?ea, 或 ? ?bl, ）時段內才送達，則顧客的滿意度降低 (轉化為懲罰函數 )，而且顧客不接受上述兩個時段以外的時間 （ ? ?a,?? 或 ? ??,b ）收貨。 圖 23 混合型時間窗約束示意圖 e l t ??tP M ??tP e l t M a b 11 VSPTW 問題的結構 時間窗約束的車輛優化調度問題是在傳統的車輛優化調度問題的基礎上再加入顧客的時間窗約 束，所以該問題包含以下三項關鍵問題： 巡回 (Routing)問題 一般車輛優化調度問題中的配送車輛由配送中心出發后，必須完成其所指派客戶的配送，然后回到配送中心。所以對每一部車輛來說，是一個旅行商問題 (TSP)。 裝載 (Loading)問題 因為每一配送車輛都有規定負荷的載重量限制，所以在 TSP問題中加入配送車輛的裝載量限制，此時的問題成為一般車輛優化調度問題。 行程安排 (Scheduling)問題 一般車輛優化調度問題再加入時間窗約束，則必須考慮到達各顧客的先后順序，也就是行程安排問題。 有時 間窗約束的車輛優化調度問題可以用圖 24表示： 圖 24 VSPTW問題的結構 第 3 章 遺傳算法基本理論 遺傳算法的基本原理 遺傳算法是一類借鑒生物界自然選擇和自然遺傳機制的隨機搜索算法，它由美國Holland教授首先在《自然結合人工智能系統的適應性》一書中提出，是利用生物進化的特性所發展的方法，由一群群體 (Population)以隨機配對產生下一代，利用交叉 (Crossover)及變異 (Mutation)等操作進行基因的進化，并經 由選擇 (Selection)機能決定下一代相對的旅行商問題 一般車輛優化調度問題 有時間窗約束的車 輛優化調度問題 加入車輛裝載能力約束 加入時間窗約束 12 個數，使適應度越大的解存活的機會越大；也就是“適者生存”的原則來選擇隨機的值域，最后留下的就是最優解。 遺傳算法的特點 同傳統的尋優算法相比，遺傳算法具有以下特點： 算法對問題參數的代碼集起作用，而不是對參數本身起作用。遺傳算法處理的對象是染色體，因而要求把所要優化問題的基本參數轉化成一定長度的有限符號的染色體。 遺傳算法是從初始群體開始搜索的，而不是從單點開始搜索的。許多傳統優化方法都是從搜索空間的單點出發，通過某些轉換 規則確定下一點。這種點到點的搜索方法在多峰值優化問題中，容易誤入局部最優解。遺傳算法是以點集開始的尋優過程，初始群體是隨機地在搜索空間中選取的，覆蓋面大，利于全局尋優。 遺傳算法在求解時只使用適應度函數的信息，而不使用導數及其他輔助信息。對于不同類型的優化問題，傳統方法需要使用不同形式的輔助信息，沒有一種優化方法能適應各類問題的要求。遺傳算法在優化過程中，放棄使用這些輔助信息，具有廣泛適應性。 算法具有極強的容錯能力。遺傳算法的初始種群本身就帶有大量與最優解甚遠的信息，通過選擇、交叉、變異操作能迅速 排除與最優解相差極大的染色體。 算法具有隱含的并行性。 Goldeberg對 GA的處理并行性進行了合理的分析，指出了GA對模式的處理效率是 ? ?3no ， Holland稱之為 GA的“隱式并行性” ［５］ 。 遺傳算法中的選擇、交叉、和變異都是隨機操作，而不是確定的精確規則。復制體現了向最優解的逼近，交叉體現了最優解的產生，變異體現了全局最優解的覆蓋。 與傳統方法相比，遺傳算法的優越性主要表現在：首先，在遺傳算子的作用下，遺傳算法具有很強的搜索能力，能以很大的概率找到 問題的全局最優解：其次，由于它固有的并行性，能有效地處理大規模的優化問題。 遺傳算法的基本步驟和處理流程 遺傳算法的主要處理步驟是：首先構造滿足約束條件的染色體。編碼的目的主要是使優化問題解的表現形式適合于遺傳算法中的遺傳運算。實際問題的染色體有多種編碼方式，染色體編碼方式的選取應盡可能的符合問題約束，否則將影響計算效率。第二是隨機產生初始群體。初始群體群體的染色體數量應適當選擇。第三是是適應度函數的構造和應用，計算每個染色體適應度。適應度函數基本上依據問題的目標函數而定，是反映染色體優劣的 唯一指標，遺傳算法就是要尋得適應度最大的染色體。當適應度函數確定以后，復制是以適應度函數值的大小決定的概率分布來確定哪些染色體適應生存，哪些被淘汰。第四是染色體的交叉。父代的遺傳基因的結合是通過父代染色體之間的交叉并到達下一代個體的。子代的產生是一個生殖過程，它產生了一個新解；最后是變異，新解產生過程中可能產生基因變異，變異使某些解的編碼發生變化，使解具有更大的遍歷性。 13 遺傳算法的基本流程如圖 31所示。 圖 31 遺傳算法的基本流程 遺傳算法的應用 遺傳算法是 60年代由美國 J. Holland教授首先在《自然結合人工智能系統的適應性》一書中提出的，是一種新興的自適應隨機搜索方法，具有極強的魯棒性和內在的并行計算機制，特別適合于非凸空間中復雜的多極值優化和組合優化，在機器學習、自動控制、機器人技術、電器自動化以及計算機和通信領域以取得了非凡的成就。 遺傳算法的應用總的來說可以分為如下三大類： 優化計算 優化計算是遺傳算法最直接的應用，應用面也最廣。對于復雜的函數優化問題 (如非線性、不連續、多峰 值函數的優化等 )和組合優化問題 (如 VSP, TSP,01 背包問題、工作計劃問題 確定表示問題解答的染色體（編碼） 初始化染色體種群 計算每個染色體的適應度 滿足終止條件？ 根據適應度選擇串進行復制 交叉 變異 輸出最優解 否 是 14 制定等 )都有廣闊的發展前景。目前在運籌學、機械優化設計、電網設計、生產管理等應用學科中都嘗試著用遺傳算法解決現實優化計算問題。 機器學習 基于遺傳算法的機器學習也是遺傳算法應用研究的一個重要方面。機器學習是為解決專家系統設計中的知識獲取瓶頸問題而設計的。遺傳算法從其開始就與機器學習有著密切的聯系。分類器 CS1是 Halland與 Keitman實現的第一個基于遺傳算法的機器學習系統。 神經網絡 遺傳算法的另一個 活躍的研究方向是在神經網絡方面的應用，這包括優化神經網絡的連接權系數、網絡的空間結構等。遺傳算法與神經網絡的相結合應用于機械設計、結構優化、決策分析。 近些年來，人們在用遺傳算法解決現實中的各種組合優化問題上進行了探索，如在生產調度問題中的應用、對一般 TSP (Traveling Salesman Pr