以文化基因演算法求解具時窗之團隊越野競賽問題

Abstract

旅遊是現代人重要的休閒活動之一，除了參加旅行團規劃的旅程外，目前自助旅行可以自己規劃旅遊行程是相當熱門的旅遊方式。然而，從眾多熱門景點或自己有興趣的旅遊景點中，快速的規劃出一天或是多天的行程是一個相當困難的問題。我們可以將這個問題視為一種具時窗之團隊越野競賽問題(Team Orienteering Problem with Time Windows)。 具時窗之團隊越野競賽問題是越野競賽問題 (Orienteering Problem) 其中一種變型，給予許多地點，各個地點有分數、花費時間以及開始時間與結束時間的時間窗。從已知起點至終點在有限制的時間且不違反時窗限制下走訪各地點且找出需求的路徑數目，目標在求得的路徑中得到最大的分數總和。此篇論文提出以文化基因演算法的做法，首先以叢集的概念初始化族群，接著進入演化流程。本篇提出交配的方式並使用兩種適應值來比較可行解與不可行解。最後使用一般常用的路徑搜尋方式來改善族群。根據實驗結果在測試的問題集中，本篇的方法更新七個問題的最佳解。