簡易檢索 / 詳目顯示

研究生: 孫偉儒
論文名稱: 以文化基因演算法求解具時窗之團隊越野競賽問題
A Memetic Algorithm for Team Orienteering Problem with Time Windows
指導教授: 蔣宗哲
學位類別: 碩士
Master
系所名稱: 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年: 2015
畢業學年度: 103
語文別: 中文
論文頁數: 39
中文關鍵詞: 文化基因演算法具時窗之團隊越野競賽問題
論文種類: 學術論文
相關次數: 點閱:96下載:4
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 旅遊是現代人重要的休閒活動之一,除了參加旅行團規劃的旅程外,目前自助旅行可以自己規劃旅遊行程是相當熱門的旅遊方式。然而,從眾多熱門景點或自己有興趣的旅遊景點中,快速的規劃出一天或是多天的行程是一個相當困難的問題。我們可以將這個問題視為一種具時窗之團隊越野競賽問題(Team Orienteering Problem with Time Windows)。
    具時窗之團隊越野競賽問題是越野競賽問題 (Orienteering Problem) 其中一種變型,給予許多地點,各個地點有分數、花費時間以及開始時間與結束時間的時間窗。從已知起點至終點在有限制的時間且不違反時窗限制下走訪各地點且找出需求的路徑數目,目標在求得的路徑中得到最大的分數總和。此篇論文提出以文化基因演算法的做法,首先以叢集的概念初始化族群,接著進入演化流程。本篇提出交配的方式並使用兩種適應值來比較可行解與不可行解。最後使用一般常用的路徑搜尋方式來改善族群。根據實驗結果在測試的問題集中,本篇的方法更新七個問題的最佳解。

    誌謝 I 中文摘要 II 目錄 III 附圖目錄 V 附表目錄 VI 符號表 VII 第一章 緒論 1 1.1 研究背景與動機 1 1.2 具時窗之團隊越野競賽問題 2 1.3 研究目的、方法與貢獻 4 1.4 全文架構 4 第二章 文獻探討 5 2.1 具時窗之團隊越野競賽問題 5 2.1.1 直接路徑表示法 5 2.1.2 數列表示法 7 2.2 越野競賽其他種類問題 8 第三章 文化基因演算法 10 3.1 基因演算法 10 3.1.1 染色體表示方式 11 3.1.2 族群與個體的初始化 (CInsert) 11 3.1.3 適應值 14 3.1.4 親代選擇與交配 16 3.1.5 環境選擇 20 3.1.6 突變 20 3.2 GAVND 21 3.3 文化基因演算法 22 第四章 實驗分析 24 4.1 測試問題 24 4.2 比較文獻 24 4.3 預期實驗及參數設定 25 4.3.1 初始化比較 25 4.3.2 接受不可行解與懲罰值 27 4.3.3 VND與GAVND 29 4.3.4 參數設定 30 4.3.5 Insertion隨機挑選 30 4.4 效能評比 33 第五章 結論與未來發展 35 參考文獻 37

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

    下載圖示
    QR CODE