結合限制規劃法與螞蟻演算法求解運動排程問題; Combining Constraint Programming with Ant Colony Optimization to Solve Sports Scheduling Problem.

NCU Institutional Repository > 工學院 > 土木工程研究所 > 博碩士論文 > Item 987654321/47434

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/47434

题名:	結合限制規劃法與螞蟻演算法求解運動排程問題;Combining Constraint Programming with Ant Colony Optimization to Solve Sports Scheduling Problem.
作者:	蔡政諭;Cheng-yu Tsai
贡献者:	土木工程研究所
关键词:	限制規劃;美國職棒大聯盟;運動排程;中華職棒大聯盟;螞蟻演算法;constraint programming;Chinese Professional Baseball League;sports scheduling problem;ant colony optimization;major league baseball
日期:	2011-08-25
上传时间:	2012-01-05 11:11:00 (UTC+8)
摘要:	傳統人工安排運動排程的方式過程耗時且耗力。本研究提出實際美國職棒大聯盟運動排程問題之限制滿足最佳模式，目標值為所有球隊移動距離之加總。運動排程問題使屬於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.
显示于类别:	[土木工程研究所] 博碩士論文

文件中的档案:

档案	描述	大小	格式	浏览次数
index.html		0Kb	HTML	709	检视/开启

在NCUIR中所有的数据项都受到原著作权保护.

社群 sharing

数据加载中.....