研究生: |
王維新 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 |
中文關鍵詞: | 文化基因演算法 、區域搜尋法演算法 、具時窗車輛路由問題 、多目標最佳化 、共生關係 |
論文種類: | 學術論文 |
相關次數: | 點閱:220 下載:16 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
具時間窗車輛路由問題 (Vehicle Routing Problem with Time Windows, VRPTW) 為車輛路由問題(Vehicle Routing Problem)再加上時間窗限制,而車輛路由問題係為一個派車站派出多輛車輛服務顧客點,在生活實務上已經有相當廣泛的運用,包括宅配、垃圾回收車路線規劃、銀行運鈔車及定點巡邏車路線規劃。
本論文以具時窗限制之車輛路由問題為主題,其求解目標為最小化車輛數和總行駛距離,由柏拉圖最佳化觀點求解,提出文化基因演算法的求解方法。此文化基因演算法採用共生關係,即為允許違反限制解存在於族群中,初始解產生時會產生合法解與違反限制解,再由基因演算法以多目標進行最佳化。基因演算法產生交配產生的子代會使用突變策略進行修復與改善,接著區域搜尋法對產生的子代進行目標的最佳化或是對族群的多樣性加以擾動,藉此產生的子代會依一定比例讓違反限制解存活於族群中。
測試問題集是以Gehring與Homberger (1999)建立的200個顧客點大型問題集,問題集中有6大類共56個問題。本研究以多目標求解問題的過程中,探討不可行解存在於族群中對於文化基因演算法中族群演化造成的影響。
[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, 126134, 1997.
[7] T.G. Crainic, and G. Laporte, “Planning models for freight transportation”, European Journal of Operational Research, 97, 409438, 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, 61124, 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.