研究生: |
孫偉儒 |
---|---|
論文名稱: |
以文化基因演算法求解具時窗之團隊越野競賽問題 A Memetic Algorithm for Team Orienteering Problem with Time Windows |
指導教授: | 蔣宗哲 |
學位類別: |
碩士 Master |
系所名稱: |
資訊工程學系 Department of Computer Science and Information Engineering |
論文出版年: | 2015 |
畢業學年度: | 103 |
語文別: | 中文 |
論文頁數: | 39 |
中文關鍵詞: | 文化基因演算法 、具時窗之團隊越野競賽問題 |
論文種類: | 學術論文 |
相關次數: | 點閱:104 下載:4 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
旅遊是現代人重要的休閒活動之一,除了參加旅行團規劃的旅程外,目前自助旅行可以自己規劃旅遊行程是相當熱門的旅遊方式。然而,從眾多熱門景點或自己有興趣的旅遊景點中,快速的規劃出一天或是多天的行程是一個相當困難的問題。我們可以將這個問題視為一種具時窗之團隊越野競賽問題(Team Orienteering Problem with Time Windows)。
具時窗之團隊越野競賽問題是越野競賽問題 (Orienteering Problem) 其中一種變型,給予許多地點,各個地點有分數、花費時間以及開始時間與結束時間的時間窗。從已知起點至終點在有限制的時間且不違反時窗限制下走訪各地點且找出需求的路徑數目,目標在求得的路徑中得到最大的分數總和。此篇論文提出以文化基因演算法的做法,首先以叢集的概念初始化族群,接著進入演化流程。本篇提出交配的方式並使用兩種適應值來比較可行解與不可行解。最後使用一般常用的路徑搜尋方式來改善族群。根據實驗結果在測試的問題集中,本篇的方法更新七個問題的最佳解。
[1] Golden, B., Levy, L., Vohra, R. ”The orienteering problem, ”Naval Research Logistics 34, 1987, 307–318.
[2] Vansteenwegen, P., Souffriau, W., Van Oudheusden, D. ”The Orienteering Problem:A survey,” European Journal of Operational Research, 2011, 209(1) ,1–10.
[3] Gavals, D., Konstantopoulos, C., Mastakas, K., Pantziou, G. ”A survey on algorithmic approaches for solving tourist trip design problems.” Journal of Heuristics, 20 (3), 2014, 291-328.
[4] Vansteenwegen, P., Souffriau, W., Vanden Berghe, G., Van Oudheusden, D. ”Iterated local search for the team orienteering problem with time windows,” Computers & Operations Research, 36 (12), 2009, 3281-3290.
[5] Labadie, N., Melechovský, J., Calvo, RW. ”Hybridized evolutionary local search algorithm for the team orienteering problem with time windows. Journal of Heuristics, 17 (6), 2011, 729-753.
[6] Gavalas, D., Konstantopoulos, C., Mastakas, K., Pantziou, G., Tasoulas, Y. “Cluster-based heuristics for team orienteering problem with time windows,” in Experimental Algorithms, 7933, 2013, 390-401.
[7] Hu, Q., Lim, A. “An iterative three-component heuristic for the team orienteering problem with time windows,” European Journal of Operational Research, 232 (2), 2014, 276-286.
[8] Lin, SW., Yu, VF. “A simulated annealing heuristic for the team orienteering problem with time windows,” European Journal of Operational Research, 217 (1), 2012, 94-107.
[9] Nesrine Guibadj, R., Moulrim, A. “Memetic algorithm with efficient split procedure for the team orienteering problem with time windows,” in Artificial Evolution, 2014, 183-194.
[10] Bouly, H., Dang, D.C., Moukrim, A. “A memetic algorithm for the team orienteering problem,” 4OR, 8(1), 2010, 49-70.
[11] Karbowska-Chilinska, J., Zabielski, P. “Genetic algorithm with path relinking for the orienteering problem with time windows,” Proceedings of the 22nd International Workshop on Concurrency, Specification and Programming 2013, 2014, 419-431.
[12] Glover, F.: “A Template for Scatter Search and Path Relinking,” in Artificial Evolution, 1363, 1997, 13-54.
[13] Souffriau, W., Vansteenwegen, P., Vanden Berghe, G., Van Oudheusden, D. “A Path Relinking approach for the Team Orienteering Problem,” Computers & Operations Research 37, 2010, 1853 – 1859.
[14] Xie, J., Shuai, J. “A Simple and Fast Algorithm for Global K-means Clustering,” in Proc. 2nd Int. Workshop ETCS, 2010, 36-40.
[15] Nagata, Y., Bräysy, O., Dullaert, W. “A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows,” Computers & Operations Research 37, 2010, 724-737.
[16] Schneider, M.,Sand, B.,Stenger, A. “A note on the time travel approach for handling time windows in vehicle routing problems,” Computers & Operations Research 40, 2013, 2564-2568.
[17] Montemanni R, Gambardella L. “Ant colony system for team orienteering problems with time windows,” Foundations of Computing and Decision Sciences, 34(4), 2009, 287–306.
[18] Solomon M. “Algorithms for the vehicle routing and scheduling problem with time window constraints,” Operations Research 35, 1987, 254–65.
[19] Cordeau J-F, Gendreau M, Laporte G. 1997. A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks 30, 105–19.