研究生: |
翁仁一 Ren-Yi Wong |
---|---|
論文名稱: |
以限制多目標演化演算法求解具時窗限制之車輛路由問題 A Constrained Multiobjective Evolutionaary Algorithm for the Vehicle Routing Problem with Time Windows |
指導教授: |
蔣宗哲
Chiang, Tsung-Che |
學位類別: |
碩士 Master |
系所名稱: |
資訊工程學系 Department of Computer Science and Information Engineering |
論文出版年: | 2013 |
畢業學年度: | 101 |
語文別: | 中文 |
論文頁數: | 36 |
中文關鍵詞: | 多目標最佳化 、演化式演算法 、時窗限制車輛路由問題 、限制處理 |
論文種類: | 學術論文 |
相關次數: | 點閱:184 下載:18 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
「時窗限制車輛路由問題 (Vehicle Routing Problem with Time Windows, VRPTW)」在原有的車輛路由問題 (Vehicle Routing Problem, VRP) 上增添時間的限制,增加了題目的難度,但也更符合現實生活中的需求。此問題的研究已有20多年歷史。過去的精確演算法對於如此困難的問題,往往不能求解規模龐大的輸入。近年許多研究偏好採用多目標最佳化的方式解決,但因此問題的時窗限制較難修復,較少人會提及不合法解的處理。
本研究修改自現有的MOEA-EO [14]。在交換最佳的路由時,總是選擇客戶數目最多的,以祈刪除最多的客戶以減少路由數目。在限制處理上,環境的選擇會依據解的合法性,使用不同的凌越關係來分級。合法的解會使用傳統的解題目標來分級,不合法的解會使用限制的違反量來分級。最後會以交互的方式篩選出可以存活到下一代的個體,適當保留不合法的個體以增加搜尋的廣度。
本演算法對於客戶數目較少的問題已有不錯的表現。在Solomon 25個客戶的問題中,更新了9個最佳解。
[1] Lin Tian, “Analysis of the Degree of Difficulty in Solving Vehicle Routing Problem with Time Windows,” in Proceedings of 6th International Conference on Internet Computing for Science and Engineering, pp.51–54, 2012.
[2] É. Taillard et al., “A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows,” Transportation Science, vol.31, no.2, pp.170–186, 1997.
[3] A.W.J. Kolen, A.H.G. Rinnooy Kan, and H.W.J.M. Trienekens, “Vehicle Routing with Time Windows,” Operations Research, vol.35, no.2, pp.266–273, 1987.
[4] M. Desrochers, J. Desrosiers, and M. Solomon, “A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows,” Operations Research, vol.40, no.2, pp.342–354, 1992.
[5] M.M. Solomon, “Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints,” Operations Research, vol.35, no.2, pp.254–265, 1987.
[6] S. Lin, “Computer Solutions of the Traveling Salesman Problem,” Bell System Technical Journal, vol.44, pp.2245–2269, 1965.
[7] 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.
[8] J.Y. Potvin, T. Kervahut, B.L. Garcia, and J.M. Rousseau, “The Vehicle Routing Problem with Time Windows—Part I: Tabu Search,” INFORMS Journal on Computing, vol.8, no.2, pp.158–164, 1996.
[9] J.Y. Potvin, J.M. Rousseau, “An Exchange Heuristic for Routing Problems with Time Windows,” Journal of the Operational Research Society, vol.46, no.12, pp.1433–1446, 1995.
[10] J.Y. Potvin, S. Bengio, “The Vehicle Routing Problem with Time Windows—Part II: Genetic Search,” INFORMS Journal on Computing, vol.8, no.2, pp.165–172, 1996.
[11] K.C. Tan, Y.H. Chew, and L.H. Lee, “A Hybrid Multiobjective Evolutionary Algorithm for Solving Vehicle Routing Problem with Time Windows,” Computational Optimization and Applications, vol.34, no.1, pp.115–151, 2006.
[12] B. Ombuki, B.J. Ross, and F. Hanshar, “Multi-Objective Genetic Algorithms for Vehicle Routing Problem with Time Windows,” Applied Intelligence, vol.24, pp.17–30, 2006.
[13] A. Garcia-Najera, J.A. Bullinaria, “An Improved Multi-objective Evolutionary Algorithm for the Vehicle Routing Problem with Time Windows,” Computers & Operation Research, vol.38, no.1, pp.287–300, 2011.
[14] W.H. Hsu, T.C. Chiang, “A Multiobjective Evolutionary Algorithm with Enhanced Reproduction Operators for the Vehicle Routing Problem with Time Windows,” in Proceedings of IEEE World Congress on Computational Intelligence (WCCI), 2012.
[15] R. Baños et al., “A Hybrid Meta-heuristic for Multi-objective Vehicle Routing Problems with Time Windows,” Computers & Industrial Engineering, vol.65, no.2, pp.286–296, 2013.
[16] Y. Nagata, O. Bräysy, “A Powerful Route Minimization Heuristic for the Vehicle Routing Problem with Time Windows,” Operations Research Letters, vol.37, no.5, pp.333–338, 2009.
[17] T. Vidal et al., “A Hybrid Genetic Algorithm with Adaptive Diversity Management for a Large Class of Vehicle Routing Problems with Time-windows,” Computers & Operations Research, vol.40, no.1, pp.475–489, 2013.
[18] M.N. Hsieh, T.C. Chiang, and L.C. Fu, “A Hybrid Constraint Handling Mechanism with Differential Evolution for Constrained Multiobjective Optimization,” in Proceedings of IEEE Congress on Evolutionary Computation (CEC), pp.1785–1792, 2011.
[19] M. Asafuddoula, T. Ray, R. Sarker, “Evaluate till you Violate: A Differential Evolution Algorithm Based on Partial Evaluation of the Constraint Set,” in Proceedings of IEEE Symposium on Differential Evolution (SDE), pp.31–37, 2013.
[20] Y. Nagata, O. Bräysy, W. Dullaert, “A Penalty-based Edge Assembly Memetic Algorithm for the Vehicle Routing Problem with Time Windows,” Computers & Operations Research, vol.37, no.4, pp.724–737, 2010.
[21] S.W. Lin et al., “A Hybrid Approach for Vehicle Routing Problem with Time Windows,” Advances in Intelligent Transportation Systems, vol.1, no.1, pp.11–18, 2012.
[22] J. Homberger, H. Gehring, “A Two-phase Hybrid Metaheuristic for the Vehicle Routing Problem with Time Windows,” European Journal of Operation Research, vol.162, no.1, pp.220–238, 2005.