臺灣博碩士論文加值系統

運動排程問題在這篇研究中被定義成路徑規劃問題，利用啟發式演算法建構有效率且符合賽制之賽程表。我們並以美國職棒大聯盟賽程表排程為例，收集相關文獻後，對此個案進行資料蒐集且深入研究，建立賽程表排程路徑規劃模式，期望所產出之賽程表能降低整個球季間球隊的總移動距離，及減低因球隊間移動距離差異過大造成賽程的公平性問題。
本研究以美國職棒大聯盟2009年至2011年賽程表作為比較實例，包含30個球隊一年共2430場賽事的安排，總求解時間約為4.2小時。產出之賽程表比美國職棒大聯盟近三年球季的平均總移動距離減少了約14.7萬公里，當中有23支球隊降低了每年的移動距離。此外，我們成功地降低移動距離最長與最短的球隊之間的差距達36%，減少了移動距離差異過大之不公平的問題，我們期望此系統可作為美國職棒大聯盟賽程安排之決策支援系統，將來亦可擴展應用範圍至世界各國職業運動賽程排程規劃與決策。

The scope of this study is on planning an optimal schedule for professional sports game. We take the MLB as an example to construct an effective schedule by a heuristic algorithm which meets the league rules. After collecting the references, we proceed to gather the information and to research it deeply for this case. We design the pattern for planning the schedules, and organize the related statistic reports about the scheduling. Finally, we estimate the results and analyze the targets. We expect to reduce the total moving distance of the MLB and make the schedule of the MLB fairer.
This research applies the contests scheduling of year 2009 to 2011 of the MLB as a case study. It takes 4.2 hours to get the solution. The output of our system is shorter than the average moving distance of the MLB in recent 3 years by 147,000 km, and 23 out of the 30 teams can reduce their moving distances in the season. Moreover, the ratio between the two teams with the longest moving distance to the shortest moving distance is reduced by 36 %. That is, our approach makes the schedule fairer. We expect that this research can be used to establish the schedule decision support system for the MLB, and for other professional sports games around the world.

中文摘要 I
英文摘要 II
目錄 IV
圖目錄 VI
表目錄 VII

第一章 導論 1
1.1研究背景 1
1.2研究範圍 2
1.3系統架構與研究流程 2
第二章 文獻回顧 6
2.1排程議題探討 6
2.2排程優化演算法探討 9
2.2.1整數規劃法 10
2.2.2啟發式演算法 10
2.2.3限制規劃法 11
2.3基因演算法介紹 12
第三章 系統架構 20
3.1演算法之整體架構 20
3.2賽程初始化 25
3.3改良型基因交配 30
3.4改良型基因突變 34
3.5賽程輸出 37
第四章 模擬結果與數據分析 40
4.1實驗設計與評估方式簡介 40
4.2實驗結果分析 42
第五章 結論與未來研究方向 51
5.1結論 51
5.2未來發展與研究方向 52
參考文獻 55
附錄 59
附錄一：2011年MLB球場距離表 59
附錄二：系統產出最佳化賽程表 62
附錄三：英文論文 85

圖目錄
圖1.1系統架構圖 3
圖1.2研究流程圖 5
圖2.1輪盤法 16
圖2.2競爭式選擇 16
圖2.3單點交配範例 17
圖2.4雙點交配範例 17
圖2.5突變範例 18
圖2.6基因演算法優缺點比較圖 19
圖3.1距離測量工具 21
圖3.2演算法步驟架構圖 23
圖3.3初始賽程產出步驟 26
圖3.4賽程表編碼 29
圖3.5暫存賽程表編碼 29
圖3.6輪盤法比較圖 31
圖3.7基因交換方法 32
圖3.8母代基因交配過程 33
圖3.9選擇性的順序導向突變 34
圖3.10基因突變方法 35
圖3.11賽程表突變過程 36
圖3.12賽程表產出決策過程 38
圖3.13演算法過程 39
圖4.1突變率目標值比較圖 44
圖4.2本研究與2009-2011年官方MLB賽季移動距離比較圖 46
圖5.1賽程優化系統發展藍圖 54

表目錄
表2.1循環賽賽程表 7
表2.2賽程表排程問題文獻比較 9
表2.3演算法比較 12
表3.1硬性限制參數表 27
表3.2軟性限制參數表 28
表3.3突變成果模擬數據比較表 36
表3.4賽程表突變結果 37
表4.1軟體開發環境 40
表4.2硬體環境 41
表4.3球隊代碼表 42
表4.4各突變值的數據結果表 43
表4.5突變率0.1%數據表 45
表4.6本研究與官方各球隊賽季移動距離比較表 47
表4.7球隊最長與最短移動距離比例表 48
表4.8乘坐飛機碳排放量計算公式表 49
表4.9相關研究比較表 50

1.台灣棒球維基館http://twbsball.dils.tku.edu.tw/wiki/index.php
2.Bean, J. C. and Birge, J. R. (1980), “Reducing Travelling Costs and Player Fatigue in the National Basketball Association,” Interfaces, Vol. 10, pp. 98-102.
3.Saltzman, R. M. and Bradford, R. M. (1996), “Optimal Realignments of the Teams in the National Football League,” European Journal of Operational Research, Vol. 93, pp. 469-475.
4.Rasmussen, R. V. and Trick, M. A. (2008), “Round robin scheduling - A survey,” Eur. J. Oper. Res., v188, pp. 617-636.
5.Nemhauser, G.L. and Trick M.A. (1998), “Scheduling a Major College Basketball Conference,” Operations Research, Vol. 46, No. 1, pp. 1-8.
6.Costa, D. (1995), “An Evolutionary Tabu Search Algorithm and the NHL Scheduling Problem,” INFOR. Ottawa, Vol. 33, No. 3, pp. 161-179.
7.Yang, J.T., Huang, H.D. and Horng, J.T. (2002), “Devising a cost effective baseball scheduling by evolutionary algorithms”, Proceedings of Evolutionary Computation 2002, Honolulu, HI, USA, pp. 1660-1665.
8.張文助(2005)，「以限制規劃構建運動排程模式-以中華職棒大聯盟賽程表排程為例」，國立交通大學運輸科技與管理學系研究所碩士論文，民國九十四年六月。
9.Kyngas, J. and Nurmi, K. (2009), “Scheduling the Finnish major ice hockey league”, Proceedings of Computational Intelligence in Scheduling 2009, Nashville, TN, pp. 84-89.
10.Croce, F.D. and Oliveri, D. (2006), “Scheduling the Italian football league: An ILP-based approach”, Computers and Operations Research, 33(7), pp. 1963-1974.
11.Potvin, J.Y. and Laporte, G. (1996), “Genetic Algorithm for the Traveling Salesman Problem”, Annals of Operations Research. Vol. 63, pp.339-370.
12.Johnson, D. S., Papadimitriou, C. H. and Yannakakis, M. (1988), ‘‘How easy is local search?,’’ J. Comput. System Sci. 37, pp. 79-100.
13.柯惠雯(2001)，「結合模擬退火法與禁忌搜尋法在流程式生產排程之應用」，私立大葉大學工業工程研究所碩士論文，民國八十九年六月。
14.Hertz, A. (1991), “Tabu Search for Large Scale Timetabling Problems,” European Journal of Operational Research, Vol. 54, pp. 39-47.
15.Brailsford, S. C., Potts, C. N. and Smith, B. M. (1999), “Constraint Satisfaction Problem: Algorithms and Applications,” European Journal of Operational Research, Vol. 19, pp. 557-581.
16.McAloon, K., Tretkoff, C. and Wetzel, G. (1997), “Sports League Scheduling,” in: Proceedings of the 1997 ILOG Optimization Suite International Users’ Conference, Paris, July, 1997.
17.Deris, S. (1999), “Incorporating Constraint Propagation in Genetic Algorithm for University Timetable Planning,” Engineering Applications of Artificial Intelligence, Vol. 12, pp. 241-253.
18.曾國雄，王日昌，黃明居(1996)，「以基因演算法與樣版路徑求解旅行推銷員問題」，運輸計畫季刊，第二十五卷，第三期，第493-516頁。
19.宋明弘，徐俊能(1994)，「以遺傳基因演算法則解決多目標考量的推銷員旅行問題之研究」，私立大葉大學事業經營研究所碩士論文，民國八十三年六月。
20.Goldberg, D.E. (1989), “Genetic algorithms in search, optimization, and machine learning”, Addison Wesley.
21.Rudolph, G. (1994), “Convergence properties of canonical genetic algorithms”, IEEE Trans. Neural Networks, Vol. 5, No. 1, pp. 96-101.
22.謝昆霖，沈進成，周君妍，鄭丞君(2005)，「基因演算法應用於顧客旅遊行程最適化模式之研究」，旅遊管理研究，第四卷，第一期，第53-66頁。
23.Grefenstette, J. J. (1986), “Optimization of control parameters for genetic algorithms,” IEEE Transactions on Systems, Man, and Cybernetics, Vol. 16, No. 1, pp. 122-128.
24.Schaffer, J.D., Caruana, R.A., Eshelman, L.J. and Das, R. (1989), “A study of control parameters affecting online performance of genetic algorithms for function optimization,” Proceedings of the Third International Conference on Genetic Algorithms, pp. 51-60.
25.Free Map Tools http://www.freemaptools.com/measure-distance.htm
26.The Official Site of Major League Baseball http://www.mlb.com
27.CO2排放計算器 http://xmecc.xmsme.gov.cn/2008-2/2008215144435.htm
28.歐洲足球官方網站 http://cn.uefa.com
29.亞洲職棒大賽 http://www.asiaseries.org