以多目標蟻群最佳化演算法求解具時窗限制之越野定向問題

Abstract

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