18 Mannschaften. 34 Spieltage. 306 Spiele. Jeder Verein spielt gegen jeden anderen, einmal zu Hause, einmal auswärts. Wer jetzt denkt, dass die Planung einer Bundesligasaison so schwer nicht sein kann, liegt falsch, erklärt Sven Krumke.
Der Professor für Mathematik gehört zu den wenigen Menschen in Deutschland, die die Spielplanung in ihrer ganzen Tiefe durchdrungen haben. Gemeinsam mit seinem damaligen Postdoktoranden Stefan Westphal entwickelte Krumke an der Technischen Universität Kaiserslautern, heute RPTU, ein mathematisches System zur Spielplanoptimierung – die Grundlage für die Softwarelösung, mit der die Deutsche Fußball Liga (DFL) seitdem arbeitet.
„Natürlich kann man einen Standardspielplan erzeugen, indem man Mannschaften einmal anordnet und dann die Paarungen rotiert“, erklärt Krumke. „Aber darum geht es im Profifußball nicht. Wir wollen nicht irgendeinen Spielplan, sondern einen besonders schönen.“
„Bei 18 Mannschaften gibt es alleine für die ersten vier Spieltage mehr als 1081 Möglichkeiten. Mehr, als es Atome im Universum gibt."
Sven Krumke
Schön bedeutet, dass die Abfolge der Begegnungen ganz unterschiedliche Anforderungen erfüllen soll, was das Unterfangen kompliziert macht. Einige Bedingungen sind gesetzt, etwa dass jedes Team an einem Spieltag nur einmal spielt; andere sind gewünscht, zum Beispiel, dass eine Mannschaft abwechselnd zu Hause und auswärts kickt. Bei 18 Mannschaften geht das allerdings nicht auf – womit wir beim ersten Knackpunkt sind.
„Wir haben gegenläufige Ziele“, erläutert Krumke die Herausforderung. „Gewünscht sind möglichst hohe Zuschauerzahlen, es soll aber gleichzeitig wenige Fehler im Wechsel zwischen Heimspiel und Auswärtspartie geben.“ Auch Sicherheitsfragen spielen eine Rolle. „Zeitgleiche Heimspiele von Dortmund und Schalke sind für die Polizei in Nordrhein-Westfalen ein logistisches Problem.“ Und schließlich ist da die Dramaturgie. Je nach Verlauf der Saison muss der Spielplan gegen Ende der Spielzeit Spielräume lassen, um Abstiegsduellen und Relegations-Krimis eine große Bühne zu bieten. Die DFL muss solche Faktoren gewichten, was wiederum das gesamte System beeinflusst.
Wer mit Krumke spricht, merkt schnell, dass sein Herz für den 1. FC Kaiserslautern schlägt. „Wenn es einen gepackt hat, lässt es einen halt nicht mehr los“, sagt der Dauerkartenbesitzer in der Westkurve des Fritz-Walter-Stadions.
„Mit dem Thema Spielplanoptimierung bringen wir die Uniforschung quasi mit der Westkurve zusammen. Das ist ein perfektes Anschauungsmaterial für unser Spezialgebiet.“ Gemeint sind sogenannte diskrete Optimierungsprobleme: mathematische Modelle, in denen es keine Zwischenwerte gibt, sondern ausschließlich klare Entscheidungen – Ja oder nein. „Ein Team spielt nicht zu 93 Prozent gegen ein anderes, sondern entweder oder.“
Um zu zeigen, wie die Mathematik mit einem solchen Problem umgeht, formuliert Krumke die Grundaufgabe der Spielplanung: „Gegeben sind n Mannschaften. Jede Mannschaft hat n−1 Gegner, weil sie gegen alle genau einmal spielt, nur nicht gegen sich selbst. Es müssen n(n−1)/2 Spiele so verteilt werden, dass jede Mannschaft pro Spieltag genau einmal spielt.“ Gesucht werde nun die Verteilung der Spiele auf die Spieltage.
„Der Spielplan ist kein Kalender, den man einfach ausfüllt, sondern ein kombinatorisches Problem. Wer meint, man könne einfach alle Möglichkeiten durchprobieren, stößt schnell an Grenzen. Bei 18 Mannschaften gibt es alleine für die ersten vier Spieltage mehr als 1081 Möglichkeiten. Mehr, als es Atome im Universum gibt“, sagt Krumke. Oder abgekürzt für alle, denen es bei solchen Zahlen schwindelig wird: „Es sind furchtbar viele Möglichkeiten. Komplett verrückt", sagt Krumke.
Krumke und sein Kollege Westphal machten den gewaltigen Berg möglicher Kombinationen mit mathematischer Modellierung beherrschbar. „Wir haben die Spielplanung als ganzzahliges lineares Programm formuliert. Das ist ein mathematisches Modell, das mit Ja-Nein-Entscheidungen arbeitet. Es beinhaltet Variablen für jede mögliche Teamkombination, für Nebenbedingungen, Ausschlüsse sowie für Zielfunktionen, die bewerten, wie „gut“ ein Spielplan ist. Etwa hinsichtlich Zuschauerinteresse oder der Verteilung von Heim- und Auswärtsspielen.“
„Der Spielplan ist kein Kalender, den man einfach ausfüllt, sondern ein kombinatorisches Problem. Wer meint, man könne einfach alle Möglichkeiten durchprobieren, stößt schnell an Grenzen."
Sven Krumke
Bildlich dargestellt entsteht ein hochdimensionaler Polyeder – ein Lösungsraum, der durch viele Bedingungen definiert ist. „Jede Variable bildet darin eine eigene Dimension. Jeder ganzzahlige Punkt darin steht für einen möglichen Spielplan. Die Optimierung sucht in diesem Raum gezielt nach der besten Lösung“, erklärt der Professor. Auf Grundlage dieses Modells entwickelte Stefan Westphal eine kommerzielle Software, die von der DFL erworben wurde und dort seit über 15 Jahren im Einsatz ist.
„Ganz früher wurde der Spielplan heuristisch erstellt, also durch Annäherung. „Tauschen, verschieben, ausprobieren“, sagt Krumke. Die Zeiten des händischen „Nüppchenschiebens“, wie er es nennt, sind aber längst vorbei. Computerprogramme waren auch schon vor der „Kaiserslauterer Lösung“ im Einsatz. „Die Software mit unserem System ermöglicht es der DFL nun aber, sich im vollen Spektrum der Optionen zu bewegen, an einzelnen Stellschrauben zu drehen und Spielpläne zu erzeugen, die verlässlich im Gesamtbild funktionieren.“
„Wenn der FCK zweimal hintereinander auswärts spielt, weiß ich, jetzt haben wir diesen unvermeidbaren Heim-Auswärtsfehler kassiert. Für das große Ganze ergibt das Sinn. Als Fan denke ich dann trotzdem: So was Blödes“, lacht Krumke.
Auch wenn das Thema nicht neu ist, ist der Bundesliga-Spielplan nach wie vor ein Dauerbrenner für die Mathematikerinnen und Mathematiker an der RPTU – aber längst nicht ihr einziger Forschungsgegenstand, an dem sie zeigen können, dass Mathematik nicht nur im stillen Kämmerlein stattfindet.
„Beim ADAC gibt es zum Beispiel eine ähnliche Grundproblematik. Jede Panne soll genau einmal abgefahren werden und Reihenfolgen, Zeitfenster und knappe Ressourcen müssen bestmöglich geplant werden“, sagt Krumke, dessen Arbeitsgruppe sich auch mit Stundenplänen und der Logistik im Bahnverkehr beschäftigt und im Auftrag des rheinland-pfälzischen Innenministeriums an der Planung von Notarztstandorten und Schichtsystemen arbeitet. „Das sind alles Fälle, wo gilt: Mathematik kann etwas in der Welt bewegen.“
Dann findest Du hier weiterführende Literatur:
S. O. Krumke, H. N. Noltemeier, „Graphentheoretische Konzepte und Algorithmen“, B.G. Teubner 2012
S. O. Krumke, E. Schmidt, and M. Streicher, „Robust Multicovers with Budgeted Uncertainty“, European Journal of Operational Research, Volume 274, Issue 3, May 2019, Pages 845-857
S. M. Dimant, and S. O. Krumke, „On Approximating Partial Scenario Set Cover“, Theoretical Computer Science, Volume 1023, January 2025.
Beitrag „Cleverer Code für Gelbe Engel" im Deutschlandfunk, 27.07.2002
Artikel „Die Wurzeln des Fortschritts" in Bild der Wissenschaft, 18. März 2008
