職業籃球聯賽賽事排程問題及遺傳演算法求解法

Abstract

美國職業籃球聯賽賽事排程問題是一特定的運動排程問題。求解目的是在 聯賽的賽制規範下，考量賽事的基本資料和限制條件安排出一合理的賽程。求 解目標是在滿足主要限制條件的情形下，減少球隊移動總距離，且減少次要限 制條件違反量。本研究將官方歷年的賽程資訊製作成標竿問題，並研擬遺傳演 算求解法進行求解並與官方賽程比較優劣。求解法的基因編碼採用賽事排序的 編碼格式。因應編碼方式，研擬專用的初始解產生法，盡量避免同球隊的賽事 排在相鄰位置。此法能降低解碼後的賽程賽日長度，避免產生過多不可行的解。 此外，為了有效地改善總球隊移動距離，求解法將賽事間的移動距離當作賽事 成本考量，並設計一啟發式突變機制去改善單場賽事成本最高的球隊的賽程。 完整定義本賽程問題的數學模式外，同時依據研擬的遺傳演算求解法開發一套 求解本問題的軟體系統。實例測試時使用2012-2013、2013-2014、和2014-2015 三個標竿問題進行求解並與官方的賽程統計數據比較優劣。結果顯示本遺傳演 算求解法能有效地改善各問題的球隊移動總距離，且兩項賽程指標：球隊連續 二日出賽次數加總和球隊五日內出賽四場次數加總的統計量也都能減少。

NBA Scheduling Problem is a particular game scheduling problem. The purpose of the problem is to generate a reasonable schedule by following basic information and restrictions from the league. The goal is to reduce Traveling Length Total by satisfying all hard constraints, and also decrease the statistic of soft constraints. This work construct NBA benchmarks from recent official information, then use genetic algorithm to solve it, finally, compare the results to official schedule. Encoding scheme uses game sequencing as format. Due to this format, this work develop a method to generate initial populations to avoid arranging same game on near position. The method reduce the number of infeasible solutions which have excessive season length after decoding scheme. Besides, to reduce traveling distance, the algorithm use distance between two games as game cost, and design a heuristic mutation method to improve the team schedule which has highest game cost. After define mathematical functions of the problem, we develop a genetic algorithm-based software to test three benchmarks: 2012-2013, 2013-2014, and 2014-2015. Moreover, this work compare the results with official schedule. The results show that this algorithm can not only reduce traveling distance effectively, but also decrease the statistic of two soft constraints: Back-to-back Games Count Total and Four-games-in-five Count Total.