簡易檢索 / 詳目顯示

回結果列表
研究生： 陳昱翰
Chen, Yu-Han
論文名稱： 以多目標蟻群最佳化演算法求解具時窗限制之越野定向問題
An Ant Colony Optimization Algorithm for the Multiobjective Orienteering Problem with Time Windows
指導教授： 蔣宗哲
Chiang, Tsung-Che
學位類別： 碩士
Master
系所名稱： 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年： 2015
畢業學年度： 103
語文別： 中文
論文頁數： 59
中文關鍵詞： 多目標蟻群最佳化演算法 、路徑重新鏈接 、具時窗限制之越野定向問題
論文種類： 學術論文
相關次數： 點閱：86  下載：1 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 時窗限制之越野定向問題 (Orienteering Problem with Time Windows, OPTW) 是由越野定向問題 (Orienteering Problem, OP) 增加時窗限制，同時也增加問題的難度，更加符合現實生活的情形。考慮到出遊往往有多人同行，針對每個景點所給予個人的感受有所不同，於是本論文將單目標的最佳化問題，發展成多目標時窗限制之越野定向問題 (Multiobjective Orienteering Problem with Time Windows, MOOPTW)，同時考量每個人對不同景點的評分，找出一群相對好的路線，由使用者來選擇。
    本論文將費洛蒙配置在每個權重方向上，費洛蒙的更新分為區域以及全域。區域更新:選擇到的路徑做更新，其餘路徑進行揮發，全域更新:權重方向上最好的路線做更新。區域搜尋採用路徑重新鏈接 (Path relinking) 以不同的鄰域函式，來提高搜尋的效能，並且比較不同的鄰域函式。本論文的方法與P-ACO [10] 套用本論文所使用的區域搜尋來比較。最後本論文列出目前所找到的多目標最佳解，使得日後能夠做比較。

    中文摘要 i 誌謝 ii 目錄 iii 附表目錄 v 附圖目錄 vi 第一章 緒論 1 1.1研究動機 1 1.2 問題定義 2 1.2.1 具時窗限制之越野定向問題 2 1.2.2 多目標具時窗限制之越野定向問題 4 1.3 蟻群最佳化演算法 5 1.4 研究範疇 7 1.5 論文架構 7 第二章 文獻探討 8 2.1 越野定向問題 8 2.2 具時窗限制之越野定向問題 9 2.3 多目標越野定向問題 (multi-objective orienteering problem, MOOP) 11 2.4 具時窗限制之團隊越野定向問題 (team orienteering problem with time windows, TOPTW) 13 2.4.1 模擬退火法 13 2.4.2 迭代區域搜尋法 14 2.4.3 蟻群最佳化演算法 14 2.5 MOEA/D-ACO 15 第三章 多目標蟻群最佳化演算法 MO-ACO 17 3.1 MO-ACO 17 3.1.1 參數介紹 17 3.1.2 演算法流程 18 3.2 區域搜尋 23 3.2.1 路線選擇機制 23 3.2.2 插入與刪除 27 第四章 實驗與分析 29 4.1 測試問題 29 4.2 效能指標 29 4.3 測試環境 30 4.4 參數設定 30 4.5 路線選擇機制 31 4.6 比較費洛蒙更新差異 34 4.7 生活實例 39 第五章 結論與未來展望 40 參考文獻 42 附錄 45

    [1] P. Vansteenwegen, W. Souffriau & D. V. Oudheusden, “The orienteering problem: A survey,” European Journal of Operational Research, vol. 209, issue 1, pp. 1-10, 2011.
    [2] M. Dorigo, Optimization, learning and natural algorithms, Ph.D. Thesis, Dipartimento di Elettronica, Politecnico di Milano, Italy, 1992.
    [3] K. Doerner, W. J. Gutjahr, R. F. Hartl, C. Strauss & C. Stummer, “Pareto ant colony optimization: A metaheuristic approach to multiobjective portfolio selection,” Annals of Operations Research, vol. 131, issue 1-4, pp. 79-99, 2004.
    [4] T. Tsiligirides, “Heuristic methods applied to orienteering,” The Journal of the Operational Research Society, vol. 35, no. 9, pp. 797-809, 1984.
    [5] B. L. Golden, L. Levy & R. Vohra, “The orienteering problem,” Naval Research Logistics, vol. 34, issue 3, pp. 307-318, 1987.
    [6] M. F. Tasgetiren & A. E. Smith, “A genetic algorithm for the orienteering problem,” Proceedings of IEEE Congress on Evolutionary Computation, vol. 2, pp. 910-915, 2000.
    [7] M. Verma, M. Gupta, B. Pal & K. K. Shukla, “A stochastic greedy heuristic algorithm for the orienteering problem,” 2014 International Conference on Computer and Communication Technology, pp. 59-65, 2014.
    [8] M. G. Kantor & M. B. Rosenwein, “The orienteering problem with time windows,” The Journal of the Operational Research Society, vol. 43, no. 6, pp. 629-635, 1992.
    [9] J. Karbowska-Chilinska & P. Zebielski, “Genetic algorithm with path relinking for the orienteering problem with time windows,” Fundamenta Informaticae - Concurrency Specification and Programming, vol. 135, issue 4, pp. 419-431, 2014.
    [10] J. Karbowska-Chilinska & P. Zebielski, “Genetic algorithm solving the orienteering problem with time windows,” Proceedings of the International Conference on Systems Science 2013, pp. 609-619, 2014.
    [11] M. Schilde, K. F. Doerner, R.F. Hartl & G.Kiechle, “Metaheuristics for the bi-objective orienteering problem,” Swarm Intelligence, vol. 3 issue 3, pp.179-201, 2009.
    [12] S. W. Lin & V. F. Yu, “A simulated annealing heuristic for the team orienteering problem with time windows,” European Journal of Operational Research, vol. 217, issue 1, pp. 94-107, 2012.
    [13] P. Vansteenwegen, W. Souffriau, G. V. Berghe & D. V. Oudheusden, “Iterated local search for the team orienteering problem with time windows,” Computers & Operations Research, vol. 36, issue 12, pp. 3281-3290, 2009.
    [14] R. Montemanni & L. M. Grambardella, “An ant colony system for team orienteering problems with time windows,” Foundations of Computing and Decision Sciences, vol. 34, issue 4, pp. 287-306, 2009.
    [15] Q. Zhang & H. Li, “MOEA/D: A multiobjective evolutionary algorithm based on decomposition,” IEEE Transactions on Evolutionary Computation, vol. 11, issue 6, pp. 712-731, 2007.
    [16] H. Li, D. Landa-silva & X. Gandibleux, “Evolutionary multi-objective optimization algorithms with probabilistic representation based on pheromone trails,” Proceedings of IEEE Congress on Evolutionary Computation, pp. 1-8, 2010.
    [17] L. Ke, Q. Zhang & R. Battiti, “MOEA/D-ACO：A multiobjective evolutionary algorithm using decomposition and ant colony,” IEEE Transactions on Cybernetics, vol. 43, issue 6, pp. 1845-1859, 2013.
    [18] Team orienteering problem with time windows instances. http://www.mech.kuleuven.be/en/cib/op/
    [19] G. Righini & M. Salani, “Dynamic programming for the orienteering problem with time windows,” Dipartimento di Technologie dell’Informazione, Universita degli Studi Milano, Crema, Italy, Tech. Rep. TR-91, 2006.
    [20] D. A. Van Veldhuizen & G. B. Lamont, “Multiobjective evolutionary algorithm research: A history and analysis,” Dept. Elec. Comput. Eng., Graduate School of Eng., Air Force Inst. Technol., Wright-Patterson, AFB, OH, Tech. Rep. TR-98-03, 1998.
    [21] Y. Qi, X. Ma, F. Liu, L. Jiao, J. Sun & J. Wu, “MOEA/D with Adaptive Weight Adjustment,” Evolutionary computation, vol. 22, no. 2, pp. 231-264, 2014.
    [22] S. N. Parragh & F. Tricoire, “Branch-and-bound for bi-objective integer programming,” Optimization online, 2015

    下載圖示
    QR CODE