結合限制規劃法與螞蟻演算法求解運動排程問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：33

、訪客IP：3.133.12.172

姓名

蔡政諭(Cheng-yu Tsai) 查詢紙本館藏

畢業系所

土木工程學系

論文名稱

結合限制規劃法與螞蟻演算法求解運動排程問題
(Combining Constraint Programming with Ant Colony Optimization to Solve Sports Scheduling Problem.)

相關論文

★ 圖書館系統通閱移送書籍之車輛途程問題	★ 起迄對旅行時間目標下高速公路匝道儀控之研究
★ 共同邊界資料包絡分析法在運輸業之應用-以國內航線之經營效率為例	★ 雙北市公車乘客知覺服務品質、知覺價值、滿意度、行為意向路線與乘客之跨層次中介效果與調節式中介效果
★ Investigating the influential factors of public bicycle system and cyclist heterogeneity	★ A Mixed Integer Programming Formulation for the Three-Dimensional Unit Load Device Packing Problem
★ 高速公路旅行時間預測之研究--函數資料分析之應用	★ Behavior Intention and its Influential Factors for Motorcycle Express Service
★ Inferring transportation modes (bus or vehicle) from mobile phone data using support vector machine and deep neural network.	★ 混合羅吉特模型於運具選擇之應用-以中央大學到桃園高鐵站為例
★ Preprocessing of mobile phone signal data for vehicle mode identification using map-matching technique	★ 含額外限制式動態用路人均衡模型之研究
★ 動態起迄旅次矩陣推估模型之研究	★ 動態號誌時制控制模型求解演算法之研究
★ 不同決策變數下動態用路人均衡路徑選擇模型之研究	★ 動態人口分布最佳化控制之研究-雙層規劃模型之應用

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 ( 永不開放)

摘要(中)

傳統人工安排運動排程的方式過程耗時且耗力。本研究提出實際美國職棒大聯盟運動排程問題之限制滿足最佳模式，目標值為所有球隊移動距離之加總。運動排程問題使屬於NP-complete問題，且美國職棒大聯盟運動排程問題賽制規則之複雜，而應用限制規劃法結合螞蟻演算法之整合式演算法，求解三種不同的運動排程問題：美國職棒大聯盟賽程問題、張文助(2005)提出之中華職棒大聯盟賽程問題及Goossens and Spieksma (2009)提出比利時足球聯盟賽程問題。本研究對大聯盟賽程問題求解後，所得到的總旅行距離較大聯盟現況減少3.92%，顯示出整合式演算法能確實能改進大聯盟現況總移動成本的目標值，最後提出結論與建議。

摘要(英)

The arrangement of sports scheduling for each sport scheduling planner is a time consuming work. In this research, a constraint satisfaction problem (CSP) of Major League Baseball (MLB) scheduling with real world considerations is represented. The objective value of the proposed formulation is to minimize total travel distance of all teams in MLB. Since the sport scheduling problem is NP-complete, the CSP of MLB is hard to solve with consideration of rules of regulations of MLB. A combined algorithm which composed by constraint programming (CP) and ant colony system is proposed to solve the CSP of sport scheduling. Three different types of sports scheduling problem are tested by using the combined algorithm. The first one is MLB Scheduling problem, the second is Chinese Professional Baseball League Problem and the third is Belgian Soccer League scheduling. The test results show that the combined algorithm is advantageous over the current status of MLB with respect to the objective value.

關鍵字(中)

★ 限制規劃
★ 美國職棒大聯盟
★ 運動排程
★ 中華職棒大聯盟
★ 螞蟻演算法

關鍵字(英)

★ constraint programming
★ Chinese Professional Baseball League
★ sports scheduling problem
★ ant colony optimization
★ major league baseball

論文目次

摘要 i
Abstract ii
誌謝 iii
表目錄 vi
圖目錄 vii
第一章緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究範圍與假設 2
1.4 研究流程 3
第二章文獻回顧 5
2.1 限制規劃 5
2.1.1 限制滿足問題 7
2.1.2 限制規劃求解方法 10
2.1.2.1 一致性檢驗技術 10
2.1.2.2 樹狀搜尋方法 11
2.1.3 限制規劃與數學規劃之比較 12
2.1.4 限制規劃及啟發式演算法之結合 14
2.1.5 OPL語言之使用介紹 16
2.2 排程問題 17
2.2.1 排課問題及求解 19
2.2.2 運動賽程問題及求解 20
2.3 螞蟻演算法 25
2.4 小結 26
第三章美國職棒大聯盟運動賽程模型構建 27
3.1 美國職棒大聯盟簡介 27
3.2 美國職棒大聯盟賽程問題 27
3.2.1問題描述 28
3.2.2系統限制與參數設定 31
3.3 限制規劃法結合螞蟻演算法 34
3.4 其他運動賽程問題 36
第四章範例測試分析 38
4.1 美國職棒大聯盟賽程問題 38
4.2 中華職棒大聯盟賽程問題 43
4.3 比利時足球聯盟賽程問題 48
第五章結論與建議 52
5.1 結論 52
5.2 建議 52
參考文獻 54
附錄A 限制滿足問題實例 61
附錄B 節線一致性檢驗技術例題 64
附錄C 樹狀搜尋方法之比較 66
附錄D MLB各球隊主場間距離表 72
附錄E 堪薩斯市皇家隊賽程表 75
附錄F 整合式演算法求解結果：2005年中華職棒賽程表 77
附錄G 比利時足球聯盟限制式詳細資料 82

參考文獻

1. 王國琛，「結合限制規劃與數學規劃求解大型後勤空勤組員排班問題」，國立交通大學運輸科技與管理學系，碩士論文，民國91年。
2. 陳柏榮，「以限制規劃程式構建投資組合決策支援系統之研究」，國立交通大學運輸科技與管理學系，碩士論文，民國91年。
3. 陳惠國，網路與物流分析，初版，台北：五南圖書出版股份有限公司，民國98年。
4. 吳志仁，「一般化卡車拖車路線問題」，國立交通大學運輸科技與管理學系，碩士論文，民國92年。
5. 唐依伶，「以限制規劃求解公平性空服組員派遣問題-以座艙長為例」，國立交通大學運輸科技與管理學系，民國92年。
6. 張若怡，「運用限制規劃求解氣體配送途程問題」，國立成功大學交通管理科學系，碩士論文，民國96年。
7. 張文助，「以限制規劃構建運動排程模式-以中華職棒大聯盟賽程表排程為例」，國立交通大學運輸科技與管理學系，碩士論文，民國94年。
8. 蔡正誠，「啟發式分析方法在職棒排程問題應用」，東海大學工業工程研究所，碩士論文，民國81年。
9. 葉杰榮，「應用Constraint Satisfation Programming方法來探討即時排課問題」，國立高雄第一科技大學資訊管理系，碩士論文，民國91年。
10. 李開暉，邱佩玲，「以模擬退火法為基礎的排課演算法之研究」，2004國際學術研討會，銘傳大學，民國93年。
11. 張振卿，「職業運動賽程表最佳系統以最短路徑輸出量為主」，僑光科技大學資訊科技系，碩士論文，民國98年。
12. 楊大輝、朱政威、李綺容、楊智環，「中華職棒大聯盟賽程表排程問題」，第二屆全國當代行銷學術研討會，中興大學，中華民國93年。
13. Apt, K. R., Principles of Constraint Programming, Cambridge, Cambridge University Press, 2003.
14. Babakus, E., Boller, G. W., “An Empirical Assessment of the SERVQUAL Scale,” Journal of Business Research, Vol. 24, No. 3, pp. 253-268, 1992.
15. Baptiste, P., Le Pape, C., “A Theoretical and Experimental Comparison of Constraint Propagation Techniques for Disjunctive Scheduling,” Proceedings of the 14th International Joint Conference on Artificial Intelligence, Morgan Kaufmann, pp. 600-606, 1995.
16. Berbeglia, G., Pesant, G., Rousseau, L.M., “Checking the Feasibility of Dial-a-ride Instances Using Constraint Programming,” Research Report CIRRELT-2010-16.
17. Brailsford, S. C., Potts, C. N., Smith, B. M., “Constraint Satisfaction Problems: Algorithms and Applications,” European Journal of Operational Research, Vol. 119, No. 3, pp. 557-581, 1999.
18. Bartak R., “Constraint Programming: In Pursuit of the Holy Grail,” Proceedings of Week of Doctoral Students, Part IV, pp. 555-564, 1999.
19. Bean, J.C., Birge, J.R., “Reducing Travelling Costs and Player Fatigue in the National Basketball Association,” Interfaces, Vol. 10, pp. 98-102, 1980.
20. Blazewicz, J., Ecker, K., Pesch, E., Schmidt, G., Węglarz, J., Handbook on Scheduling, Springer Verlag, Berlin, New York, 2007,
21. Blum, C., Sampels, M., “An Ant Colony Optimization Algorithm for Shop Scheduling Problems,” Journal of Mathematical Modelling and Algorithms, Vol. 3, NO. 3, pp. 285-308, 2004.
22. Blum, C., Puchinger, J., Raidl, G., Roli, A., “A Brief Aurvey on Hybrid Metaheuristics,” Proceedings of BIOMA 2010 - 4th International Conference on Bioinspired Optimization Methods and their Applications, Slovenia, 2010.
23. Costa, D., “An Evolutionary Tabu Search Algorithm and the NHL Scheduling Problem,” INFOR., Vol. 33, No. 3, pp. 161-179, 1995.
24. Cooper, T.B., Kingston, J.H., “The Complexity of Timetabling Construction Problems,” Lecture Notes in Computer Science, Vol. 17, pp. 183-295, 1996.
25. Cordeau, J.F. and Laporte, G., “The Dial-a-ride Problem (DARP): Variants, Modeling Issues and Algorithms,” Quarterly Journal of the Belgian, French and Italian Operations Research Societies, pp. 89-101, 2003.
26. Crauwels, H., Van Oudheusden, D., “A Generate-and-Test Heuristic Inspired by Ant Colony Optimization for the Travelling Tournament Problem,” Proceedings of the 4th International Conference on the Practice and Theory of Automated Timetabling, pp. 314-315, 2002.
27. De Backer, B., Furnon, V., “Meta-Heuristics in Constraint Programming: Experiments with Tabu Search on the Vehicle Routing Problem,” Proceedings of the 2nd International Conference on Meta-heuristics, 1997.
28. Dorigo, M., Maniezzo, V., Colorni, A., “The Ant System: An Autocatalytic Optimizing Process,” Technical Report 91-016, 1991.
29. Dorigom M., Gambardella, L. M., “Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem,” IEEE Transactions on Evolutionary Computation, Vol. 1, No, 1 , pp. 53-66, 1997.
30. Easton, K., Nemhauser, G., Trick, M., “The Traveling Tournament Problem Description and Benchmarks,” Proceedings of the 7th International Conference on Principles and Practice of Constraint Programming, pp. 580-589, 2001.
31. Easton, K., Nemhauser G., Trick M., “Solving the Travelling Tournament Problem: A Combined Integer Programming and Constraint Programming Approach,” Proceedings of the 4th International Conference on the Practice and Theory of Automated Timetabling, pp. 319-330, 2002.
32. Glover, F., “One-pass Heuristics for Large-scale Unconstrained Binary Quadratic Problems,” European Journal of Operation Reasearch, Vol. 137, No.3, pp. 272-287, 2002.
33. Gomes, N., Vale, Z., Ramos, C., “Combining Metaheuristics and Constraint Programming to Solve a Scheduling Problem,” AMCOS'05 Proceedings of the 4th WSEAS International Conference on Applied Mathematics and Computer Science, 2005.
34. Goossens, D., Spieksma, F., “Scheduling the Belgian Soccer League,” Interfaces, Vol. 39, No. 2, pp. 109-118, 2009.
35. Henz, M., Muller, T., Thiel, S., “Global Constraints for Round Robin Tournament Scheduling,” European Journal of Operational Research, Vol. 153, No.1, pp. 92-101, 2004.
36. Heipcke, S., “Comparing Constraint Programming and Mathematical ProgrammingApproaches to Discrete Optimisation - The Change Problem,” The Journal of the Operational Research Society, Vol. 50, No. 6, pp. 581-595, 1999.
37. Huang, K.L., Liao, C.J., “Ant Colony Optimization Combined with Tabu Search for the Job Shop Scheduling Problem,” Computers & Operations Research, Vol. 35, pp. 1030-1046, 2008.
38. Kendall, G., Knust, S., Ribeiro, C. C., Urrutia, S., “Scheduling in Sports: An Annotated Bibliography,” Computers & Operations Research, Vol. 37, No.1, pp. 1-19, 2010.
39. Khichane, M., Albert, P., Solnon, C., “CP with ACO,” Proceedings of CPAIOR 2008, pp. 328-332, 2008.
40. Khichane, M., Albert P., Solnon, C., “Strong Combination of Ant Colony Optimization with Constraint Programming Optimization,” Proceedings of CPAIOR 2010, pp. 232-245, 2010.
41. Leung, J., (Editor)., Handbook of Scheduling : Algorithms, Models, and Performance Analysis, Chapman Hall, CRC Press, 2004.
42. Martin, C.H., “Ohio University's College of Business Uses Integer Programming to Schedule Classes,” Interfaces, Vol. 34, No. 6, pp. 460-465, 2004.
43. McAloon, K., Tretkoff, C., Wetzel, G., “Sports League Scheduling,” Proceedings of the 1997 ILOG Optimization Suite International Users’ Conference, 1997.
44. Meyer, B., Ernst, A., “Integrating ACO and Constraint Propagation,” Lecture Notes in Computer Science, Vol. 3172, pp. 166-177, 2004.
45. McAloon, K., Tretkoff, C. and Wetzel, G., “Sports League Scheduling,” Proceedings of the 1997 ILOG Optimization Suite International Users’ Conference, 1997.
46. Nemhauser, G.L., Trick, M.A., “Scheduling a Major College Basketball,” Operations Research, Vol. 46, No. 1, pp. 1-8, 1998.
47. Nurmi, K., Goossens, D., Bartsch, T., Bonomo, F., Briskorn, D., Duran, G., Kyngas, J., Marenco, J., Ribeiro, C. C., Spieksma, F., Urrutia, S., Wolf, R., “A Framework for a Highly Constrained Sports Scheduling Problem,” Proceedings of the International MultiConference of Engineers and Computer Scientists, Vol. 3, pp. 1991-1997, 2010.
48. Pesant, G., Gendreau, M., “A Constraint Programming Framework for Local Search Methods,” Journal of Heuristics, Vol. 5, pp. 255-279, 1999.
49. Puget, J.F., “A Comparison between Constraint Programming and Integer Programming,” Conference on Applied Mathematical Programming and Modelling, 1995.
50. Russell, R.A., Leung, J., “Devising a Cost Effective Scheduling for a Basketball League,” Operations Research, Vol. 42, No. 4, pp. 612-625, 1994.
51. Sabin, D., Freuder, E. C., “Contradicting Conventional Wisdom in Constraint Satisfaction,” Proceedings of ECAI-94, pp. 125-129, 1994.
52. Schaerf, A., “Scheduling Sport Tournaments Using Constraint Logic Programming,” Constraints, Vol. 4, No. 1, pp. 43-65, 1999.
53. Thiruvady, D., Blum, C., Meyer, B., Ernst, A., “Hybridizing Beam-ACO with Constraint Programming for Single Machine Job Scheduling Problem,” Lecture Notes in Computer Science, Vol. 5818, pp. 30-44, 2009.
54. Tsang, E., Foundations of Constraint Satisfaction, London and San Diego: Academic Press, 1993.
55. Uthus, D.C., Riddle, P.J., Guesgen, H.W., “Ant Colony Optimization and the Single Round Robin Maximum Value Problem,” Proceedings of the 6th International Conference on Ant Colony Optimization and Swarm Intelligence, pp. 243-250, 2008.
56. Van Hentenryck, P., The OPL Optimization Programming Language, Cambridge: MIT Press, 1999.

指導教授

陳惠國(Huey-Kuo Chen)

審核日期

2011-8-25

推文