{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T03:21:25Z","timestamp":1768706485521,"version":"3.49.0"},"reference-count":27,"publisher":"MIT Press","issue":"3","content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,9,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>The traveling tournament problem is a well-known sports league scheduling problem famous for its practical hardness. Given an even number of teams with symmetric distances between their venues, a double round-robin tournament has to be scheduled minimizing the total travel distances over all teams. We consider the most common constrained variant without repeaters and a streak limit of three, for which we study a beam search approach based on a state-space formulation guided by heuristics derived from different lower bound variants. We solve the arising capacitated vehicle routing subproblems either exactly for small- to medium-sized instances up to 18 teams or heuristically also for larger instances up to 24 teams. In a randomized variant of the search, we employ random team ordering and add small amounts of Gaussian noise to the nodes' guidance for diversification when multiple runs are performed. This allows for a simple yet effective parallelization of the beam search. A final comparison is done on the NL, CIRC, NFL, and GALAXY benchmark instances with 12 to 24 teams, for which we report a mean gap difference to the best known feasible solutions of 1.2% and five new best feasible solutions.<\/jats:p>","DOI":"10.1162\/evco_a_00319","type":"journal-article","created":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T14:08:00Z","timestamp":1686665280000},"page":"233-257","update-policy":"https:\/\/doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":4,"title":["Approaching the Traveling Tournament Problem with Randomized Beam Search"],"prefix":"10.1162","volume":"31","author":[{"given":"Nikolaus","family":"Frohner","sequence":"first","affiliation":[{"name":"Institute of Logic and Computation, TU Wien, Vienna, Austria nfrohner@ac.tuwien.ac.at"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bernhard","family":"Neumann","sequence":"additional","affiliation":[{"name":"Institute of Logic and Computation, TU Wien, Vienna, Austria bernhard.neumann96@gmail.com"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giulio","family":"Pace","sequence":"additional","affiliation":[{"name":"Institute of Logic and Computation, TU Wien, Vienna, Austria giulio.pace93@gmail.com"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G\u00fcnther R.","family":"Raidl","sequence":"additional","affiliation":[{"name":"Institute of Logic and Computation, TU Wien, Vienna, Austria raidl@ac.tuwien.ac.at"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","published-online":{"date-parts":[[2023,9,1]]},"reference":[{"issue":"2","key":"2023090105042766700_B1","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/s10951-006-7187-8","article-title":"A simulated annealing approach to the traveling tournament problem","volume":"9","author":"Anagnostopoulos","year":"2006","journal-title":"Journal of Scheduling"},{"key":"2023090105042766700_B2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-42849-9","volume-title":"Decision diagrams for optimization (Artificial intelligence: Foundations, theory, and algorithms)","author":"Bergman","year":"2016","edition":"1st"},{"issue":"3","key":"2023090105042766700_B3","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1287\/inte.1110.0587","article-title":"An application of the traveling tournament problem: The Argentine volleyball league","volume":"42","author":"Bonomo","year":"2012","journal-title":"Interfaces"},{"key":"2023090105042766700_B4","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1016\/S0304-0208(08)73478-9","article-title":"Scheduling in sports","volume":"11","author":"De Werra","year":"1981","journal-title":"Studies on Graphs and Discrete Programming"},{"issue":"2","key":"2023090105042766700_B5","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s10732-006-9007-x","article-title":"A composite-neighborhood tabu search approach to the traveling tournament problem","volume":"13","author":"Di Gaspero","year":"2007","journal-title":"Journal of Heuristics"},{"issue":"1","key":"2023090105042766700_B6","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s11750-020-00576-9","article-title":"Sports scheduling and other topics in sports analytics: A survey with special reference to Latin America","volume":"29","author":"Dur\u00e1n","year":"2021","journal-title":"Top"},{"issue":"3","key":"2023090105042766700_B7","doi-asserted-by":"crossref","first-page":"1126","DOI":"10.1016\/j.ejor.2018.12.018","article-title":"Scheduling Argentina's professional basketball leagues: A variation on the travelling tournament problem","volume":"275","author":"Dur\u00e1n","year":"2019","journal-title":"European Journal of Operational Research"},{"key":"2023090105042766700_B8","first-page":"580","article-title":"The traveling tournament problem description and benchmarks","volume":"2239","author":"Easton","year":"2001","journal-title":"International Conference on Principles and Practice of Constraint Programming"},{"key":"2023090105042766700_B9","first-page":"100","article-title":"Solving the travelling tournament problem: A combined integer programming and constraint programming approach","volume":"2740","author":"Easton","year":"2002","journal-title":"International Conference on the Practice and Theory of Automated Timetabling"},{"key":"2023090105042766700_B10","first-page":"67","article-title":"A beam search approach to the traveling tournament problem","volume":"12102","author":"Frohner","year":"2020","journal-title":"Evolutionary Computation in Combinatorial Optimization \u2013 20th European Conference, Held as Part of EvoStar 2020"},{"key":"2023090105042766700_B11","first-page":"2271","article-title":"Solving the traveling tournament problem by packing three-vertex paths","author":"Goerigk","year":"2014","journal-title":"Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence"},{"issue":"1","key":"2023090105042766700_B12","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/s10479-014-1586-6","article-title":"A combined local search and integer programming approach to the traveling tournament problem","volume":"239","author":"Goerigk","year":"2016","journal-title":"Annals of Operations Research"},{"issue":"2","key":"2023090105042766700_B13","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/j.ejor.2009.10.024","article-title":"A new branch-and-price algorithm for the traveling tournament problem","volume":"204","author":"Irnich","year":"2010","journal-title":"European Journal of Operational Research"},{"issue":"1\u20132","key":"2023090105042766700_B14","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/S0004-3702(01)00092-3","article-title":"Disjoint pattern database heuristics","volume":"134","author":"Korf","year":"2002","journal-title":"Artificial Intelligence"},{"key":"2023090105042766700_B15","article-title":"An improved neighbourhood for the traveling tournament problem","author":"Langford","year":"2010"},{"issue":"1","key":"2023090105042766700_B16","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1080\/00207548808947840","article-title":"Filtered beam search in scheduling","volume":"26","author":"Ow","year":"1988","journal-title":"International Journal of Production Research"},{"issue":"1","key":"2023090105042766700_B17","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/j.ejor.2005.10.063","article-title":"A benders approach for the constrained minimum break problem","volume":"177","author":"Rasmussen","year":"2007","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"2023090105042766700_B18","doi-asserted-by":"publisher","first-page":"775","DOI":"10.1016\/j.ejor.2005.03.061","article-title":"Heuristics for the mirrored traveling tournament problem","volume":"179","author":"Ribeiro","year":"2007","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"2023090105042766700_B19","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1109\/4235.873238","article-title":"Stochastic ranking for constrained evolutionary optimization","volume":"4","author":"Runarsson","year":"2000","journal-title":"IEEE Transactions on Evolutionary Computation"},{"issue":"4-5","key":"2023090105042766700_B20","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/j.tcs.2010.10.001","article-title":"Complexity of the traveling tournament problem","volume":"412","author":"Thielen","year":"2011","journal-title":"Theoretical Computer Science"},{"key":"2023090105042766700_B21","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1109\/SCIS.2007.367664","article-title":"A new lower bound to the traveling tournament problem","author":"Urrutia","year":"2007","journal-title":"2007 IEEE Symposium on Computational Intelligence in Scheduling"},{"key":"2023090105042766700_B22","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1145\/1569901.1569913","article-title":"An ant colony optimization approach to the traveling tournament problem","author":"Uthus","year":"2009","journal-title":"Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation"},{"key":"2023090105042766700_B23","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/978-3-642-01929-6_21","article-title":"DFS* and the traveling tournament problem","volume":"5547","author":"Uthus","year":"2009","journal-title":"International Conference on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems"},{"issue":"5","key":"2023090105042766700_B24","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1007\/s10951-011-0237-x","article-title":"Solving the traveling tournament problem with iterative-deepening A*","volume":"15","author":"Uthus","year":"2012","journal-title":"Journal of Scheduling"},{"issue":"2","key":"2023090105042766700_B25","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1016\/j.ejor.2019.07.023","article-title":"Robinx: A three-field classification and unified data format for round-robin sports timetabling","volume":"280","author":"Van Bulck","year":"2020","journal-title":"European Journal of Operational Research"},{"key":"2023090105042766700_B26","first-page":"228","article-title":"Traveling tournament scheduling: A systematic evaluation of simulated annealling","author":"Van Hentenryck","year":"2006","journal-title":"International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming"},{"key":"2023090105042766700_B27","first-page":"262","article-title":"Population-based simulated annealing for traveling tournaments","author":"Van Hentenryck","year":"2007","journal-title":"Proceedings of the 22nd National Conference on Artificial Intelligence"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/31\/3\/233\/2155608\/evco_a_00319.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/31\/3\/233\/2155608\/evco_a_00319.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,1]],"date-time":"2023-09-01T05:04:41Z","timestamp":1693544681000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/31\/3\/233\/116322\/Approaching-the-Traveling-Tournament-Problem-with"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"references-count":27,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2023,9,1]]},"published-print":{"date-parts":[[2023,9,1]]}},"URL":"https:\/\/doi.org\/10.1162\/evco_a_00319","relation":{},"ISSN":["1530-9304"],"issn-type":[{"value":"1530-9304","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023]]},"published":{"date-parts":[[2023]]}}}