以多目標與限制最佳化觀點求解競賽旅程問題

Abstract

運動時間表問題 (Sport Timetabling Problem) 一直以來都是一個相當困難的問題，其影響的因素五花八門，像是運動員的需求、場館間的距離、商業和廣告的考量等等。其中針對球隊旅行產生了競賽旅程問題 (Traveling Tournament Problem)，本論文針對這樣的問題做研究。該問題原本為一個單目標最佳化問題，本論文將此問題發展為多目標最佳化問題，藉由此方式讓使用者能夠有多元的選擇，例如選擇一個總距離並非最短，但是能讓所有的隊伍移動距離較為平均的解。 本論文提出群體式多鄰域模擬退火法 (Population-based Multi Neighborhood Simulated Annealing, PMNSA) ，其中使用變動鄰域搜尋法 (Variable Neighborhood Search) 與隨機選擇鄰域函式做比較，希望能找到一種效能較好的做法，接著使用模擬退火法 (Simulated Annealing) 以及群體式的 (population-based) 概念去搜尋，另外也改良過去競賽旅程問題所使用的鄰域函式，並比較其改良前後搜尋解空間的能力，藉由此方式提高搜尋的效能。在限制處理機制的部分採用原先單目標常用的懲罰函數 (penalty function) 以及ϵ-constraint做比較，並找到一個最適合此多目標最佳化問題的限制處理機制。最後本論文列出目前找到的多目標最佳解，以供之後做比較。