簡易檢索 / 詳目顯示

研究生: 翁仁一
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個最佳解。

    中文摘要 i 誌 謝 ii 目 錄 iii 附表目錄 v 附圖目錄 v 第一章 緒論 1 1.1 研究背景 1 1.2 問題定義 1 1.3 研究主軸 4 第二章 文獻探討 5 2.1 精確演算法 (exact algorithms) 5 2.2 路由建構法 (route construction method) 5 2.3 路由改善法 (route improvement method) 7 2.3.1 2-opt 7 2.3.2 Or-opt 8 2.3.3 2-opt* 9 2.3.4 CROSS-exchange 10 2.4 啟發式演算法 (metaheuristics) 11 2.4.1 禁忌搜尋法 11 2.4.2 基因演算法 12 2.5 從多目標問題的觀點 13 2.5.1 發現兩個解題目標的衝突性 13 2.5.2 新的交配運算與解的表示法 13 2.5.3 解的相似度指標和族群的發散程度 14 2.5.4 改善現有的交配和突變 14 2.5.5 考慮車輛載重的不平衡 15 2.6 其他相關的重要文獻 16 2.6.1 使用ejection pool的概念以減少車輛數 16 2.6.2 一併解決相關的VRPTW問題 16 2.7 限制處理 (constraint handling) 17 2.8 綜合比較 18   第三章 限制多目標演化演算法 19 3.1 解的表示法 19 3.2 初始族群 (initial population) 的產生 19 3.3 親代的選擇 (parent selection) 20 3.4 交配 (crossover) 21 3.4.1 交換路由 21 3.4.2 減少路由 21 3.5 突變 (mutation) 22 3.6 環境的選擇 (environmental selection) 23 第四章 實驗數據與效能評比 25 4.1 測試問題集 25 4.2 效能指標 25 4.3 比較對象 26 4.4 實驗與觀察 26 4.4.1 選擇親代解的策略 26 4.4.2 選擇最佳路線的策略 28 4.4.3 刪除最差路線的策略 29 4.4.4 與目前最佳解的比較 30 4.4.5 與原本MOEA-EO的比較 32 第五章 結論與未來發展 34 參考文獻 35

    [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.

    下載圖示
    QR CODE