研究生: |
許巍懷 |
---|---|
論文名稱: |
以混合演化式演算法求解多目標且具時窗限制之車輛路由問題 A Hybrid Multiobjective Evolutionary Algorithm for the Vehicle Routing Problem with Time Windows |
指導教授: | 蔣宗哲 |
學位類別: |
碩士 Master |
系所名稱: |
資訊工程學系 Department of Computer Science and Information Engineering |
論文出版年: | 2011 |
畢業學年度: | 99 |
語文別: | 中文 |
論文頁數: | 50 |
中文關鍵詞: | 基因演算法 、禁忌搜尋法 、時窗車輛路由問題 、多目標最佳化 |
論文種類: | 學術論文 |
相關次數: | 點閱:178 下載:14 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
車輛路由問題旨在尋求車輛與客戶之間最佳分配與移動路線,在已知客戶需求 (如運送量和服務時窗限制) 和車輛容量的情況下,由派車站發車前往服務客戶,最後返回派車站。車輛路由問題在實務上已有廣泛應用,如物品宅配、校車動線、計程車載客、銀行運鈔車補給、郵務信件遞送等等。
本論文以具時窗限制之車輛路由問題為主題,其求解目標為最小化車輛數和總行駛距離,由柏拉圖最佳化觀點求解,提出一混合基因演算法和禁忌搜尋的求解方法。初始解經由禁忌搜尋將目標專於車輛數目最小化,再由基因演算法以多目標進行最佳化。並以改良式的交配和突變策略增加解的品質;在演化一定代數後由禁忌搜尋法對族群中非凌越解集進行深度搜尋以最小化行駛距離。
測試問題集是Solomon建立的6大類共56個問題。本研究以多目標求解問題,對於文獻所提出的67個近似最佳解集合更新了34個,另外有2大類的問題可以達到車輛數與總距離的最佳解。
[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.