【論文摘要】應用病毒最佳化演算法求解旅遊規劃問題

10.29893/NCUTMAN.201811.0008

梁韵嘉；陳香伶；陳慧芝

旅遊行程規劃問題 ； 雙目標具時窗之越野定向問題 ； 病毒最佳化演算法

管理學術研討會

第十六屆（2018 / 11 / 01）

45 - 45

繁體中文

旅遊行程規劃問題（Tourist Trip Design Problem；TTDP）可歸類為具時窗（Time Window）的越野定向問題（Orienteering Problem；OP），在越野定向問題中，競賽者不像旅行推銷員需要拜訪所有節點，只需要在限定的時間內極大化收集到的分數即可。一般而言，旅遊通常都是團體行動，在安排行程的時候，同一個景點可能會因為參與者興趣或預算等因素導致不同人會有不一樣的喜好度。在傳統的具時窗的越野定向問題中，每個景點都僅給定一個分數，也可以說是獲益值或偏好值，而為了符合實際情況，本研究將具時窗越野定向問題擴展成雙目標（Bi-Objective）的具時窗越野定向問題。雙目標具時窗越野定向問題由於必須同時滿足兩種目標，兩種目標間的相對重要性不容易比較，故使用柏拉圖最佳解前緣法（Pareto Front）找出一群相對好的路線，讓使用者自行選擇。本研究使用一新穎的萬用啟發式演算法（Metaheuristic）─病毒最佳化演算法（Virus Optimization Algorithm；VOA）求解此具時窗的雙目標越野定向問題，並利用經過修改後的Solomon及Cordeau共76題測試例題進行驗證，最後並將本論文的方法與Chen等學者於2015發表之文獻中，使用蟻群最佳化演算法（Ant Colony Optimization；ACO）的結果進行比較。病毒最佳化演算法在c和r類的題型2表現較佳；rc類不管是題型1或題型2和pr類問題表現普遍較蟻群最佳化演算法為佳。