簡易檢索 / 詳目顯示
| 研究生： |
陳重堯 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 |
| 論文種類： | 學術論文 |
| 相關次數： | 點閱：122 下載：6 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
在國內外職業運動賽事中，每年都需要為比賽排出新的賽程。而賽程的安排會間接影響到進場的觀眾人數、廣告的安排、贊助商的贊助、球員的實力發揮以及休息時間；賽程的安排不當將導致職業賽事聯盟的收益降低。賽程的安排需考量隊伍的移動距離、對戰組合的話題性及公平性，所以賽程的安排是一件極為複雜的事情，運動排程也被認為是高度複雜的組合問題。在2013年，石大維的碩士論文將競賽旅程問題的單目標最佳化問題，發展為多目標最佳化問題。本論文為了更貼近真實情形，以中華職棒季賽賽程去探討最佳化旅行總距離和最長旅行距離的多目標最佳化問題。
本論文提出群體式彈性機率鄰域模擬退火法，使用彈性機率鄰域的選取方法去和隨機機率鄰域函式作比較，並且修改了群體式模擬退火法的流程，讓本論文的方法可以在一定的搜尋次數內，找到多目標最佳解。最後本論文也列出找到的多目標最佳解，並和真實的賽程去做比較，也提供決策者作參考。
[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.
