簡易檢索 / 詳目顯示

回結果列表
研究生： 許巍懷
論文名稱： 以混合演化式演算法求解多目標且具時窗限制之車輛路由問題
A Hybrid Multiobjective Evolutionary Algorithm for the Vehicle Routing Problem with Time Windows
指導教授： 蔣宗哲
學位類別： 碩士
Master
系所名稱： 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年： 2011
畢業學年度： 99
語文別： 中文
論文頁數： 50
中文關鍵詞： 基因演算法 、禁忌搜尋法 、時窗車輛路由問題 、多目標最佳化
論文種類： 學術論文
相關次數： 點閱：151  下載：14 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 車輛路由問題旨在尋求車輛與客戶之間最佳分配與移動路線，在已知客戶需求 (如運送量和服務時窗限制) 和車輛容量的情況下，由派車站發車前往服務客戶，最後返回派車站。車輛路由問題在實務上已有廣泛應用，如物品宅配、校車動線、計程車載客、銀行運鈔車補給、郵務信件遞送等等。
    本論文以具時窗限制之車輛路由問題為主題，其求解目標為最小化車輛數和總行駛距離，由柏拉圖最佳化觀點求解，提出一混合基因演算法和禁忌搜尋的求解方法。初始解經由禁忌搜尋將目標專於車輛數目最小化，再由基因演算法以多目標進行最佳化。並以改良式的交配和突變策略增加解的品質；在演化一定代數後由禁忌搜尋法對族群中非凌越解集進行深度搜尋以最小化行駛距離。
    測試問題集是Solomon建立的6大類共56個問題。本研究以多目標求解問題，對於文獻所提出的67個近似最佳解集合更新了34個，另外有2大類的問題可以達到車輛數與總距離的最佳解。

    誌謝 I 中文摘要 II 目錄 III 附圖目錄 VI 附表目錄 VIII 符號表 1 第一章 緒論 2 1.1 研究背景與動機 2 1.1.1 車輛路由問題 2 1.1.2 多目標最佳化問題 3 1.1.3 VRPTW的數學模型 4 1.2 研究目的、方法與貢獻 5 1.3 全文架構 6 第二章 文獻探討 7 2.1 建構式演算法 7 2.1.1 節省法 7 2.1.2 時間導向最近鄰點法 8 2.1.3 插入法 9 2.2 路線改善法 9 2.2.1 K-opt 10 2.2.2 Or-opt 10 2.2.3 λ-interchange 11 2.2.4 Cross-exchange 11 2.3 啟發式演算法 12 2.3.1 傳統VRPTW解法 12 2.3.2 兩階段求解VRPTW 13 2.3.3 違反限制 16 2.3.4 多目標觀點 17 2.3.5 特殊方法求解VRPTW 20 第三章 混合演化式演算法 23 3.1 演算法架構 24 3.2 路線表示法 24 3.3 基因演算法 25 3.3.1 起始解建構 25 3.3.2 適應度計算 26 3.3.3 親代選擇 26 3.3.4 交配 26 3.3.5 突變 28 3.3.6 環境選擇 30 3.4 禁忌搜尋法 31 3.4.1 禁忌搜尋步驟 31 3.4.2 禁忌名單 32 3.4.3 最小化目標 32 3.4.4 IR插入法 33 3.4.5 鄰域函式 34 第四章 實驗數據與效能評比 36 4.1 測試資料 36 4.2 比較文獻 37 4.3 效能指標 37 4.4 參數設定 37 4.5 效能評比 38 4.5.1 最小化路線數最佳解比較 38 4.5.2 最小化總行駛距離最佳解比較 40 4.5.3 多目標最佳解比較 41 4.6 觀察與討論 43 4.6.1 問題分析 43 4.6.2 參數測試 44 4.6.3 交配與突變策略 45 4.6.4 最小化車輛數 46 第五章 結論與未來發展 47 第六章 參考文獻 48

    [1] B. M. Baker, M. A. Ayechew, “A genetic algorithm for the vehicle routing problem,” Computers & Operations Research, vol. 30, pp. 787–800, 2003.
    [2] C. Prins, “A simple and effective evolutionary algorithm for the vehicle routing problem,” Computers & Operations Research, vol. 31, pp. 1985–2002, 2004.
    [3] K. C. Tan, L. H. Lee, Q. L. Zhu, and K. Ou, “Heuristic methods for vehicle routing problem with time windows,” Artificial Intelligence in Engineering, vol. 15, pp. 281–295, 2001.
    [4] M. M. Solomon, “Algorithms for the vehicle routing and scheduling problem,” Operations Research Society of America, vol. 35, no. 2, pp. 254－265, 1987.
    [5] S. R. Balseiro, I. Loiseau, J. Ramonet, “An ant colony algorithm hybridized with insertion heuristics for the time dependent vehicle routing problem with time windows,” Computer & Operations Research, vol. 38, pp. 954－966, 2011.
    [6] O. Bräysy, M. Gendreau, “Vehicle routing problem with time windows, Part I：Route construction and local search algorithm,” Transportation Science, vol. 39, No. 1, pp. 104－118, 2005.
    [7] E. Taillard, P. Badeau, M. Gendreau, F. Guertin and J. Y. Potvin, “A tabu search heuristic for the vehicle routing problem with soft time windows,” Transportation Science, vol. 31, pp. 170－186, 1997.
    [8] O. Bräysy, “A reactive variable neighborhood search for the vehicle routing problem with time windows,” Journal on Computing, vol. 15, no.4, pp. 347－368, 2003.
    [9] J. Y. Potvin, T. Kervahut, B. L. Garcia and J. M. Rousseau, “The vehicle routing problem with time windows, Part I : Tabu search,” Journal on Computing, vol. 8, no. 2, 158－164, 1996.
    [10] J. Y. Potvin, S. Bengio, “The vehicle routing problem with time windows , Part II: Genetic search,” Journal on Computing, vol. 8, no. 2, pp. 165－172, 1996.
    [11] J. Homberger, H. Gehring, “Two evolutionary metaheuristics for the vehicle routing problem with time windows,” Information Systems and Operational Research-Special issue: Metaheuristics for Location and Routing Problems, vol. 37, pp. 297－318, 1999.
    [12] R. Bent, P. V. Hentenryck, “A two-Stage hybrid local search for the vehicle routing problem with time windows,” Transportation Science, vol. 38, no. 4, pp. 515－530, 2001.
    [13] A. Lim, X. Zhang, “A two-stage heuristic with ejection pools and generalized ejection chains for the vehicle routing problem with time windows,” Journal on Computing, vol. 19, no. 3, pp. 443－457, 2007.
    [14] J. Berger, M. Barkoui, O. Bräysy, “A route-directed hybrid genetic approach for the vehicle problem with time windows,” Information Systems and Operations Research, vol. 41, pp. 179－194. 2003.
    [15] K. C. Tan, Y. H. Chew, L. H. Lee, “A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows,” Computational Optimization and Applications, vol. 34, pp. 115－151, 2006.
    [16] A. Garica-Najera, J. A. Bullinaria, “An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows,” Computer & Operations Research, vol. 38, pp. 287－300, 2011.
    [17] O. Bräysy, G. Hasle, W. Dullaert, “A multi-start local search algorithm for the vehicle routing problem with time windows,” European Journal of Operational Research, vol. 159, pp. 586－605, 2004.
    [18] Y. Nagata, O. Bräysy, “A powerful route minimization heuristic for the vehicle routing problem with time windows,” Operations Research Letters, vol. 37, pp. 333－338, 2009.
    [19] G. B. Alvarenga, G. R. Mateus, G. de. Tomi, “A genetic and set partitioning two-phase approach for the vehicle problem with time windows,” Computers & Operations Research, vol. 34, pp.1561－1584, 2007.
    [20] C. J. Ting, C. H. Chen, “An improved genetic algorithm for vehicle routing problem with time windows,” International Journal of Industrial Engineering, vol. 12, no. 3, pp.216－226, 2005.
    [21] K. Deb, A. Pratap, S. Agarwal and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm：NSGA-II, ” IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182－197, 2002.

    下載圖示
    QR CODE