簡易檢索 / 詳目顯示

回結果列表
研究生： 陳重堯
Chen, Chung-Yao
論文名稱： 以多目標與限制最佳化觀點求解非固定主場運動排程問題：以中華職棒大聯盟為例
Solving Multi-Home Sport Scheduling Problem by Constrained Multiobjective Optimization : A Case Study of Chinese Professional Baseball League
指導教授： 蔣宗哲
Chiang, Tsung-Che
學位類別： 碩士
Master
系所名稱： 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年： 2019
畢業學年度： 107
語文別： 中文
論文頁數： 89
中文關鍵詞： 競賽旅程問題 、多目標最佳化 、模擬退火法 、中華職棒
DOI URL： http://doi.org/10.6345/NTNU201900850
論文種類： 學術論文
相關次數： 點閱：121  下載：6 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 在國內外職業運動賽事中，每年都需要為比賽排出新的賽程。而賽程的安排會間接影響到進場的觀眾人數、廣告的安排、贊助商的贊助、球員的實力發揮以及休息時間；賽程的安排不當將導致職業賽事聯盟的收益降低。賽程的安排需考量隊伍的移動距離、對戰組合的話題性及公平性，所以賽程的安排是一件極為複雜的事情，運動排程也被認為是高度複雜的組合問題。在2013年，石大維的碩士論文將競賽旅程問題的單目標最佳化問題，發展為多目標最佳化問題。本論文為了更貼近真實情形，以中華職棒季賽賽程去探討最佳化旅行總距離和最長旅行距離的多目標最佳化問題。
    本論文提出群體式彈性機率鄰域模擬退火法，使用彈性機率鄰域的選取方法去和隨機機率鄰域函式作比較，並且修改了群體式模擬退火法的流程，讓本論文的方法可以在一定的搜尋次數內，找到多目標最佳解。最後本論文也列出找到的多目標最佳解，並和真實的賽程去做比較，也提供決策者作參考。

    謝誌 i 中文摘要 ii 目錄 iii 附表目錄 vi 附圖目錄 ix 附錄 x 第一章 緒論 1 1.1 研究動機 1 1.2 傳統競賽旅程問題定義 1 1.3 本論文研究問題定義 3 1.4 實例說明 6 1.5 全文架構 7 第二章 文獻探討 8 2.1 背景知識 8 2.1.1 演化演算法 8 2.1.2 多目標最佳化問題 9 2.2 區域搜尋法 9 2.2.1 禁忌搜尋法 9 2.2.2 模擬退火法 10 2.3 群體式搜尋法 13 2.3.1 螞蟻演算法 13 2.3.2 基因演算法 14 2.4 初始化 17 2.4.1 隨機初始化 17 2.4.2 快速賽程初始化 17 2.5 鄰域函式 20 第三章 群體式彈性機率鄰域模擬退火法 26 3.1 演算法架構 26 3.2 解的編碼 27 3.3 初始化 28 3.4 鄰域函式 30 3.5 適應度評估 37 3.6 群體式彈性機率鄰域模擬退火法 38 3.7 環境選擇 42 第四章 實驗設計與分析 43 4.1 測試問題 43 4.2 效能指標 44 4.3 參數設定 45 4.4 實驗與結果 46 4.4.1 單目標最佳化：初始解品質 46 4.4.2 單目標最佳化：各項鄰域函式單獨使用的效能 47 4.4.3 單目標最佳化：各項鄰域函式單獨使用，搭配初始溫度實驗，懲罰值設定實驗，策略震盪與無策略震盪比較 48 4.4.4 單目標最佳化：隨機選取鄰域函式模擬退火法搭配初始溫度，懲罰值，策略震盪綜合評比 49 4.4.5 單目標最佳化：隨機選取鄰域函式與彈性機率鄰域函式比較 50 4.4.6 單目標最佳化：使用群體式模擬退火法和使用一般模擬退火法比較 52 4.4.7 單目標最佳化：群體式模擬退火法群體數量之比較 54 4.4.8 多目標最佳化實驗 56 4.4.9 實驗最佳解和實際賽程比較 58 第五章 結論與未來研究方向 61 參考文獻 62 附錄 65

    [1] K. Easton, G. Nemhauser, and M. Trick, "The Traveling Tournament Problem Description and Benchmarks," Principles and practice of constraint programming--CP2001. pp. 580-585,2001.
    [2] D.W. Shi, Solving the Traveling Tournament Problem by Constrained Multiobjective Optimization, Department of Computer Science and Information Engineering, National Taiwan Normal University, Master Thesis, 2013. (In Chinese)
    [3] M. Carvalho and L. Lorena, "New Models for the Mirrored Traveling Tournament Problem," Computers & Industrial Engineering, vol. 63, no. 4, pp. 1089-1095, 2012.
    [4] W.C. Chang, Constraint Programming Models for Sports Scheduling Problem : A Case of Chinese Professional Baseball League, Department of Transportation & Logistics Management, National ChiaoTung University, Master Thesis, 2015. (In Chinese)
    [5] K. Miettinen, Nonlinear Multiobjective Optimization. Boston, MAA:Kluwer, 1999.
    [6] L. Gaspero and A. Schaerf, "A Composite-Neighborhood Tabu Search Approach to the Traveling Tournament Problem," Journal of Heuristics, vol. 13, no. 2, pp. 189-207, 2007.
    [7] C.W. Yeh, Tabu Search Algorithm for Major League Baseball Scheduling, Department of Industrial Engineering and Management, Yuan Ze University, Master Thesis, 2013. (In Chinese)
    [8] A. Anagnostopoulos, L. Michel, P. Hentenryck, and Y. Vergados, "A Simulated Annealing Approach to the Traveling Tournament Problem," Journal of Scheduling, vol. 9, no. 2, pp. 177-193, 2006.
    [9] A. Lim, B. Rodrigues, and X. Zhang, "A Simulated Annealing and Hill-Climbing Algorithm for the Traveling Tournament Problem," European Journal of Operational Research, vol. 174, no. 3, pp. 1459-1478, 2006.
    [10] P.V. Hentenryck and Y. Vergados, "Population-Based Simulated Annealing for Traveling Tournaments," Proceedings of the 22nd National Conference on Artificial Intelligence, pp. 267-272, 2007.
    [11] P. Chen, G. Kendall, and G. Berghe, "An Ant Based Hyper-heuristic for the Travelling Tournament Problem," 2007 IEEE Symposium on Computational Intelligence in Scheduling, 2007.
    [12] N. Choubey, "A Novel Encoding Scheme for Traveling Tournament Problem using Genetic Algorithm," International Journal of Computer Applications, no. 2, pp. 79-82, 2010.
    [13] F. Yang, "NBA Sports Game Scheduling Problem and GA-Based Solver," 2017 International Conference on Industrial Engineering, Management Science and Application (ICIMSA), 2017.
    [14] A. Tajbakhsh, K. Eshghi, and A. Shamsi, "A Hybrid PSO-SA Algorithm for the Travelling Tournament Problem," European Journal of Industrial Engineering, vol. 6, no. 1, pp. 512-518, 2012.
    [15] C. Ribeiro and S. Urrutia, "Heuristics for the Mirrored Traveling Tournament Problem," European Journal of Operational Research, vol. 179, no. 3, pp. 775-787, 2007.
    [16] W. Wei, S. Fujimura, X. Wei, and C. Ding, "A Hybrid Local Search Approach in Solving the Mirrored Traveling Tournament Problem," IEEE17th International Conference on Industrial Engineering and Engineering Management, pp. 620-624, 2010.
    [17] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, "A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II," IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182-197, 2002.
    [18] E. Zitzler, M. Laumanns, and L. Thiele, "SPEA2: Improving the Strength Pareto Evolutionary Algorithm for Multiobjective Optimization," Proc. Evolutionary Methods for Design Optimization and Control with Applications to Industrial Problems, pp. 95-100, 2001.
    [19] Q.F. Zhang and H. Li, "MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition," IEEE Transactions on Evolutionary Computation, vol. 11, no. 6, pp. 712-731, 2007.
    [20] P. Bosman and D. Thierens, "The Balance between Proximity and Diversity in Multiobjective Evolutionary Algorithms," IEEE Transactions on Evolutionary Computation, vol. 7, no. 2, pp. 174-188, 2003.

    下載圖示
    QR CODE