Was die vier Ziele bedeuten, wie Grenzen und Derbys wirken und wie der Staffelplaner die beste Aufteilung sucht.
Die Teams einer Liga werden auf die gewählte Zahl an Staffeln verteilt. Die Staffeln sind dabei immer gleich groß oder unterscheiden sich um höchstens ein Team. In jeder Staffel spielt jedes Team gegen jedes andere.
Zwischen je zwei Teams gibt es eine Entfernung: nach Luftlinie, nach Fahrstrecke oder nach Fahrzeit, je nach gewähltem Maß. Gemessen wird vom Stadion aus, in dem das Team in dieser Liga spielt.
Aus diesen Entfernungen entstehen drei Kennzahlen, auf denen alles Weitere aufbaut:
Zu den Kilometern: In einer Saison mit Hin- und Rückspiel fährt jedes Team zu jedem Gegner einmal hin und wieder zurück. Tatsächlich gefahren wird deshalb ein festes Vielfaches der angezeigten Zahlen: bei einer Team-Gesamtstrecke das Doppelte, bei der Gesamtstrecke der Liga das Vierfache. Weil dieser Faktor für jede Aufteilung derselbe ist, ändert er nichts daran, welche Aufteilung die beste ist.
Wird nach Fahrzeit gerechnet, gilt alles genauso, nur in Minuten statt Kilometern.
Welche Aufteilung „die beste“ ist, hängt davon ab, was einer Liga wichtig ist. Der Staffelplaner rechnet deshalb vier Ziele, jedes für sich, und stellt die Ergebnisse nebeneinander. In der Tabelle der Ergebnisse ist in jeder Spalte der beste Wert hervorgehoben.
Was zählt: die Gesamtstrecke. Gesucht wird die Aufteilung, bei der sie am kleinsten ist.
Wofür: Die Liga als Ganzes fährt am wenigsten. Wer Reisekosten, Reisezeit oder CO₂ für alle zusammen senken will, nimmt dieses Ziel.
Der Preis: Wie sich die Strecke auf die Teams verteilt, spielt keine Rolle. Ein Team am Rand der Liga kann deutlich mehr fahren als die anderen, wenn das der Liga insgesamt Kilometer spart.
Was zählt: die Summe der Quadrate der Team-Gesamtstrecken. Durch das Quadrieren wiegt jeder Kilometer eines Teams umso schwerer, je weiter es ohnehin schon fährt: Ein Team mit 400 km zählt 160.000, zwei Teams mit je 200 km zählen zusammen nur 80.000.
Genau genommen wird diese Zahl klein, wenn die Team-Gesamtstrecken klein und ähnlich sind. Es ist also nicht „möglichst gleich um jeden Preis“: Wären alle Teams gleich weit unterwegs, aber alle sehr weit, stünde eine etwas ungleichere, insgesamt kürzere Aufteilung besser da.
Die Spalte „Ausgleich“ zeigt dazu den quadratischen Mittelwert der Team-Gesamtstrecken: die Wurzel aus dem Durchschnitt der Quadrate. Er liegt nie unter der durchschnittlichen Team-Gesamtstrecke und steigt, je ungleicher die Teams fahren.
Der Preis: Insgesamt wird meist etwas mehr gefahren als bei der kürzesten Gesamtstrecke.
Was zählt: die größte Team-Gesamtstrecke, also die des am stärksten belasteten Teams. Gesucht wird die Aufteilung, bei der dieses eine Team so wenig wie möglich fährt.
Bei Gleichstand: Haben mehrere Aufteilungen dieselbe größte Team-Gesamtstrecke, gewinnt die mit der kleineren Summe der Quadrate, also die ausgeglichenere.
Der Preis: Es zählt nur das eine Team. Insgesamt wird oft deutlich mehr gefahren.
Was zählt: die längste Entfernung zwischen zwei Teams derselben Staffel. Gesucht wird die Aufteilung, bei der die weiteste Anreise so kurz wie möglich ist.
Bei Gleichstand: Haben mehrere Aufteilungen dieselbe längste Einzelfahrt, gewinnt die mit der kürzeren Gesamtstrecke.
Wofür: wenn einzelne sehr weite Fahrten das Problem sind, etwa weil sie eine Übernachtung oder einen freien Arbeitstag kosten.
Der Preis: Es zählt nur die eine Fahrt. Insgesamt wird meist mehr gefahren.
Acht Teams, A bis H, werden auf zwei Staffeln zu je vier verteilt. Die Entfernungen sind hier der Einfachheit halber gerade Linien auf einer Fläche, in km. Dafür gibt es 35 mögliche Aufteilungen. Der Staffelplaner hat für dieses Beispiel alle durchgerechnet, mit genau der Bewertung, die er auch für eine echte Liga benutzt. Jede Karte zeigt die Aufteilung, die ein Ziel wählt.
A B C H · D E F G
A B E H · C D F G
A B D H · C E F G
A B D E · C F G H
| Ziel | Gesamtstrecke | Längste Teamstrecke | Ausgleich | Längste Einzelfahrt |
|---|---|---|---|---|
| Gesamtstrecke minimieren | 703 km | 319 km | 200 km | 149 km |
| Team-Gesamtstrecken ausgleichen | 712 km | 248 km | 185 km | 102 km |
| Längste Team-Gesamtstrecke minimieren | 719 km | 246 km | 190 km | 106 km |
| Längste Einzelfahrt minimieren | 805 km | 272 km | 206 km | 94 km |
So unterschiedlich fallen die Antworten aus: Die kürzeste Gesamtstrecke (703 km) lässt das am stärksten belastete Team 319 km fahren. Wer stattdessen die längste Team-Gesamtstrecke minimiert, bringt dieses Team auf 246 km; dafür fährt die Liga insgesamt 16 km mehr. Die kürzeste längste Einzelfahrt (94 km) kostet gegenüber der kürzesten Gesamtstrecke 102 km. Ausgeglichen nach dem Mittelwert der Quadrate ist die Aufteilung mit 185 km.
Keine dieser Aufteilungen ist falsch. Welche passt, entscheidet die Liga.
Unter „Grenzen festlegen“ lassen sich zwei Obergrenzen setzen: für die Team-Gesamtstrecke und für eine Einzelfahrt. Sie gelten für jedes der vier Ziele.
Lassen sich die Grenzen einhalten, wird unter den Aufteilungen, die sie einhalten, die beste für das Ziel gesucht. Lassen sie sich nicht für alle Teams einhalten, wird die Überschreitung so klein wie möglich, und das geht dem eigentlichen Ziel vor.
Bei „Längste Team-Gesamtstrecke minimieren“ und „Längste Einzelfahrt minimieren“ wird die Überschreitung der Team-Grenze immer zuerst verglichen, das Ziel erst danach.
Bei „Gesamtstrecke minimieren“ und „Team-Gesamtstrecken ausgleichen“ sowie für die Grenze der Einzelfahrt bei allen Zielen wird jede Überschreitung mit einem Strafaufschlag verrechnet: Ein Kilometer über der Grenze zählt so viel wie 1.000 km Strecke, beim Ausgleich entsprechend mehr. In der Praxis geht die Grenze damit vor; ein mathematisch unbedingter Vorrang ist es dort nicht.
Bei Fahrzeit werden die Grenzen in Minuten angegeben.
In einer eigenen Liga lassen sich Derbys festlegen: zwei Teams, die in derselben Staffel spielen sollen. Ein Derby wirkt nur, wenn es neben den Zielen angehakt ist. Derbys, die sich ein Team teilen, bilden eine Gruppe, die zusammenbleibt.
Bei jedem Suchversuch kommt jede Gruppe in eine zufällig gewählte Staffel, und die Suche bewegt ihre Teams danach nicht mehr. Über die vielen Versuche hinweg kommt so jede Staffel an die Reihe. Passen die Gruppen nicht in die Staffeln, etwa weil eine Gruppe größer ist als eine Staffel, scheitert die Berechnung mit einer Meldung.
Ein Ergebnis, das ein angehaktes Derby trennt, trägt „Derby getrennt“ und zählt nicht als bester Wert. Jedes festgehaltene Derby schränkt die Suche ein, sie braucht dann meist länger. Am besten erst ohne Derbys rechnen: Oft landen Derbygegner ohnehin in einer Staffel.
Entfernungen werden auf ganze Kilometer bzw. Minuten gerundet. Jedes Maß hat seine eigenen Ergebnisse. Eine Aufteilung nach Fahrzeit kann anders aussehen als nach Fahrstrecke, weil Autobahn und Landstraße verschieden schnell sind.
Alle Aufteilungen durchzurechnen geht nur bei sehr kleinen Ligen wie im Beispiel. Schon für 80 Teams in vier Staffeln zu je 20 ist die Zahl der möglichen Aufteilungen eine Zahl mit 44 Stellen. Der Staffelplaner sucht deshalb gezielt, mit einer lokalen Suche mit Neustarts:
Wann die Suche aufhört: sobald die beste Aufteilung von 5 unabhängigen Starts aus wiedergefunden wurde (bei „Gesamtstrecke minimieren“) bzw. von 3 (bei den anderen Zielen), frühestens aber nach 10 Versuchen. Dann steht beim Ziel „sehr wahrscheinlich optimal“. Spätestens nach 5.000 Versuchen oder wenn das Zeitlimit erreicht ist, endet die Suche ebenfalls. Das Zeitlimit beträgt 10 Minuten je Berechnung, für alle gewählten Ziele zusammen; beim Ausprobieren ohne Konto 2 Minuten. Wurde die beste Aufteilung bis dahin nicht oft genug wiedergefunden, steht dort „nicht sicher“.
Was „sehr wahrscheinlich optimal“ heißt und was nicht: Einen Beweis, dass es keine bessere Aufteilung gibt, liefert diese Suche nicht. Dass viele voneinander unabhängige Versuche immer wieder bei derselben Aufteilung ankommen und keiner eine bessere findet, ist aber ein starkes Zeichen dafür.
Danach gleichen sich die Ziele ab: In der verbleibenden Zeit startet jedes Ziel noch einmal von den Aufteilungen aus, die die anderen Ziele gefunden haben. Findet es dabei etwas Besseres, ersetzt das sein Ergebnis.
Gespeichert wird je Ziel und Maß ein Ergebnis. Eine neue Berechnung ersetzt es nur, wenn sie besser ist, und beginnt bei der gespeicherten Aufteilung. Ein gutes Ergebnis geht also nie verloren. Starts von gespeicherten oder von anderen Zielen übernommenen Aufteilungen zählen nicht als Wiederfinden.
Ab 30 Teams beginnen die drei Ziele außer der Gesamtstrecke nicht bei einer völlig zufälligen Aufteilung, sondern bei einer, die vorher auf eine kurze Gesamtstrecke gebracht wurde. Ihre eigene Suche ist je Schritt deutlich langsamer und endet von zufälligen Starts aus an schlechteren Stellen.
Mit einer Grenze für die Team-Gesamtstrecke wird jeder zweite dieser Starts zusätzlich durchgeschüttelt: Etwa ein Sechstel der Teams tauscht zufällig die Staffel. Nur diese Starts zählen dann als Wiederfinden, weil die übrigen einander zu ähnlich sind.
Wie stark ein Tausch ein Ziel verändert, wird aus vorher berechneten Teilsummen bestimmt, ohne die ganzen Staffeln neu zu summieren. Deshalb schafft die Suche viele Versuche in kurzer Zeit.
Der Staffelplaner rechnet ausschließlich mit den Entfernungen zwischen den Spielorten, mit den Grenzen und Derbys, die festgelegt sind, und mit gleich großen Staffeln. Nicht in die Rechnung gehen unter anderem ein:
Die Ergebnisse zeigen, was die Wege angeht, die besten Möglichkeiten. Die Entscheidung über eine Staffeleinteilung bleibt bei denen, die sie verantworten.