Adaptive large neighbourhood search for double-round-Robin sports tournament problem

Abstract

Sportturniere ziehen Millionen von Fans und Sportler auf der ganzen Welt in ihren Bann. Die erfolgreiche Organisation und Planung dieser Turniere spielt eine wichtige Rolle bei der Gewährleistung eines fairen Wettbewerbs, der Maximierung der Einnahmen und der Verbesserung des Gesamterlebnisses für die Zuschauer. Heutzutage bringen die Größe und Bedeutung solcher Veranstaltungen jedoch so viele verschiedene Faktoren mit sich, dass es für die Organisatoren fast unmöglich ist, bei der Erstellung von Zeitplänen für solche Turniere jedes Detail zu berücksichtigen. Aus diesem Grund wurden in den letzten Jahren viele verschiedene Ansätze entwickelt, um solche Spielpläne automatisch mit Hilfe von Computern zu erstellen. Viele solcher Tools sind im Rahmen des International Timetabling Competition 2021 (ITC2021) entstanden, die sich speziell auf die Suche nach guten Heuristiken für schwierige Instanzen des zeitbeschränkten Double-Round-Robin-sports tournament (DRRST) Problem konzentrierte, welches ein sehr häufiges Format bei Sportveranstaltungen ist. Während viele Algorithmen bereits sehr gute Ergebnisse zeigen, hat der Wettbewerb auch deutlich gemacht, wie schwierig es ist, zufriedenstellende Zeitpläne für solche Turniere zu entwickeln. Viele der im Rahmen des Wettbewerbs entwickelten Ansätze mussten eine übermäßige Menge an Ressourcen einsetzen, um qualitativ hochwertige Lösungen zu erzeugen. Darüber hinaus haben bis heute nur 3 der 45 Instanzen, die während des Wettbewerbs vorgestellt wurden, Lösungen, die bewiesenermaßen optimal sind. In dieser Arbeit schlagen wir eine Adaptive Large Neighborhood Search vor, die weniger Rechenressourcen verbraucht als bisherige LNS-Ansätze und dennoch Ergebnisse erzielt, die dem Stand der Technik nahe kommen. Diese Effizienzsteigerung resultiert aus einer Kombination von multi-armed bandit-Methoden aus dem Reinforcement Learning, sechs neu entwickelten Nachbarschaftstypen sowie der Einführung neuer Heuristiken, die von der Tabu-Suche und Methoden der manuellen Optimierung inspiriert sind. Mit Hilfe dieser Techniken sind wir in der Lage, trotz unseres geringeren Ressourcenverbrauchs für 3 der 45 Instanzen des Wettbewerbes neue beste bekannte Lösungen zu finden. Unsere Forschung zeigt, wie wichtig der Einsatz adaptiver Methoden ist, wenn die Ressourcen nicht im Überfluss vorhanden sind. Schließlich zeigen wir auch, dass selbst bei ausschließlicher Betrachtung von LNS-basierten Ansätzen verschiedene Instanzen unterschiedliche Nachbarschaftstypen und Algorithmuskonfigurationen bevorzugen.

Sports tournaments captivate millions of fans and athletes all around the world. The successful organization and scheduling of these tournaments play an important role in ensuring fair competition, maximizing revenue, and enhancing the overall spectator experience. However, nowadays the size and importance of such events introduce so many different factors that it becomes almost impossible for organizers to factor in every detail when creating schedules for such tournaments. For this reason in recent years, many different approaches have been developed to create such schedules computationally. Many such tools have emerged in the International Timetabling Competition in 2021 (ITC2021) that focused specifically on finding good heuristics for difficult instances of the time-constraint double-round-robin sports tournament (DRRST) problem which is a very common format in sporting events. While many algorithms already show very good results, the competition has also highlighted just how hard it is to come up with satisfactory schedules for such tournaments. Many of the approaches developed during the competition had to use an excessive amount of resources to find high-quality solutions. Furthermore, to this date, only 3 out of the 45 instances featured during the competition have solutions that were proven to be optimal. In this thesis, we propose an Adaptive Large Neighborhood Search, that uses fewer computational resources than previous LNS approaches while still achieving results close to the state of the art. This increase in efficiency stems from a combination of multi-armed bandit methods from reinforcement learning, six newly developed neighborhood types as well as the introduction of new heuristics that are inspired by tabu search and methods of manual optimizations. With the help of those techniques, we are able to find new best-known solutions to 3 out of the 45 competition instances despite our lower resource usage. Our research highlights the importance of using adaptive methods when resources are not abundant. Finally, we also show that even when only considering LNS-based approaches different instances favor different neighborhood types and algorithm configurations.