07469nam 2200613 450 991074695060332120231102020341.03-031-37283-2(CKB)28447819400041(MiAaPQ)EBC30782896(Au-PeEL)EBL30782896(OCoLC) 1401962072(PPN)272916560(MiAaPQ)EBC30769355(Au-PeEL)EBL30769355(EXLCZ)992844781940004120231102d2023 uy 0engurcnu||||||||txtrdacontentcrdamediacrrdacarrierCombinatorial Models for Scheduling Sports Tournaments /Celso C. Ribeiro, Sebastián Urrutia, and Dominique de WerraFirst edition.Cham, Switzerland :Springer Nature Switzerland AG,[2023]©20231 online resource (xxv, 175 pages) illustrations (some color)EURO Advanced Tutorials on Operational Research Series9783031372827 Includes bibliographical references.Intro -- Foreword -- Preface -- Acknowledgments -- Contents -- List of Abbreviations and Acronyms -- List of Algorithms -- List of Figures -- List of Tables -- 1 Leagues, Tournaments, and Schedules -- 1.1 Tournament Characteristics -- 1.1.1 Compactness -- 1.1.2 Scheduling Timing -- 1.1.3 Design -- 1.1.3.1 Round-Robin Tournaments -- 1.1.3.2 Knockout or Single-Elimination Tournaments -- 1.1.3.3 Swiss-System Tournaments -- 1.2 Professional Versus Amateur Leagues -- 1.3 Typical Problems -- 1.3.1 Break Minimization -- 1.3.2 Distance Minimization -- 1.3.3 Traveling Tournament Problem -- 1.3.4 Cost Minimization -- 1.3.5 Carry-Over Effects -- 1.3.6 Referee Assignment and Umpire Scheduling -- 1.3.7 Multileague Scheduling -- 1.3.8 International Timetabling Competition -- 1.4 Book Organization -- 1.5 Related Literature -- References -- 2 Combinatorial Structures -- 2.1 Elements of Graph Theory -- 2.2 Basic Graph Model for Single Round-Robin Tournaments -- 2.3 From Timetables to Schedules: Home and Away Games -- 2.4 Another Type of 1-Factorization -- 2.5 Multi-Round-Robin Tournaments -- 2.6 On the Structure of HAPs with a Minimum Number of Breaks -- 2.7 Constructing Schedules from HAPs or from Timetables -- 2.8 Minimizing the Number of Rounds with Breaks -- 2.9 Fairness of Schedules -- 2.10 Travel Minimization and Break Maximization -- 2.11 Balanced Tournaments -- 2.12 Tournaments with Referees -- 2.13 Carry-Over Effects -- 2.14 List-Edge Coloring -- 2.15 Exploring the Landscape of Edge Colorings -- 2.16 How to Find General 1-Factorizations? -- 2.17 Concluding Remarks -- 2.18 Related Literature -- References -- 3 Metaheuristics and Local Search -- 3.1 Exact and Approximate Optimization Methods -- 3.2 Greedy and Semi-Greedy Algorithms -- 3.3 Local Search -- 3.3.1 Solution Representation, Neighborhoods, and Search Space -- 3.3.2 Local Search Strategies.3.3.3 Variable Neighborhood Descent -- 3.4 Metaheuristics and Templates -- 3.4.1 Simulated Annealing -- 3.4.2 Tabu Search -- 3.4.3 Greedy Randomized Adaptive Search Procedures -- 3.4.4 Variable Neighborhood Search -- 3.4.5 Iterated Local Search -- 3.4.6 Genetic Algorithms -- 3.5 Neighborhoods for Round-Robin Tournaments -- 3.5.1 Neighborhood ``Home-Away Swap'' (HAS) -- 3.5.2 Neighborhood ``Team Swap'' (TS) -- 3.5.3 Neighborhood ``Round Swap'' (RS) -- 3.5.4 Neighborhood ``Partial Round Swap'' (PRS) -- 3.5.5 Neighborhood ``Partial Team Swap'' (PTS) -- 3.5.6 Neighborhood ``Generalized Partial Team Swap'' (GPTS) -- 3.5.7 Ejection and Repair Chains -- 3.6 Connectivity of the Tournament Space -- 3.7 Related Literature -- References -- 4 Integer Programming Approaches -- 4.1 Motivation -- 4.2 The Traveling Tournament Problem with Predefined Venues -- 4.3 Preliminaries -- 4.4 Integer Programming Formulations -- 4.4.1 Formulation with O(n3) Variables -- 4.4.2 Formulation with O(n4) Variables -- 4.4.3 Formulation with O(n5) Variables -- 4.4.4 Linear Relaxation Bounds and Computational Results -- 4.5 Related Literature -- References -- 5 Case Studies -- 5.1 Minimizing Weighted Carry-Over Effects in Round-Robin Tournaments -- 5.1.1 Motivation -- 5.1.2 Formulation of the Weighted Problem -- 5.1.3 Hybrid Heuristic for Weighted Minimization -- 5.1.3.1 Construction Method for Building New Schedules -- 5.1.3.2 Local Search -- 5.1.3.3 Iterated Local Search -- 5.1.3.4 Iterated Local Search with Destructive Perturbations -- 5.1.4 Computational Results -- 5.1.4.1 Weighted Instances -- 5.1.4.2 Validation: Unweighted Instances -- 5.1.4.3 Destructive Neighboorhoods -- 5.2 Scheduling the Annual Brazilian Football Tournament -- 5.2.1 Tournament Structure -- 5.2.2 Schedule Requirements -- 5.2.2.1 Round-Robin Constraints -- 5.2.2.2 Home-Away Profiles of Game Playing.5.2.2.3 Classic and Regional Games -- 5.2.2.4 Geographical and G12 Constraints -- 5.2.2.5 Perfect Matching of Paired Teams -- 5.2.3 Integer Programming Formulation -- 5.2.4 Solution Approach -- 5.2.4.1 Phase 1: Profile Generation -- 5.2.4.2 Phase 2: Profile Assignment -- 5.2.4.3 Phase 3: Schedule Creation -- 5.2.5 Development and Practical Experience -- 5.3 Dynamic Scheduling of E-Sports Tournaments -- 5.3.1 Rating Teams with Opponents of Different Strengths -- 5.3.2 Dynamic Scheduling: Team Pairing and Game Scheduling -- 5.3.3 Numerical Results -- 5.3.3.1 Simulated Results for Dynamic Scheduling from Realistic Data -- 5.3.3.2 Results for Randomly Generated Larger Tournaments -- 5.3.4 Concluding Remarks -- 5.4 Related Literature -- References -- Epilogue.This book introduces solutions for sports scheduling problems in a variety of settings. In particular the book covers timetabling, the traveling tournament problem, carryover minimization, breaks minimization, tournament design, tournament planning, and referee assignment. A rich selection of applications to sports such as football, baseball, basketball, cricket or hockey are employed to illustrate the methods and techniques. In a step-by-step tutorial format the book describes the use of graph theory concepts, local search operators and integer programming in the context of sports scheduling. The methods presented in this book are essential to sports scheduling in all its dimensions, from tournaments that are followed by millions of people across the world, with broadcast rights that amount to hundreds of millions of dollars in some competitions, to amateur leagues that require coordination and logistical efforts due to the large number of tournaments and competitors.EURO advanced tutorials on operational research.Combinatorial analysisSchedulingMathematical modelsSports tournamentsManagementSports tournamentsMathematical modelsCombinatorial analysis.SchedulingMathematical models.Sports tournamentsManagement.Sports tournamentsMathematical models.511.6Ribeiro Celso C.756026Urrutia SebastiánDe Werra DominiqueMiAaPQMiAaPQMiAaPQBOOK9910746950603321Combinatorial models for scheduling sports tournaments3577188UNINA