結合整數規劃以及模擬退火演算法求解美國職業籃球例行賽事排程問題

Scheduling NBA Regular Season Games with Integer Programming and Simulated Annealing Algorithm

王俊中(Chun-Chung Wang)

指導教授 ： 趙坤茂

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2021年)

https://doi.org/10.6342/NTU202004332

摘要

運動賽事之排程對於任何一個運動賽事聯盟來說都是一個十分複雜且重要的問題，排程的品質直接影響了運動員的表現以及比賽的可看性。不必要的旅行距離以及過多的連續出賽次數不僅僅增加了運動員的疲勞也增加了整體聯盟的移動成本。
美國職業籃球聯盟(NBA) 是全世界知名的職業籃球聯盟，許多人更視其為籃球的最高殿堂，而其複雜的賽事規則以及眾多的隊伍數量使得在安排賽程上顯得十分困難。本論文提出了一個結合整數規劃及模擬退火演算法的兩階段式演算法去安排NBA 例行賽事，並且在符合賽事規則的情況下最小化球隊總旅行公里數以及所有球隊連續兩天出戰之次數。
我們利用 2018-19 NBA 例行賽的規則進行實驗並與 2018-19 NBA官方賽程進行比較。實驗結果顯示我們提出的演算法所規劃的賽程在兩個目標函數的表現上能同時進步12 %.

關鍵字

運動排程 ； 整數規劃 ； 模擬退火演算法 ； 組合最佳化

並列摘要

Scheduling is a very complicated and important issue for any sports league.The quality of scheduling directly affects the performance of players and the quality of games. Unnecessary travel distance increases not only the fatigue of players but also teams’ travelling cost.
National Basketball Association (NBA) is the most popular basketball league in the world. Most people even saw it as the best basketball league on Earth. The complicated rules and a multitude of teams make the schedule hard to be developed. In this thesis, we proposed a two-phase algorithm that combines integer programming and simulated annealing strategies to schedule the NBA regular season games under league’s rules, and aim to minimize the total travel distance and the number of total back-to-back games among all teams.
We applied the 2018-19 NBA regular season rules and regulations in experiments, and the 2018-19 NBA official schedule is a benchmark against our solutions. Numerical experiments showed that our solution improved by 12 % on both objectives simultaneously.

並列關鍵字

sport scheduling ； integer programming ； simulated annealing, ； combinatorial optimization

參考文獻

[1] Jeff Zillgitt. NBA schedule more player friendly with fewer back-to-back games. USA TODAY Sports, Aug 2015. URL https://www.usatoday.com/story/sports/2015/08/12/nba-schedule-more-player-friendly-fewer-back-back-games/31564149/.

[2] George L Nemhauser and Michael A Trick. Scheduling a major college basketball conference. Operations Research, 46(1):1–8, 1998.

[3] Rasmus V Rasmussen and Michael A Trick. Round robin scheduling–a survey. European Journal of Operational Research, 188(3):617–636, 2008.

[4] Kelly King Easton. Using integer programming and constraint programming to solve sports scheduling problems. PhD thesis, Georgia Institute of Technology, 2002.

[5] Filipe Brandão and João Pedro Pedroso. A complete search method for the relaxed traveling tournament problem. EURO Journal on Computational Optimization, 2(1):77–86, 2014.