- 學位論文
結合限制規劃法與螞蟻演算法求解運動排程問題
Combining Constraint Programming with Ant Colony Optimization to Solve Sports Scheduling Problem.
摘要
傳統人工安排運動排程的方式過程耗時且耗力。本研究提出實際美國職棒大聯盟運動排程問題之限制滿足最佳模式，目標值為所有球隊移動距離之加總。運動排程問題使屬於NP-complete問題，且美國職棒大聯盟運動排程問題賽制規則之複雜，而應用限制規劃法結合螞蟻演算法之整合式演算法，求解三種不同的運動排程問題：美國職棒大聯盟賽程問題、張文助(2005)提出之中華職棒大聯盟賽程問題及Goossens and Spieksma (2009)提出比利時足球聯盟賽程問題。本研究對大聯盟賽程問題求解後，所得到的總旅行距離較大聯盟現況減少3.92%，顯示出整合式演算法能確實能改進大聯盟現況總移動成本的目標值，最後提出結論與建議。
並列摘要
The arrangement of sports scheduling for each sport scheduling planner is a time consuming work. In this research, a constraint satisfaction problem (CSP) of Major League Baseball (MLB) scheduling with real world considerations is represented. The objective value of the proposed formulation is to minimize total travel distance of all teams in MLB. Since the sport scheduling problem is NP-complete, the CSP of MLB is hard to solve with consideration of rules of regulations of MLB. A combined algorithm which composed by constraint programming (CP) and ant colony system is proposed to solve the CSP of sport scheduling. Three different types of sports scheduling problem are tested by using the combined algorithm. The first one is MLB Scheduling problem, the second is Chinese Professional Baseball League Problem and the third is Belgian Soccer League scheduling. The test results show that the combined algorithm is advantageous over the current status of MLB with respect to the objective value.