簡易檢索 / 詳目顯示

回結果列表
研究生： 王維新
Wei-Hsin Wang
論文名稱： 以文化基因演算法求解大型多目標且具時窗限制之車輛路由問題
A Memetic Algorithm Solving Large Scale Multi-Objective Vehicle Routing Problem with Time Windows
指導教授： 蔣宗哲
Chiang, Tsung-Che
學位類別： 碩士
Master
系所名稱： 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年： 2014
畢業學年度： 102
語文別： 中文
論文頁數： 59
中文關鍵詞： 文化基因演算法 、區域搜尋法演算法 、具時窗車輛路由問題 、多目標最佳化 、共生關係
論文種類： 學術論文
相關次數： 點閱：199  下載：16 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 具時間窗車輛路由問題 (Vehicle Routing Problem with Time Windows, VRPTW) 為車輛路由問題(Vehicle Routing Problem)再加上時間窗限制，而車輛路由問題係為一個派車站派出多輛車輛服務顧客點，在生活實務上已經有相當廣泛的運用，包括宅配、垃圾回收車路線規劃、銀行運鈔車及定點巡邏車路線規劃。
    本論文以具時窗限制之車輛路由問題為主題，其求解目標為最小化車輛數和總行駛距離，由柏拉圖最佳化觀點求解，提出文化基因演算法的求解方法。此文化基因演算法採用共生關係，即為允許違反限制解存在於族群中，初始解產生時會產生合法解與違反限制解，再由基因演算法以多目標進行最佳化。基因演算法產生交配產生的子代會使用突變策略進行修復與改善，接著區域搜尋法對產生的子代進行目標的最佳化或是對族群的多樣性加以擾動，藉此產生的子代會依一定比例讓違反限制解存活於族群中。
    測試問題集是以Gehring與Homberger (1999)建立的200個顧客點大型問題集，問題集中有6大類共56個問題。本研究以多目標求解問題的過程中，探討不可行解存在於族群中對於文化基因演算法中族群演化造成的影響。

    誌 謝 I 中文摘要 II 目 錄 III 附圖目錄 V 附表目錄 VI 符號表 VII 第一章 緒論 1 1.1 車輛路由問題 1 1.2 具時間窗車輛路線問題的數學模型 2 1.3 多目標最佳化問題 4 1.4 研究目的研究方法 5 1.5 全文架構 6 第二章 文獻探討 8 2.1 建構式演算法 8 2.1.1 節省法 8 2.1.2 時間導向最近鄰點法 9 2.1.3 插入法 9 2.2 路線改善法 10 2.2.1 K-opt 10 2.2.2 2-opt* 11 2.2.3 Or-opt 11 2.2.4 -interchange 12 2.3 啟發式演算法 13 2.3.1 傳統時間窗車輛路線問題解法 13 2.3.2 兩階段求解時間窗車輛路線問題 14 2.3.3 違反限制 16 2.3.4 多目標求解時間窗車輛路線問題 17 2.3.5 特殊方法求解時間窗車輛路線問題 19 2.3.6 求解具時間窗大型車輛路由問題 24 第三章 方法與步驟 25 3.1 演算法架構 25 3.2 路線表示 26 3.3 基因演算法 27 3.3.1 建構初始族群 28 3.3.2 目標值 31 3.3.3 適應度 32 3.3.4 親代選擇 32 3.3.5 交配 33 3.3.6 區域搜尋法 35 3.3.7 修復 37 3.3.8 環境選擇 37 3.3.9 相似度與族群多樣性的維持 38 第四章 實驗數據與效能評比 40 4.1 測試問題 40 4.2 測試環境 41 4.3 比較文獻 41 4.4 效能指標 41 4.5 參數設定 41 4.6 實驗與討論 42 4.6.1 凌越關係與限定的凌越關係結果比較 43 4.6.2 不可行解存活率實驗參數設定結果比較 48 4.6.3 最佳結果比較 50 4.6.4 多目標最佳化結果比較 51 第五章 結論與未來發展 55 第六章 參考文獻 57

    [1] G.B. Dantzig, J.H. Ramser, “The truck dispatching problem,” Management Science, 6, 80–91, 1959.
    [2] B. M. Baker, M.A Ayechew, “A genetic algorithm for the vehicle routing problem,” Computers & Operations Research, 30, 787–800, 2003.
    [3] C. Prins, “A simple and effective evolutionary algorithm for the vehicle routing problem,” Computers & Operations Research, 31, 1985–2002, 2004.
    [4] O. Bräysy, M. Gendreau, “Vehicle routing problem with time windows, part I: route construction and local search algorithms,” Transportation Science, 39, 1, 104-118, 2005.
    [5] 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, 15, pp. 281–295, 2001.
    [6] G.F. King, and C.F. Mast, “Excess travel: causes, extent and consequences”, Transportation Research Record, 1111, 126134, 1997.
    [7] T.G. Crainic, and G. Laporte, “Planning models for freight transportation”, European Journal of Operational Research, 97, 409438, 1997.
    [8] T. Vidal, T. G. Crainic, M. Gendreau, C. Prins, “A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows”, Computers & Operations Research, 40, 475-489, 2013.
    [9] T. C. Chiang and W. H. Hsu, “A knowledge-based evolutionary algorithm for the multiobjective vehicle routing problem with time windows,” Computers & Operations Research, 45, 25-37, 2014.
    [10] M. M. Solomon, “Algorithms for the vehicle routing and scheduling problems with time window constraints,” Operations Research, 35, 2, 254–265, 1987.
    [11] T. Vidal, T. G. Crainic, M. Gendreau, N. Lahrichi, W. Rei, “A hybrid genetic algorithm for multi-depot and periodic vehicle routing problems”, Operations Research, 60, 3, 61124, 2012.
    [12] J.-Y. Potvin, J.-M. Rousseau, “An exchange heuristic for routeing problems with time windows,” Journal of the Operational Research Society, 46, 1433–1446, 1995.
    [13] I. Or, “Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking,” Ph.D. thesis, Northwestern University, Evanston, IL, 1976.
    [14] J.-Y. Potvin, T. Kervahut, Bruno-Laurent, Jean-Marc Rousseau, “The vehicle routing problem with time windows part I: tabu search,” Journal on Computing, 8, 2, 158–164, 1996.
    [15] J.-Y. Potvin, S. Bengio, “The vehicle routing problem with time windows part II: genetic search,” Journal on Computing, 8, 2, 165–172, Spring 1996.
    [16] J. Homberger, and H. Gehring, “Two evolutionary metaheuristics for the vehicle routing probloem with time windows,” Information Systems and Operational Research, 37, 297–318, 1999.
    [17] R. Bent, P.V. Hentenryck, “A two-stage hybrid local search for the vehicle routing problem with time windows,” Transportation Science, 38, 4, 515–530, 2001.
    [18] A. Lim and X. Zhang, “A two-stage heuristic with ejection pools and generalized ejection chains for the vehicle routing problem with time windows, ”Journal on Computing, 19, 3, 443–457, 2007.
    [19] 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, 41 179–194. 2003.
    [20] 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, 34, 115–151, 2006.
    [21] A. Garcia-Najera, J. A. Bullinaria, “An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows,” Computer & Operations Research, 38, 287–300, 2011.
    [22] O. Bräysy, “A reactive variable neighborhood search for the vehicle routing problem with time windows,” Journal on Computing, 15, 4, 347–368, 2003.
    [23] 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, 159, 586–605, 2004.
    [24] O. Bräysy, “Fast local searches for the vehicle routing problem with time windows,” Information Systems and Operations Research, 41, 179–194, 2003.
    [25] M.M. Solomon, E.K. Baker and J.R. Schaffer, “Vehicle routing and scheduling problems with time window constraints: efficient implementations of solution improvement procedures”, In B. Golden and A. Assad (eds.). Vehicle Routing: Methods and Studies, Elsevier Science Publishers, Amsterdam, 85–106, 1988.
    [26] J. Chunlin, “A revised particle swarm optimization approach for multi-objective and multi-constraint optimization,” Proceedings of the Genetic and Evolutionary Computation Conference, GECCO’2004, 2004 June 26–30, Springer, Seattle, Washington, Berlin, 2004.
    [27] H. Gehring, and J. Homberger, “A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows,” K. Miettinen, M. Mäkelä, J. Toivanen, eds. Proc. EUROGEN99, University of Jyväskylä, Finland, 57–64, 1999.
    [28] K. Deb, A. Pratap, S. Agarwal and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm：NSGA-II, ” IEEE Transactions on Evolutionary Computation, 6, 2, 182－197, 2002.
    [29] 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, 37, 297－318, 1999
    [30] Y. Nagata, O. Bräysy, and W. Dullaert, “A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows,” Computers & Operations Research, 37, 4, 724–737, 2010.
    [31] H. Gehring and J. Homberger, “A parallel two-phase metaheuristic for routing problems with time windows,” Asia-Pacific Journal of Operational Research, 18, 35–47, 2001.

    QR CODE