Optimierung der Staffeleinteilung in der Fußball Landesliga Bayern in der Saison 2013/14 und Konzipierung vereinsfreundlicher Spielpläne
©2014
Masterarbeit
230 Seiten
Zusammenfassung
Das Ziel dieser Masterarbeit ist es, eine Einteilung der 90 Landesligisten in die fünf Staffeln zu bestimmen, so dass in jeder Staffel gleich viele Teams sind. Des Weiteren soll jedem der 90 Vereine garantiert werden, dass seine Mannschaft, an keinem Spieltag, der unter der Woche statt findet, länger als eine Stunde fahren muss. Die Fahrtzeit soll demnach an allen Wochentagsspielen höchstens 60 Minuten betragen. Diese Forderung ist vor allem deshalb sinnvoll, da die meisten Spieler und Trainer voll berufstätig sind oder studieren und bei weiten Auswärtsfahrten unter der Woche stets Probleme haben, rechtzeitig vom Arbeitsplatz bzw. von der Universität zum Spielort zu gelangen. Die Summe aller Fahrten aller Teams im Verlaufe der Saison soll aus Umweltschutzgründen und aufgrund einer Kosten- und Aufwandsminimierung für die Vereine und deren Spieler möglichst gering sein. Als mögliche Kriterien eignen sich hierbei die gesamte Fahrtstrecke bzw. die gesamte Fahrtzeit. Für die dadurch gegebene Gruppeneinteilung soll schließlich für jede der fünf Staffeln ein Spielplan konzipiert werden, der möglichst „fair“ ist, Wünsche der Vereine berücksichtigt und an Wochenspieltagen kein einziges Spiel enthält, bei dem die Gastmannschaft länger als eine Stunde anreisen muss. In Kapitel 4 wird diese Problemstellung mit allen ihren Bedingungen nochmals aufgegriffen und als ein binäres Programm formuliert.
Leseprobe
Inhaltsverzeichnis
Inhaltsverzeichnis
Abbildungsverzeichnis
1 Einleitung
1
1.1 Motivation
1
1.2 Problemstellung
2
1.3 Gang der Untersuchung
2
2 Grundlagen
4
2.1 Sportspezifische Grundlagen
4
2.2 Graphentheoretische Grundlagen
9
2.3 Grundlagen der Optimierung
14
3 Datenerfassung
25
3.1 Die Staffeleinteilung des Bayerischen Fussball-Verbandes
25
3.2 Rahmentermine und Spielpläne
28
3.3 Fahrtstrecken und Fahrtzeiten
30
4 Modellierung der Problemstellung
32
5 Die optimale Staffeleinteilung
42
5.0 Kapitelübersicht
42
5.1 Literaturüberblick
43
5.1.1 Verwandte Probleme
43
5.1.2 Algorithmisches Vorgehen und Ergebnisse
49
5.2 Existenz einer zulässigen Lösung
50
5.3 Technisches Vorgehen
62
5.4 Ein erster Versuch
64
5.4.1 Modellierung
64
5.4.2 Ergebnisse
70
5.5 Optimierung von (KWAYRESDIS)
71
5.5.1 Verbesserung der Modellierung
71
5.5.1.1 Verbessertes Modell
71
5.5.1.2 Ergebnisse
77
5.5.1.3 Stärken und Schwächen
80
5.5.1.4 Sensitivität
80
5.5.2 Fixierung von Variablen
84
5.5.2.1 Vorgehensweise
84
5.5.2.2 Ergebnisse
88
5.5.2.3 Stärken und Schwächen
95
5.5.3 Hinzufügen verletzter Bedingungen
96
5.5.3.1 Vorgehensweise
96
5.5.3.2 Ergebnisse
105
5.5.3.3 Stärken und Schwächen
108
5.6 Optimierung von (KWAYRESTIM)
109
5.6.1 Modellierung
109
5.6.2 Ergebnisse
113
5.6.3 Das Problem (MINTIM)
115
5.6.4 Vor- und Nachteile von (KWAYRESTIM) gegenüber
(KWAYRESDIS)
119
5.7 Zusammenfassung
119
5.8 Weitere Forschungsansätze
120
6 Die Spielplanerstellung
122
6.0 Kapitelübersicht
122
6.1 Theorie der ,,Breaks"
122
6.2 Die Spielplanformulierung als binäres Programm
132
6.2.1 Die Nebenbedingungen
132
6.2.2 Die Zielfunktion
135
6.2.2.1 Die Fairness eines Spielplans
135
6.2.2.2 Die Wünsche der Vereine
139
6.2.2.3 Kombination der Zielfunktionen aus 6.2.2.1 und
6.2.2.2
145
6.2.3 Ergebnisse
148
6.3 Dekomposition
149
6.4 Konzipierung der Spielpläne
151
6.4.1 Spielplan für die Landesliga Nordwest
151
6.4.1.1 Vorgehensweise
151
6.4.1.2 Ergebnisse
156
6.4.2 Spielplan für die Landesliga Nordost
163
6.4.2.1 Vorgehensweise
163
6.4.2.2 Ergebnisse
171
6.4.3 Spielplan für die Landesliga Mitte
176
6.4.3.1 Vorgehensweise
176
6.4.3.2 Ergebnisse
181
6.4.4 Spielplan für die Landesliga Südost
185
6.4.4.1 Vorgehensweise
186
6.4.4.2 Ergebnisse
191
6.4.5 Spielplan für die Landesliga Südwest
193
6.4.5.1 Vorgehensweise
194
6.4.5.2 Ergebnis
200
6.4.6 Bewertung der Spielpläne
201
6.5 Weitere Forschungsansätze
204
7 Zusammenfassung
207
Literaturverzeichnis
209
Lebenslauf
Abbildungsverzeichnis
Abbildung 1: Gespiegeltes DRRT für 4 Mannschaften
8
Abbildung 2: Ein Graph mit Knotenmenge = { , , , , } und Kantenmenge
= { ( , ), ( , ), ( , ), ( , ), ( , ), ( , ), ( , ) }
9
Abbildung 3: Der vollständige Graph mit Kantengewichten
12
Abbildung 4: Ein mögliches Matching auf dem Graphen aus Abbildung 2
14
Abbildung 5: Der
(mit gedachten Fahrtstrecken als Kantengewichte)
16
Abbildung 6: Der Graph
eingeschränkt auf Kanten mit einem Gewicht (Fahrtzeit)
von höchstens 60 und die Darstellung zweier disjunkter, perfekter Matchings
17
Abbildung 7: Begegnungen aus Abbildung 6
18
Abbildung 8: Die Staffeleinteilung des BFV
27
Abbildung 9: Rahmentermine der Landesliga Bayern
28
Abbildung 10: Vom DFB vorgeschlagener starrer Spielplan für 18 Mannschaften
29
Abbildung 11: Ermittlung der Fahrtzeit und Fahrtstrecke zwischen dem FSV Stadeln
und dem TSV Buch-Nürnberg mit Hilfe von bing
31
Abbildung 12: Heimbreak an Spieltag 2 (Staffel mit 18 Teams)
37
Abbildung 13: Nebenbedingungen des Modells aus Kapitel 4
39
Abbildung 14: Teil der Ausgabe von GUROBI für das Modell aus Kapitel 4
40
Abbildung 15: Das weitere Vorgehen: Erst Staffeleinteilung (Kapitel 5), dann die
Spielpläne (Kapitel 6)
41
Abbildung 16: Problemabgrenzung
49
Abbildung 17: Kreis der Länge 8 (links) und dessen Darstellung als bipartiter Graph
(rechts): Die Knotenmengen und erhält man beispielsweise, indem man die
Knoten des Kreises abwechselnd den Mengen und zuordnet
52
Abbildung 18: Der
eingeschränkt auf Kanten mit einer Kapazität 60 (Daten
der Spielzeit 2013/14): Auf die Angabe der Kantengewichte wurde verzichtet
54
Abbildung 19: Die beiden disjunkten perfekten Matchings (rot und schwarz) auf
dem Kreis geben die zwei verschiedenen Spieltage an
55
Abbildung 20: Ein Kreis der Länge 6 und ein Kreis der Länge 12 mit jeweils zwei
disjunkten perfekten Matchings. Zusammen haben die beiden 18 Knoten
56
Abbildung 21: Kreis (Teilgraph von ) mit 2 disjunkten perfekten Matchings und
18 Knoten impliziert mögliche Staffel 1
57
Abbildung 22: Kreis (Teilgraph von ) mit 2 disjunkten perfekten Matchings und
18 Knoten impliziert mögliche Staffel 2
57
Abbildung 23: Kreis (Teilgraph von H) mit 2 disjunkten perfekten Matchings und
18 Knoten impliziert eine mögliche Staffel 3
58
Abbildung 24: Kreis (Teilgraph von ) mit 2 disjunkten perfekten Matchings und
18 Knoten impliziert eine mögliche Staffel 4
58
Abbildung 25: Kreis (Teilgraph von ) mit 2 disjunkten perfekten Matchings und
18 Knoten impliziert eine mögliche Staffel 5
59
Abbildung 26: Der Kreis der Spieltage 2 und 6 aus Abbildung 10: Die erste Ziffer
bezeichnet das jeweilige Team aus Abbildung 10. Die Ziffer in Klammern stellt die
Identifizierung mit den Teams aus Abbildung 25 dar
60
Abbildung 27: Technisches Vorgehen bei der Lösung der nachfolgenden Probleme 64
Abbildung 28: Einschränkung der -Variablen
66
Abbildung 29: Von GUROBI gelieferte Ergebnisse für (KWAYRESDIS) und
(KWAYRESTIM) bei der Anwendung der Modelle ,,distanz.mod" bzw. ,,zeit.mod" 70
Abbildung 30: Auswahl von 4 Teams
75
Abbildung 31: Von GUROBI gelieferte Ergebnisse für (KWAYRESDIS) bei Einsatz
des Modells (ENTMOD)
77
Abbildung 32: Optimale Einteilung des Problems (KWAYRESDIS): In grün sind die
Teams markiert, die im Vergleich zur BFV-Einteilung einer anderen Staffel zugeteilt
sind
78
Abbildung 33: Unterschiede zwischen der BFV-Einteilung und der optimalen
Einteilung des Problems (KWAYRESDIS)
78
Abbildung 34: Die von GUROBI für (KWAYRESDIS) gelieferten zwei Spieltage unter
der Woche ohne Aussage über Heimrecht
79
Abbildung 35: Stärken und Schwächen des Ansatzes aus 5.5.1.1
80
Abbildung 36: Einfluss von
auf den Zielfunktionswert und die Laufzeit
81
Abbildung 37: Einfluss von
auf den Zielfunktionswert und die Laufzeit
83
Abbildung 38: Variablenfixierung und Staffeleinteilung im Iterationsprozess
88
Abbildung 39: Ergebnisse des Iterationsprozesses
94
Abbildung 40: Stärken und Schwächen des Vorgehens aus 5.5.2.1
95
Abbildung 41: Kreis der Länge 5
101
Abbildung 42: Graph |
( , )
bei dem jeder Knoten einen Grad deg( ) 2
hat und auf dem dennoch keine zwei perfekten disjunkten Matchings gefunden
werden können
101
Abbildung 43: Ergebnisse des Vorgehens aus 5.5.3.1
105
Abbildung 44: Bestimmung zweier disjunkter perfekter Matchings in den
fünf Staffeln
106
Abbildung 45: Gruppeneinteilung mit der kürzesten möglichen Gesamtfahrtstrecke:
Grün markiert sind die Vereine, die im Vergleich zur BFV-Einteilung einer anderen
Staffel zugeordnet wurden
107
Abbildung 46: Vor- und Nachteile des Vorgehens aus 5.5.3
108
Abbildung 47: Auswahl von 4 Teams
111
Abbildung 48: Von GUROBI gelieferte Ergebnisse für (KWAYRESTIM) bei Einsatz
des Modells (FAHRMOD)
113
Abbildung 49: Optimale Einteilung des Problems (KWAYRESTIM): In grün sind die
Teams markiert, die im Vergleich zur BFV-Einteilung einer anderen Staffel zugeteilt
sind
114
Abbildung 50: Unterschiede zwischen der BFV-Einteilung und der optimalen
Einteilung des Problems (KWAYRESTIM)
114
Abbildung 51: Von GUROBI gelieferte Ergebnisse für (MINTIM) 117
Abbildung 52: Optimale Einteilung für das Problem (MINTIM): In grün sind die
Teams markiert, die im Vergleich zur BFV-Einteilung einer anderen Staffel zugeteilt
sind
118
Abbildung 53: Vor- und Nachteile von (KWAYRESTIM)
119
Abbildung 54: Darstellung der Zielfunktionswerte im Vergleich zur BFV-Einteilung 120
Abbildung 55: Zulässige Breakfolgen nach Satz 6.16 für eine Liga mit 18 Teams
129
Abbildung 56: Zulässige Breakfolgen für eine Liga mit 18 Teams
130
Abbildung 57: Heim-Auswärts-Profil einer Mannschaft mit Auswärtsbreak an
Spieltag 7
131
Abbildung 58: Heim Auswärts-Profil einer Mannschaft mit einem Break an
Spieltag 9 und Saisonauftakt zu Hause
131
Abbildung 59: Platzierungen der Landesliga Nordwest Teams im Vorjahr
137
Abbildung 60: zufällig ausgewählte Wünsche der Teams in einer Liga mit 8
Mannschaften: Die Wünsche sind schon so angegeben, dass sie nur in der Hinrunde
(hier Spieltag 1 bis 7) auftreten
143
Abbildung 61: Problemübersicht
147
Abbildung 62: Ergebnisse der Optimierung von (WUNSCHMAX), (FAIRNESSMAX),
(KOMBIMAX), (WUNSCHMAXRES), (FAIRNESSMAXRES) und (KOMBIMAXRES)
mit GUROBI
148
Abbildung 63: FSTB-Ansatz für fiktive Liga
150
Abbildung 64: Identifizierung der Teams mit den Nummern des Spielplans aus
Abbildung 10: Die Ziffer hinter dem Ort gibt die Nummer an, für die der Ort im
statischen Spielplan eingesetzt werden muss
154
Abbildung 65: Das erste HAPS für Algorithmus 4: Rot markiert sind die Breaks, die
obere Zeile gibt den Spieltag an, die erste Spalte das Team. Eine Zeile entspricht
dem Heim-Auswärts-Profil einer Mannschaft
157
Abbildung 66: Das zweite HAPS für Algorithmus 4: Rot markiert sind die Breaks, die
obere Zeile gibt den Spieltag an, die erste Spalte das Team. Eine Zeile entspricht
dem Heim-Auswärts-Profil einer Mannschaft
158
Abbildung 67: Zuordnung von Teams zu Heim-Auswärts-Profilen des ersten HAPSs:
14 - bedeutet beispielsweise, dass Team 14 dem Profil E aus Abbildung 65
zugeordnet wird
159
Abbildung 68: Ergebnisse der einzelnen Iterationen
161
Abbildung 69: Der Spielplan für die Landesliga Nordwest: Dargestellt ist nur die
Hinrunde, die Rückrunde ist bis auf das getauschte Heimrecht in jeder Partie
identisch zur Hinrunde
162
Abbildung 70: Die Wünsche der Vereine
164
Abbildung 71: Wunschtableau
167
Abbildung 72: Zuordnung von Teams zu Heim-Auswärts-Profilen aus Abbildung 65,
die jeweils alle 36 Wünsche erfüllen: Die erste Spalte ist hierbei die von GUROBI
ausgegebene Lösung zu (MATCHHAPS), die anderen Zuteilungen wurden heuristisch
ermittelt
172
Abbildung 73: Ergebnisse der Team-Profil-Zuordnungen aus Abbildung 72
173
Abbildung 74: Der Spielplan für die Landesliga Nordost: Dargestellt ist nur die
Hinrunde, die Rückrunde ist bis auf das getauschte Heimrecht in jeder Partie
identisch zur Hinrunde
174
Abbildung 75: Wünsche der Landesliga Mitte
179
Abbildung 76: Wunschtableau
180
Abbildung 77: Team-Profil-Zuordnungen (zu den Profilen aus Abbildung 65) in der
Landesliga Mitte, die jeweils 34 der oben aufgeführten 36 Wünsche realisieren
182
Abbildung 78: Ergebnisse der Team-Profil-Zuordnungen aus Abbildung 77
183
Abbildung 79: Spielplan für die Landesliga Mitte
184
Abbildung 80: Stadionsperren des TSV Musterstadt
186
Abbildung 81: fiktive Wünsche und Platzsperren in der Landesliga Südost
189
Abbildung 82: Ergebnisse der Optimierung für die Landesliga Südost
191
Abbildung 83: Der Spielplan für die Landesliga Südost: Dargestellt ist nur die
Hinrunde, die Rückrunde ist bis auf das getauschte Heimrecht in jeder Begegnung
identisch zur Hinrunde
191
Abbildung 84: Anordnungsmuster zu Beginn (a) und die erste Rotation (b): Dabei
bedeutet das Team Heimrecht hat. Ein Spiel wird durch eine gestrichelte Kante
dargestellt
194
Abbildung 85: Spielplan nach dem Vorgehen von [DEW81]
196
Abbildung 86: Der Graph stellt den zweiten und den sechsten Spieltag dar
198
Abbildung 87: Ein Kreis für die Landesliga Südwest, der nur Kanten mit einem
Gewicht von maximal 60 enthält
199
Abbildung 88: Identifikation der Landesliga Südwest Vereine (erste Zahl in jedem
Kästchen) mit Nummern (zweite Zahl in jedem Kästchen) aus Abbildung 86
199
Abbildung 89: Ein Spielplan für die Landesliga Südwest: Dargestellt ist nur die
Hinrunde, die Rückrunde ist bis auf das getauschte Heimrecht in jeder Partie
identisch zur Hinrunde. Mannschaften, welche ein Break haben sind an den
beiden betroffenen Spieltagen rot markiert
200
Abbildung 90: Abschließende Übersicht zu Vor- und Nachteilen der fünf
präsentierten Verfahren zur Spielplangenerierung
202
Danksagung
Das Schreiben einer wissenschaftlichen Arbeit ist ohne eine sorgfältige
Literaturrecherche nicht möglich. Daher möchte ich mich zunächst bei allen
Mitarbeitern der Universitätsbibliothek Erlangen bedanken. Ein besonderer Dank
ergeht dabei an die Abteilung Fernleihe, welche äußerst zügig jede bestellte
wissenschaftliche Abhandlung bereitstellen konnte.
Darüber hinaus möchte ich mich sehr herzlich bei Herrn Prof. Dr. Alexander Martin
bedanken, der mehrfach ein offenes Ohr für Fragen, Probleme und Wünsche hatte und
mich zu zahlreichen Verbesserungen in dieser Arbeit anregte. Ohne Herrn Martin, der
mich schon im Laufe meines Studiums inspirierte, wäre ein Gelingen dieser Masterarbeit
nicht denkbar gewesen.
Aber auch an Herrn Andreas Heidt, der in wöchentlichen Gesprächen wertvolle
Anregungen zu dieser Ausarbeitung einbrachte und immer wieder Modifikationen
vorschlug, muss gebührender Dank ergehen.
Nicht vergessen werden darf an dieser Stelle Herr Andreas Bärmann, der die Anfänge
dieser Masterarbeit unterstütze.
Schließlich gilt mein herzlicher Dank auch noch Frau Christina Weber, die stets ein
offenes Ohr für jegliche Anliegen hatte.
Diespeck, im Mai 2014
Bastian Rückel
Vorwort
Im Rahmen des Vorwortes sollen dem Leser einige Hinweise zu dieser Masterarbeit
gegeben werden. Verwendete Quellen werden als [ABC10, S.100] gekennzeichnet. Dabei
kürzt ABC den (die) Autor(en) ab. Dieser Abkürzung folgt die Jahreszahl des
Erscheinens, gefolgt von der Seitenzahl, auf der die relevanten Inhalte zu finden sind.
Wurde eine Literaturquelle sinngemäß angewandt, so wird dies im Anschluss an den
Bereich, der aus dieser Quelle stammt durch
(vgl. [ABC10, S.100])
deutlich gemacht. Wurde ein Inhalt wörtlich übernommen, so befindet sich dieser Inhalt
in Anführungszeichen und endet mit der Quellenangabe
,, Text ([ABC10, S.100])."
Einige Male wurde zwar Literatur verwendet, aber inhaltlich abgeändert in diese Arbeit
übernommen. In diesem Falle wird die Quelle mit
(angelehnt an [ABC10, S.100])
angegeben. Bei Abbildungen, die einen anderen Urheber haben, wurde dies in der
Bildunterschrift durch
(aus [ABC10, S.100])
kenntlich gemacht. Eigens erstellte Abbildungen wurden mit dem Prädikat eigene
Darstellung versehen. Beziehen sich eigene Abbildungen auf eine Literaturquelle, so
wird dies als
eigene Darstellung nach [ABC10, S.100]
verdeutlicht. Zur Erstellung einiger Abbildungen wurde GeoGebra verwendet. Dies ist
ebenfalls in der Bildunterschrift vermerkt.
Es wird aber nicht nur auf verwendete Literatur verwiesen. An einigen Stellen ist auch
ein Vermerk zu anderen Abschnitten dieser Ausarbeitung angegeben. Die zusätzliche
Betrachtung dieser Textstellen oder Abbildungen kann durchaus der Veranschaulichung
dienen.
Im Verlauf der Arbeit tauchen immer wieder die Abkürzungen SRRT (Single Round
Robin Tournament) und DRRT (Double Round Robin Tournament) auf. Die Mehrzahl
dieser Begriffe wurde als SRRTs bzw. DRRTs abgekürzt. Ebenso wurde die Mehrzahl der
Home-Away-Pattern Sets (HAPS) als HAPSs abgekürzt.
Nun wünsche ich dem Leser viel Freude und Spannung an dieser Ausarbeitung.
1
1 Einleitung
1.1 Motivation
In den professionellen Sportligen der ganzen Welt werden jährlich Milliarden
umgesetzt.
Für die Spielzeit 2013/2014 erhält die deutsche Fußball Bundesliga
beispielsweise 560 Millionen Euro an Fernsehgeldern, 2014/2015 sind es 615 Millionen
und in der Saison 2015/2016 beläuft sich die Summe auf 663 Millionen. Dieser Betrag
wird ausschließlich unter den 36 Profiklubs der 1. und 2. Bundesliga aufgeteilt.
Zusätzlich können die Vereine noch Einnahmen in Millionenhöhe durch Merchandising
und Marketingmaßnahmen erwarten (vgl. [WEL13]). Ganz anders ist die Situation im
Breitensport. Der Deutsche Fußball Bund (DFB) beschreibt die Situation im
Amateurfußball als ,,Problemdruck im Bereich Finanzierung ([DFB12])". Als Ausgaben
sind dabei vor allem Aufwandsentschädigungen für Spieler, Honorare für Trainer und
Ablösesummen für wechselwillige Spieler zu nennen. 54,3 % der Sechstligisten zahlen
Aufwandsentschädigungen und 49 % aller Sechstligisten wären bereit für Neuzugänge
eine Ablösesumme zu bezahlen (vgl. [DFB12]). Im Rahmen dieser Arbeit geht es um
eben diese 6. Liga in Bayern. Ziel ist es, anhand der aufgezeigten Ergebnisse, einige
Erleichterungen für die zum Teil stark belasteten Vereine mit ihren größtenteils
ehrenamtlich tätigen Verantwortlichen und den voll berufstätigen Spielern zu schaffen.
Im Jahr 2012 entstand durch eine vom Bayerischen Fussball-Verband (BFV)
durchgeführte Strukturreform der Spielklassen im Amateurbereich die neue Landesliga
Bayern, welche nun nicht länger die fünfthöchste, sondern ab sofort die sechsthöchste
Liga im deutschen Fußball
ist. Schirmherr über diese Spielklasse ist der BFV (vgl.
[BFV14 (1)]). ,,
Die Landesliga der Herren spielt im Verbandsgebiet in funf Gruppen, die
in der Regel bis zu 18 Mannschaften umfassen ([BFV14 (1)])". In der Spielzeit
2013/2014 spielen somit insgesamt 90 Vereine auf 5 Staffeln verteilt in der Landesliga
Bayern. Diese Anzahl soll auch in den kommenden Jahren bestand haben, es kann jedoch
durch Auf- und Abstiegsszenarien passieren, dass die Normzahl von 90 Teams über-
bzw. unterschritten wird. Eine mögliche Abweichung wird in der jeweils nachfolgenden
Spielzeit korrigiert (vgl. [BFV13 (1)]). Die fünf Staffeln der Landesliga Bayern werden
2
anhand der Attribute ,,Nordwest", ,,Nordost", ,,Mitte", ,,Südwest" und ,,Südost"
unterschieden (vgl. [BFV14 (2)]).
1.2 Problemstellung
Das Ziel dieser Masterarbeit ist es, eine Einteilung der 90 Landesligisten in die fünf
Staffeln zu bestimmen, so dass in jeder Staffel gleich viele Teams sind. Des Weiteren soll
jedem der 90 Vereine garantiert werden, dass seine Mannschaft, an keinem Spieltag, der
unter der Woche statt findet, länger als eine Stunde fahren muss. Die Fahrtzeit soll
demnach an allen Wochentagsspielen höchstens 60 Minuten betragen. Diese Forderung
ist vor allem deshalb sinnvoll, da die meisten Spieler und Trainer voll berufstätig sind
oder studieren und bei weiten Auswärtsfahrten unter der Woche stets Probleme haben,
rechtzeitig vom Arbeitsplatz bzw. von der Universität zum Spielort zu gelangen. Die
Summe aller Fahrten aller Teams im Verlaufe der Saison soll aus Umweltschutzgründen
und aufgrund einer Kosten- und Aufwandsminimierung für die Vereine und deren
Spieler möglichst gering sein. Als mögliche Kriterien eignen sich hierbei die gesamte
Fahrtstrecke bzw. die gesamte Fahrtzeit. Für die dadurch gegebene Gruppeneinteilung
soll schließlich für jede der fünf Staffeln ein Spielplan konzipiert werden, der möglichst
,,fair" ist, Wünsche der Vereine berücksichtigt und an Wochenspieltagen kein einziges
Spiel enthält, bei dem die Gastmannschaft länger als eine Stunde anreisen muss. In
Kapitel 4 wird diese Problemstellung mit allen ihren Bedingungen nochmals
aufgegriffen und als ein binäres Programm formuliert.
1.3 Gang der Untersuchung
Nach einigen einführenden Worten und einer Erörterung der Problemstellung im
Abschnitt Einleitung werden in Kapitel 2 die für diese Arbeit grundlegende Sätze und
Definitionen dargestellt. Dabei wird immer wieder ein Bezug zur Problemstellung
hergestellt. In Kapitel 3 wird die durchgeführte Datenerfassung, in deren Rahmen alle
für diese Arbeit relevanten Daten zusammengetragen wurden, beschrieben. Anhand
dieser Daten werden in den späteren Abschnitten die Optimierungsprozesse
durchgeführt. Im Anschluss wird ein großes Modell vorgestellt, welches die soeben
3
erläuterte Problemstellung in seiner Gesamtheit beschreibt. Da dieses Modell für
handelsübliche Rechner zu groß ist, um es zu lösen, wird es in kleinere Teilprobleme
aufgeteilt. Die Vorteile dieser Aufteilung werden in den entsprechenden Paragraphen
beleuchtet. So wird zunächst eine optimale Gruppeneinteilung bestimmt. Anschließend
wird das Spielplanerstellungsproblem gelöst. Als Abschluss dieser Arbeit findet im
letzten Kapitel eine Zusammenfassung der Resultate statt. Den Kapiteln ,,Die optimale
Staffeleinteilung" und ,,Die Spielplanerstellung" wird aufgrund ihres Umfangs eine kurze
Übersicht über die dargelegten Inhalte vorausgestellt.
4
2 Grundlagen
In diesem Abschnitt werden alle Definitionen und Aussagen formuliert, die für diese
Ausarbeitung vorausgesetzt werden. Zur übersichtlicheren Darstellung findet eine
Aufteilung in die Bereiche ,,sportspezifische Grundlagen", ,,graphentheoretische
Grundlagen" und ,,Grundlagen der Optimierung" statt.
2.1 Sportspezifische Grundlagen
In der Einleitung wurden bereits Begriffe wie Mannschaft oder Team und Liga oder
Staffel verwendet. An dieser Stelle sollen für diese und weitere sportspezifische Begriffe
Definitionen angegeben werden, die zu einer einheitlichen Auffassung des jeweiligen
Begriffs führen.
Definition 2.1: Eine Mannschaft besteht aus Personen, die zusammen ein sportliches
Ziel erreichen wollen. Als Synonyme werden in dieser Arbeit auch Fußballmannschaft
oder (Fußball-) Team verwendet. Die Mannschaft spielt unter dem Namen eines
Vereins (vgl. [BAR01, S. 8]).
In einer Liga treten mehrere Mannschaften gegeneinander an. Dies bedeutet, dass eine
bestimmte Anzahl an Mannschaften, im hier gegebenen Problem sind das 18, in einer
Gruppe zusammengefasst werden. Etwas formaler wird dies in Definition 2.2
ausgedrückt:
Definition 2.2: Sei
. Eine Liga = { | = 1, ... , } ist eine Menge von
Mannschaften (vgl. [BAR01, S.9]).
Gibt es verschiedene Ligen, die eine annähernd gleiche Spielstärke der Mannschaften
aufweisen, so werden hierfür im Folgenden die Begriffe Staffel, Gruppe oder auch
Division synonym verwendet (vgl. [BAR01, S.29]). Für die Landesliga Bayern wird
angenommen, dass die fünf Staffeln, welche alle sechstklassig sind, in etwa das gleiche
sportliche Niveau aufweisen.
5
Der sportliche Vergleich zweier Mannschaften findet im Rahmen eines Spiels statt:
Definition 2.3: Ein Spiel = ( , ) ist ein 2-Tupel, welches sich aus den beiden
Mannschaften , ( ) zusammensetzt. Dabei gehören die beiden Mannschaften
und der gleichen Liga an. Als Synonyme werden auch die Bezeichnungen Paarung,
Partie oder Begegnung verwendet (vgl. [BAR01, S.9]).
Da das Tupel ( , ) geordnet ist, kann eine Aussage darüber getroffen werden, welche
Mannschaft zu Hause spielt und welche Mannschaft auswärts antreten muss. Daher
bezeichne im Nachfolgenden das Tupel ( , ) die Begegnung bei der die Mannschaft
Heimrecht im Spiel gegen die Mannschaft hat. Dementsprechend spielt Mannschaft
auswärts bei der Mannschaft . Das sogenannte Wettbewerbsprogramm
= { | = 1, ... , } ist eine Menge von Spielen , die in einer Liga stattfinden.
Spielt jedes Team genau zweimal gegen alle anderen Teams seiner Liga, so besteht das
Wettbewerbsprogramm aus
=
( - 1) Spielen (vgl. [BAR01, S.10]).
Bemerkung 2.4: Für die Landesligen in Bayern bedeutet dies, dass das
Wettbewerbsprogramm in jeder der fünf Staffeln, die jeweils 18 Mannschaften
umfassen, 18 17 = 306 Begegnungen beinhaltet.
Definition 2.5: Ein Spieltag ist ein vorgegebener Zeitraum, in dem Spiele aus dem
Wettbewerbsprogramm ausgetragen werden. An einem Spieltag trägt jede Mannschaft
genau ein Spiel aus, sofern die Anzahl der Mannschaften gerade ist. Andernfalls hat
genau eine Mannschaft kein Spiel an diesem Spieltag und ist somit spielfrei. Es ist
üblich, dass die Spieltage fortlaufend, bei 1 beginnend, nummeriert werden. Für das
Heimspiel von Team gegen Team an Spieltag schreibt man auch ( , ),
(vgl. [BAR01, S.11]).
Ein Spieltag kann über mehrere Kalendertage verteilt ausgetragen werden. Auch die
Uhrzeit, zu der die Spiele beginnen kann von Partie zu Partie variieren. Dies gilt für die
1.Bundesliga, in der üblicherweise ein Spiel am Freitag Abend, fünf Begegnungen
Samstag nachmittags, eine Partie am Samstag Abend und zwei Spiele am Sonntag
stattfinden, genauso, wie für die Landesligen (vgl. [BUN14]).
6
Satz 2.6: Sei die Anzahl der Mannschaften in Liga gerade. Dann finden an einem
Spieltag genau Paarungen statt. Für ungerades sind
Begegnungen anzusetzen.
Zusätzliche erhält eine Mannschaft den Status spielfrei (vgl. [BAR01, S.11]).
Bemerkung 2.7: Für Ligen mit 18 Mannschaften, sind dies 9 Partien pro Spieltag.
Definition 2.8: Unter einer Saison = { | = 1, ... , } versteht man eine Menge von
Spieltagen, an denen zusammen alle Paarungen des Wettbewerbsprogramms
durchgeführt werden (vgl. [BAR01, S.11]).
In der Landesliga Bayern spielt im Verlauf einer Saison jede Mannschaft zwei Mal
ein Mal zu Hause und ein Mal auswärts gegen jede andere Mannschaft seiner Staffel
(vgl. [BFV14 (1)]).
Definition 2.9: Ein Spielplan ist eine Menge von Spielen, welche auf Spieltage
verteilt angesetzt sind, so dass an jedem Spieltag jedes Team genau ein Spiel austrägt (1)
und das gesamte Wettbewerbsprogramm eingeplant wird (2). Formal muss demnach
gelten (vgl. [BAR01, S.12]):
, mit ( , ),
und
(
): ( , ),
(1)
= ( , ) mit ( , ),
(2)
Definition 2.10: Ein Spielplan, bei dem jede Mannschaft genau zwei Mal gegen jedes
andere Team ( ) seiner Liga spielt, wobei in genau einem der beiden Spiele
gegen Heimrecht hat, nennt man ein Double Round Robin Tournament (DRRT) (vgl.
[BRI10, S.366]).
Für eine Liga mit Mannschaften bedeutet dies, daß jede Mannschaft zwei Spiele
gegen jedes der anderen - 1 Teams bestreitet, insgesamt also
2 ( - 1) = 2 - 2
7
Partien. Daraus folgt aber nur unter der in Satz 2.11 dargestellten Einschränkung, dass
eine Saison auch aus 2 - 2 Spieltagen besteht.
Satz 2.11: Sei gerade. Dann besteht eine Saison, die nach den Prinzipien des
DRRTs ausgetragen wird, aus 2 - 2 Spieltagen (vgl. [BRI10, S.366]).
Ist die Anzahl der Mannschaft ungerade, so wird ein "Dummy-Team" mit der
Bezeichnung ,,Spielfrei" als ( + 1) -Team hinzugefügt (vgl. [BAR01, S.9]). Dies führt
dazu, dass =
+ 1 gerade ist. Daher werden
2 - 2 = 2 ( + 1) - 2 = 2
Spieltage ausgetragen. Im Folgenden wird davon ausgegangen, dass gerade ist. Dies ist
aufgrund der Möglichkeit des Hinzufügens eines "Dummy-Teams" ohne Beschränkung
der Allgemeinheit möglich (vgl. [BRI10, S.366]).
Bemerkung 2.12: In jeder Staffel der Landesliga Bayern gibt es in der Saison 2013/2014
genau 34 Spieltage. Diese werden nach dem Prinzip des im Nachfolgenden dargestellten
gespiegelten DRRTs ausgetragen (vgl. [BFV14 (1)]).
Definition 2.13: Ein Spezialfall des DRRTs ist das gespiegelte DRRT. Hier findet das
erste Spiel zwischen den Teams und ( ) in einer Liga mit
Mannschaften an Spieltag (
- 1) statt. Das zweite Spiel wird dann an Spieltag
+
- 1 mit getauschtem Heimrecht ausgetragen. Hierdurch wird der Spielplan in
zwei Hälften geteilt, welche man jeweils als Single Round Robin Tournament (SRRT)
bezeichnet (vgl. [BRI10, S.366]).
Die beiden Hälften des gespiegelten DRRT nennt man auch Hin- und Rückrunde. Die
Spieltage 1 bis - 1 bilden die Hinrunde. Die Rückrundenspieltage bis 2 - 2
finden nach Definition 2.12 in der gleichen Reihenfolge wie die Hinrundenspieltage statt.
Der Unterschied zwischen Hin- und Rückrunde, welche beim gespiegelten DRRT als
komplementär bezeichnet werden, liegt einzig im getauschten Heimrecht (vgl. [BAR01,
S. 11f.]). Durch das gespiegelte DRRT wird ein Spielplan dargestellt, der eine Aussage
darüber trifft, wann welches Spiel ausgetragen wird. Zur Veranschaulichung ist in
8
Beispiel 2.14 ein Spielplan für 4 Mannschaften nach den Prinzipien des gespiegelten
DRRT dargestellt.
Beispiel 2.14: In diesem Beispiel wird ein möglicher Spielplan für ein gespiegeltes DRRT
dargestellt. Die vier Mannschaften, die gegeneinander antreten sollen, seien der FC
Chelsea London, der FC Schalke 04, der FC Basel und Steaua Bukarest. Das
Wettbewerbsprogramm enthält 12 Partien, davon finden nach Satz 2.6 und Satz 2.11
genau 2 Begegnungen an jedem der 6 Spieltage statt.
Spieltag 1 Spieltag 2 Spieltag 3 Spieltag 4 Spieltag 5 Spieltag 6
Spiel 1
Schalke
Chelsea
Basel
Schalke
Schalke
Bukarest
Chelsea
Schalke
Schalke
Basel
Bukarest
Schalke
Spiel 2
Bukarest
Basel
Chelsea
Bukarest
Basel
Chelsea
Basel
Bukarest
Bukarest
Chelsea
Chelsea
Basel
Abbildung 1: Gespiegeltes DRRT für 4 Mannschaften (eigene Darstellung)
Bei genauerer Betrachtung dieses Spielplans fällt auf, dass sowohl Basel als auch
Bukarest mehrfach nacheinander zu Hause bzw. auswärts spielen.
Definition 2.15: Eine Mannschaft hat an Spieltag ein Heimbreak, wenn sie an
Spieltag - 1 und an Spieltag zu Hause spielt. Analog liegt ein Auswärtsbreak an
Spieltag vor, wenn das Team sowohl an Spieltag - 1 als auch an Spieltag
auswärts antreten muss. Im Folgenden wird nicht mehr explizit zwischen Heim- und
Auswärtsbreaks differenziert, sondern für beide einfach der Begriff Break verwendet
(vgl. [BRI08, S.41]).
Betrachtet man nochmals Beispiel 2.14, so erkennt man, dass der FC Basel an den
Spieltagen 3, 4 und 6 ein Break hat. Das Selbe gilt für Steaua Bukarest. Wann und wie
viele Breaks in einem Spielplan auftreten, wird in Kapitel 6 beschrieben.
2.2 Gra
Neben
immer
Grundk
Definiti
( ),
Knoten
möglich
des Gr
schreib
Abbildu
= { (
GeoGeb
Ist im F
endlich
Definiti
b
u
aphentheor
den sport
wieder
kenntnisse
ion 2.16: Ei
( ) . Die
n des Gr
herweise le
aphen be
ben (vgl. [CL
ung 2: Ei
, ), ( ,
bra)
Folgenden
her Graph b
ion 2.17: Se
benachbar
und zu
retische Gr
tspezifische
graphen
werden in
n endliche
e Menge (
raphen
.
eer und en
ezeichnet.
LA91, S.2])
in Graph
), ( , ), (
nichts and
betrachtet.
ei = ( ,
rt oder auc
(vgl. [CLA
rundlagen
en Begriffe
ntheoretisc
diesem Ab
r, schlichte
( ) = { , ...
Die Men
ndlich. Jede
Es ist übl
.
mit Kno
, ), ( , )
deres angem
) ein Grap
ch adjazen
A91, S.13ff
9
n
en werden
che
Begr
bschnitt dar
er, ungerich
... , } ist e
nge ( )
es ungeordn
lich statt
otenmenge
), ( , ), (
merkt, so w
ph und sei
nt in . Die
f.]).
n im Laufe
iffe
verw
rgestellt.
hteter Gra
endlich un
( ) =
nete Paar (
( ) und
= { , ,
, ) }
(e
wird stets e
= ( , )
e Kante =
e dieser A
wendet.
ph ist ein
d nichtleer
{ ( , ) |
( , ) (
( ) einfach
, , } un
igene
D
ein ungeric
. Dann
= ( , ) ist
Ausarbeitun
Die
wich
n geordnet
r und enth
, ,
) wird als
h kurz u
nd Kante
Darstellung
chteter, sch
heißen
dann inzid
ng auch
htigsten
tes Paar
hält alle
} ist
s Kante
und zu
nmenge
g
mit
hlichter,
und
dent zu
10
Definition 2.18: Sei = ( , ) ein Graph und sei ein Knoten in . Der Grad deg( )
von Knoten entspricht der Anzahl der Kanten in , zu denen Knoten inzident ist
(vgl. [CLA91, S.14]):
deg( ) = | { | st inzident zu } |
Definition 2.19: Sei ein Graph. Eine Kantenfolge = { , ... , } mit (1 )
heißt Weg von nach , falls = (
, ) mit (1 ) und
=
sowie
= (vgl. [DOM07, S.2f.]). Geläufig ist für den Weg von nach auch die
Schreibweise =
-
-. . . -
-
= .
Die Definition eines Weges in einem ungerichteten Graphen führt nun unmittelbar zum
Begriff des Kreises.
Definition 2.20:
Ein Weg = ( , ... , ) von nach ist ein Kreis in , falls gilt:
=
Ein Kreis heißt einfach, falls in der Kantenfolge kein Knoten, ausgenommen Start- und
Endknoten, mehr als ein Mal vorkommt (vgl. [GUR10, S.33]).
Die in den Definitionen 2.17 bis 2.20 vorgestellten Begriffe sollen durch das folgende
Beispiel 2.21, welches sich auf Abbildung 2 bezieht, veranschaulicht werden.
Beispiel 2.21: Der Grad der Knoten des Graphen in Abbildung 2 beträgt:
deg( ) = 3, deg( ) = 4, deg( ) = 3, deg( ) = 2 und deg( ) = 2
Ein Weg von nach ist beispielsweise gegeben durch die Kantenfolge - - - .
Die Kantenfolge - - - stellt ein Beispiel für einen Kreis dar.
An dieser Stelle möchte ich noch einmal auf die Problemstellung aus Abschnitt 1.2
zurückkommen. Gegeben sind 90 Vereine, deren geografische Lage über ganz Bayern
verteilt ist. Es ist natürlich möglich, mit dem PKW von jedem der 90 Orte zu jedem
Anderen zu gelangen. Hierfür wird unterstellt, dass Hin- und Rückweg identisch sind.
Modelliert man nun als Ausgangssituation den Spielort jedes Vereins durch einen
11
Knoten in einem Graphen = ( , ) und den Fahrtweg zwischen je zwei
Spielorten und ( ) durch eine ungerichtete Kante = ( , ) , und
dies für alle und mit , so erhält man einen Graphen , in dem jeder
Knoten mit jedem anderen Knoten { } benachbart ist. Die beiden Knoten
,
( ) sind inzident zur Kante = ( , ) . Spezifiziert wird diese
Modellierung durch Definition 2.21:
Definition 2.22: Ein vollständiger (ungerichteter) Graph = ( , ) ist ein schlichter
Graph, in dem jeder Knoten mit jedem anderen Knoten durch eine Kante verbunden ist:
= { , ... , }
=
,
,
, 1 < }
Man schreibt für einen vollständigen Graphen mit Knoten (vgl. [LAU04, S.117]).
Der vollständige Graph
beschreibt demnach die oben dargestellte Ausgangssituation
zur Staffeleinteilung in der Landesliga Bayern.
Satz 2.23: In einem vollständigen Graphen mit Knoten ist die Anzahl der Kanten
(
)
(vgl. [LAU04, S.117]).
Beispiel 2.24: Gegeben sei der vollständige Graph
. In diesem Graphen gibt es
= 4005 Kanten.
Der Graph, der die Ausgangsituation der Einteilung der fünf Landesligen in Bayern
modelliert, ist vollständig und hat 4005 Kanten. Jedoch ist hierdurch noch kein
Kriterium zur Einteilung von je 18 Teams in jede der fünf Staffeln der Landesliga
gegeben. Um ein solches konstruieren zu können, muss man erst die Kanten gewichten.
Definition 2.25: Ein gewichteter Graph ist ein Graph = ( , ), in dem jeder Kante
ein Gewicht zugeordnet wird. Hierzu wird eine Gewichtsfunktion
:
verwen
[COR01
Als mö
dessen
Fahrtze
optimal
von Kap
Definiti
Die Zu
disjunk
gleiche
Abbildu
GeoGeb
Hat ma
so spiel
Da natü
Division
= (
ndet. Für
1, S.532]).
gliche Kan
Kanten d
eiten von
le Einteilun
pitel 2.3 un
ion 2.26: Se
uordnung j
kten Menge
= gilt, b
Kardinalit
ung 3: Der
bra)
an nun eine
lt im Laufe
ürlich auch
n erreichba
, ) ( =
alle
ntengewich
den Fahrtw
Spielort zu
ng unter Ei
nd von Kap
ei = ( ,
jedes Kno
en , ... ,
bezeichnet
tät, so spric
vollständi
e Graph Eq
einer Saiso
h hier jeder
ar ist, indu
1, ... ,5) de
bezeichnet
hte für den
weg beschr
u Spielort.
inhaltung a
itel 5.
) ein Grap
ten der
(
t man als P
cht man von
ge Graph
quipartition
on jede Ma
r Ort innerh
uziert die G
es vollständ
| | =
12
t ( ) das
n oben besc
reiben, eig
. Wie man
aller releva
ph mit | | =
Knotenme
= 1, . .
Partition d
n Graph Eq
mit Kan
n der 90 La
annschaft g
halb einer
Gruppenein
digen Graph
= 18 =
Gewicht
chriebenen
gnen sich
n anhand
anten Restr
= und se
nge in g
, ), wobe
es Graphen
quipartitio
ntengewich
andesligist
egen jedes
Division vo
nteilung fün
hen
. Hi
1, ... ,5
der jewei
n vollständ
die Fahrts
der Kanten
riktionen b
ei 2 ein
genau eine
ei | | =
n. Haben al
on (vgl. [SO
hten (eigen
en in fünf
andere Te
on jedem a
nf vollständ
erbei gilt:
iligen Kan
digen Graph
strecken b
ngewichtu
estimmt, is
ne natürlic
e von pa
, ... , | | =
lle ( =
OT12, S.1]).
ne Darstellu
Staffeln ge
eam seiner
anderen Or
dige Unterg
te (vgl.
hen
,
bzw. die
ng eine
st Inhalt
che Zahl.
arweise
=
mit
1, ... , )
.
ung mit
efunden,
Gruppe.
rt dieser
graphen
13
= { ( , ) | , , } = 1, ... ,5
Etwas allgemeiner wird dies in Definition 2.27 und der nachfolgenden Erläuterung
dargestellt:
Definition 2.27: Seien = ( , ) ein ungerichteter Graph und eine Teilmenge der
Knotenmenge von . heißt Clique in , falls gilt (vgl. [GUR10, S.28]):
( , ) für alle , mit
Dies impliziert, dass eine Lösung des Problems aus 1.2 eine Partition des vollständigen
Graphen
in Cliquen mit jeweils 18 Knoten ist, denn es sind nur noch Kanten relevant,
die zwischen zwei Mannschaften der gleichen Staffel verlaufen. Zwischen Teams
unterschiedlicher Staffeln finden keine Spiele statt. Daher sind diese Kanten für den im
Laufe dieser Arbeit bestimmten Zielfunktionswert (vgl. Kapitel 2.3) uninteressant. Auch
hierauf wird in den Abschnitten 2.3 und 5 genauer eingegangen. Bei den obigen
Ausführung wurde erneut unterstellt, dass Hin- und Rückweg identisch sind, so dass
eine einzige ungerichtete Kante für die Modellierung des Fahrtwegs zwischen zwei
Orten genügt. Dabei ist es zunächst unwesentlich, dass diese Kante während einer
Saison eigentlich vier Mal (jede Mannschaft muss hin und zurück fahren und spielt ein
Mal daheim und ein Mal auswärts gegen jeden Gegner) abgefahren wird. Es wird in der
Modellierung zunächst von einer Fahrt über diese Kante ausgegangen und erst in der
Interpretation der Ergebnisse mit dem Faktor 4 multipliziert.
Ein weiterer graphentheoretischer Begriff, der in dieser Ausarbeitung noch von
Bedeutung sein wird, ist das Matching.
Definition 2.28: Sei = ( , ) ein Graph. Ein Matching ist eine Teilmenge der
Kantenmenge, so dass keine zwei Kanten aus einen gemeinsamen Knoten haben. Ist
jeder Knoten der Knotenmenge in genau einer Kante aus , so nennt man ein
perfektes Matching. Die Größe des Matchings ist durch die Anzahl der Kanten in
gegeben (vgl. [GUR10, S.45]).
Abbildu
Darstel
Als Bei
durch d
Allerdin
enthalt
enthält
2.3 Gru
In dies
welche
definier
zudem
werden
Definiti
vier Ko
·
·
ung 4: Ein
llung mit Ge
spiel sei hi
die rot gek
ngs ist die
en ist. Die
.
undlagen d
sem Absch
zur Lösun
rt werden
zur Besch
n.
ion 2.29: ,,E
mponenten
: die Men
( ) für
n mögliche
eoGebra)
ier nochma
kennzeichn
eses nicht
e Größe de
der Optimie
nitt sollen
g des gegeb
soll, ist das
hreibung de
Ein kombin
n:
nge der (Pr
: die Me
es Matchin
als der Gra
neten Kant
perfekt, d
es Matchin
erung
Grundlag
benen Prob
s kombinat
er Staffelei
atorisches
roblem)-Ins
enge der zu
14
ng auf dem
aph aus Ab
ten ein mö
da der Kno
ngs beträgt
en im Ber
blems notw
torische Op
inteilung u
Optimieru
stanzen, Ei
u Eingabe
m Graphen
bildung 2
gliches Ma
oten in k
t zwei, da
reich Optim
wendig sind
ptimierung
und der Sp
ungsproblem
ngaben
zulässigen
n aus Abb
angeführt.
atching auf
keiner Kan
das Match
mierung vo
d. Der erste
gsproblem.
pielplanerst
m ist cha
n Lösungen
bildung 2
Abbildung
f diesem G
nte des Ma
hing zwei
orgestellt w
e Grundbeg
Dieser Beg
tellung ver
arakterisier
n
(eigene
g 4 zeigt
Graphen.
atchings
Kanten
werden,
griff, der
griff soll
rwendet
rt durch
15
· Die Bewertungs- oder Maßfunktion : ( )
· ziel {
,
}
Gesucht ist zu eine zulässige Lösung
( ), so dass
= ziel { ( ) | ( )}.
( ) ist der Wert der zulässigen Lösung ([WAN06, S.8f.])."
Das
Hauptziel
dieser Arbeit
ist
das
Lösen
zweier
kombinatorischer
Optimierungsprobleme. Es soll zunächst eine Gruppeneinteilung gefunden werden, in
der die Summe aller Fahrtstrecken (alternativ die Fahrtzeiten) minimiert wird und die
jeder Mannschaft garantiert, dass sie an keinem Wochenspieltag länger wie 60 Minuten
fahren muss. Anschließend soll ein Spielplan konzipiert werden, der die Fahrtbedingung
unter der Woche einhält. Diese beiden Optimierungsprobleme sollen in den Beispielen
2.30 und 2.32 anhand von Definition 2.29 beschrieben werden.
Beispiel 2.30: Gesucht ist eine Einteilung der 90 Teams in fünf Staffeln zu je 18 Teams,
welche die Spieltagsbedingungen (Fahrtzeiten sind alle maximal eine Stunde) unter der
Woche einhält. Dieses Problem wird im Folgenden als (KWAYRES) bezeichnet. Dabei
wird an dieser Stelle noch kein Minimierungsziel spezifiziert. Im weiteren Verlauf dieses
Beispiels werden allerdings noch zwei mögliche Varianten von Zielfunktionen
vorgestellt.
Wie in der Datenerfassung in Kapitel 3 ausgeführt wird, gibt es genau 2 Spieltage, die
nicht am Wochenende ausgetragen werden.
·
= { <
, ,
> |
ist vollständiger Graph auf 90 Knoten,
: Kantengewichtung bzgl. Fahrtstrecken,
: Kantengewichtung bzgl. Fahrtzeiten }
·
K
b
Hierbei
Kanten
Kanten
perfekt
der Wo
A
D
·
1
e
K
(
F
(<
,
(alternativ
Kardinalitä
bezüglich d
i bezeichne
der fünf C
weglässt,
ten, disjunk
oche stattfin
Abbildung
Darstellung
1
Die Wah
erläuterte
Kantengew
(KWAYRE
|
ist vo
Fahrtzeiten
,
>) = {
v
bezügli
ät 18 und e
der Kanten
et
|
( ,
)
Cliquen, au
die eine F
kten Match
nden. Zur V
5: Der
g mit GeoG
hl von
:
Problem
wichte von
STIM). Im
ollständige
n }
|
bes
ich
:
s existieren
gewichtun
)
den Teilg
us denen
Fahrtzeit v
hings auf
Veranschau
(mit geda
Gebra)
als
(KWAYR
n
brauch
Fall (KWA
er Graph au
16
steht bezüg
)
1
au
n auf
|
( ,
ng :
graphen vo
besteht, m
von mehr
|
( ,
)
ind
ulichung so
achten Fah
Kantenge
RESDIS) n
ht man fü
AYRESTIM
uf 90 Knote
glich der Ka
us 5 paarw
,
)
zwei d
}
on
, den
mit den Fa
als 60 Min
duzieren di
llen die Ab
rtstrecken
ewichte vo
nötig, die
r das auf
M) genügt a
en, :
antengewic
eise disjun
disjunkte, p
man erhä
hrtzeiten g
nuten aufz
e beiden S
bildungen
als Kante
on
ist fü
Wahl v
f S.18f. er
als Eingabe
Kanten
chtung :
nkten Cliqu
perfekte Ma
ält, wenn m
gewichtet u
zeigen. Die
pieltage, d
5 und 6 die
ngewichte,
ür das au
von :
rläuterte P
e = { <
ngewichtun
en der
atchings
man die
und alle
beiden
ie unter
enen.
, eigene
uf S.18f.
als
Problem
,
>
ng bzgl.
In Abbi
aufgeze
zwische
(alterna
der Abb
werden
gewicht
entfern
von Or
|
( ,
die zwe
weitere
Problem
Matchin
möglich
geben h
Partien
beiden
einem S
Abbildu
höchste
Darstel
ildung 5 is
eigt. Da jed
en je zwei
ativ die Fah
bildung we
n alle Kan
tet und die
nt. Beispiel
rt A nach C
)
für ledig
ei disjunkt
en Kanten
ms aus 1.2
ng bezügli
he Spieltag
hierbei die
n des ander
Knoten, d
Spieltag geg
ung 6: Der G
ens 60 un
llung mit Ge
st eine der
der Ort von
Knoten di
hrtzeiten)
eggelassen,
nten der in
e Kanten m
sweise bed
C bzw. von
glich eine St
ten, perfekt
mit einem
2 muss in
ch der Fa
ge, die unt
e Begegnun
ren Spielta
die zu eine
geneinande
Graph
e
nd die Dar
eoGebra)
r fünf Cliqu
n jedem an
ieser Cliqu
zwischen d
, um nicht
n Abbildun
mit einem
deutet das
n C nach A
taffel wiede
ten Matchi
m Gewicht
jeder der
hrtzeiten h
ter der Wo
ngen des e
gs. Die Inte
er Kante in
er antreten
eingeschrä
rstellung z
17
uen, die sic
nderen Ort
e. Als Kant
den jeweili
an Übersic
ng 5 darg
Gewicht, w
Gewicht 5
A 55 Minu
er. Die rote
ings an. Di
t von höch
r fünf Staf
haben, den
oche stattf
einen Spielt
erpretation
nzident sin
n.
nkt auf Kan
zweier dis
ch bei der
t aus erreic
tengewicht
gen Knoten
chtlichkeit
gestellten C
welches ech
55 der Kan
uten beträg
en und die g
e übrigen,
hstens 60.
ffeln ein s
nn die bei
finden kön
tags an, di
n der Matc
nd, stellen
nten mit ei
sjunkter, p
Gruppenei
chbar ist, g
te werden
n ,,gedacht"
zu verliere
Clique mit
ht größer a
nte ( , ), d
gt. Die Abb
grünen Kan
schwarzen
Jede zulä
olches disj
den Match
nnen, dar.
e grünen K
hingkanten
zwei Team
nem Gewic
perfekter M
inteilung e
gibt es ein
die Fahrts
". Diese wu
en. In Abbi
t den Fah
als 60 ist,
dass die F
bildung 6
nten geben
n Kanten s
ässige Lösu
junktes, pe
hings stelle
Die roten
Kanten lief
n ist wie fo
ms dar, we
cht (Fahrtz
Matchings
ergeben,
e Kante
strecken
urden in
ildung 6
rtzeiten
werden
ahrtzeit
spiegelt
n hierbei
sind alle
ung des
erfektes
en zwei
Kanten
fern die
olgt: Die
elche an
zeit) von
(eigene
18
Durch Abbildung 6 werden nun anhand der beiden disjunkten Matchings die zwei
folgenden Spieltage (nur Paarungen, keine Aussage über Heimrecht) induziert:
Spieltag 1
Spieltag 2
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
Abbildung 7: Begegnungen aus Abbildung 6 (eigene Darstellung)
· Die Bewertungsfunktion (vgl. [OOS01, S.209]):
(
) =
( , )
( , )
(I)
Dabei bezeichnen die ( = 1, ... ,5) die fünf (zulässigen) disjunkten Cliquen und
( , ) das Gewicht (Fahrtstrecke) der Kante ( , )
( {1, ... ,5}) . In die
Berechnung fließen nur Kanten innerhalb der fünf Cliquen ein, da es keine Fahrten
zwischen Teams unterschiedlicher Staffeln gibt. Alternativ könnte man zur Berechnung
des Zielfunktionswertes die Kanten auch mit den Fahrtzeiten gewichten, wodurch die
Fahrtstrecken als Gewichte und somit auch als Eingabe überflüssig wären:
(
) =
( , )
( , )
(II)
Ist die Wahl der Zielfunktion für die Argumentation relevant, so werden die beiden eben
dargestellten Varianten des Problems (KWAYRES) im Folgenden unterschiedlich
bezeichnet. Bezieht sich die Zielfunktion auf die Fahrtstrecken (I), so wird das Problem
mit (KWAYRESDIS) abgekürzt. Bezieht sich die Zielfunktion auf die Fahrtzeiten (II), so
19
bezeichne (KWAYRESTIM) die zugehörige Optimierungsaufgabe. Ist die Wahl der
Zielfunktion nicht von Bedeutung, so wird weiterhin die Abkürzung (KWAYRES)
verwendet. In diesem Fall gelten die für (KWAYRES) getroffenen Aussagen sowohl für
(KWAYRESDIS) als auch für (KWAYRESTIM).
· ziel =
Das Ziel dieses kombinatorischen Optimierungsproblems ist klar. Die Zielfunktion soll
minimiert werden, damit der Aufwand für die Vereine möglichst gering ist.
Bemerkung 2.31:
In den Ausführungen in Kapitel 5 soll bei (KWAYRESDIS) bzw.
(KWAYRESTIM) zusätzlich darauf geachtet werden, dass kein Team eine zu weite bzw.
eine zu lange Fahrt absolvieren muss. Diese jeweilige Forderung stellt bei beiden
Optimierungsvarianten eine weitere Bedingung an eine zulässige Lösung dar und wird
in Kapitel 5 spezifiziert.
Beispiel 2.32: Ist eine optimale Einteilung gefunden, so muss in jeder Staffel ein
Spielplan konzipiert werden, der an den beiden Spieltagen, welche unter der Woche
stattfinden, kein Spiel enthält, bei dem die Gastmannschaft länger als eine Stunde fahren
muss. Des Weiteren soll der Spielplan kein Team benachteiligen und es sollen möglichst
viele Wünsche der Vereine erfüllt werden. Die Formulierung dieser Anforderungen als
kombinatorisches Optimierungsproblem soll nun (für eine Staffel) dargestellt werden:
·
= = {1, ... ,18} ist eine Liga mit 18 Mannschaften }
·
() = { | ist ein Spielplan im gespiegelten DRRT - Format mit 48 Breaks
2
,
der kein Spiel enthält, bei dem die Gastmannschaft unter der Woche länger als 60
Minuten fahren muss }
· Die Zielfunktion:
() =
() +
()
Hierbei beschreibt die Funktion : die Fairness des Spielplans. Die Funktion
: stellt die Anzahl der erfüllten Wünsche der Mannschaften dar. Durch die
2
Dies ist die minimale Anzahl an Breaks in einem Spielplan für 18 Teams im
gespiegelten DRRT-Format. Ausführlich wird hierauf in Kapitel 6 eingegangen
20
Gewichte ,
mit
+
= 1, ist es möglich, die Fairness und die Anzahl der
erfüllten Wünsche unterschiedlich stark in den Zielfunktionswert einfließen zu lassen
(vgl. [BAR01, S.79ff.]). Die genaue Konstruktion der Funktionen und ist Inhalt von
Paragraph 6.
· ziel =
Selbstverständlich muss es das Ziel der Spielplanerstellung sein, möglichst viele
Wünsche der Vereine zu erfüllen und einen fairen Spielplan zu erzeugen. Deshalb soll
der Zielfunktionswert maximiert werden.
,,Das Ziel der kombinatorischen Optimierung besteht (...) darin, Algorithmen zu
entwerfen, die (erheblich) schneller als die Enumeration aller Lösungen sind.
Kombinatorische und ganzzahlige Optimierungsprobleme stehen in enger Beziehung
([GRÖ97, S.12])", denn kombinatorische Optimierungsprobleme können als lineare oder
ganzzahlige Programme formuliert werden (vgl. [GEI02, S.129]).
Definition 2.33: Seien
, , und {1, ... , }. Dann nennt man
max
. .
ein gemischt ganzzahliges lineares Programm (MIP) (vgl. [MAR13, S.232]).
Die folgende Definition 2.34 beschäftigt sich mit Spezialfällen des gemischt ganzzahligen
linearen Programms aus 2.33:
21
Definition 2.34: Gegeben sei das gemischt ganzzahlige lineare Programm aus 2.33. Für
dieses gibt es die folgenden Spezialfälle (vgl. [MAR13, S.232]):
·
= 0
(
) :
max
. .
·
=
( ) :
max
. .
·
= und {0,1} (
ä
):
max
. .
{0,1}
Besonders das binäre Programm wird in dieser Arbeit noch von großer Bedeutung sein,
denn in den Kapiteln 4, 5 und 6 werden die in den Beispielen 2.30 und 2.32 formulierten
kombinatorischen Optimierungsprobleme als binäre Programme formuliert und mit
deren Hilfe gelöst.
Definition 2.35: Bei einem Entscheidungsproblem soll eine Entscheidung (ja oder nein)
zu einer gestellten Frage getroffen werden (vgl. [BOR01, S.415]).
Definition 2.36: Die Komplexitätsklasse P umfasst die Menge aller
Entscheidungsprobleme, zu deren Lösung es einen Polynomzeitalgorithmus gibt (vgl.
[SCH98, S.18]).
Definition 2.37: ,,Ein Entscheidungsproblem liegt in der Komplexitätsklasse NP, falls
22
ein Polynom
und einen Polynomzeitalgorithmus existieren, der für jede Eingabe
und jedes mögliche Zertifikat der Länge höchstens
(| |) einen Wert ( , )
berechnet, so dass gilt:
1. Lautet die Antwort zur Eingabe ,,Nein", dann gilt ( , ) = 0 für alle möglichen
Zertifikate.
2. Lautet die Antwort zur Eingabe ,,Ja", dann gilt ( , ) = 1 für wenigstens ein
Zertifikat ([MEI98, S.17])".
Die Komplexitätsklasse NP besteht demnach aus Problemen, für die eine Lösung in
polynomieller Laufzeit als korrekt verifiziert werden kann (vgl. [COR07, S.984]). Jedes
Problem aus der Komplexitätsklasse NP kann durch die vollständige Enumeration aller
Lösungskandidaten gelöst werden (vgl. [KAR09, S.63]). Offensichtlich gilt P NP. Ob
auch P = NP gilt ist bislang unbekannt (vgl. [COR07, S.984]).
Definition 2.38: Ein Entscheidungsproblem heisst NP-vollständig, wenn
·
NP
(1)
·
NP:
(2)
Die zweite Bedingung (2) fordert, dass es für alle
NP eine Polynomzeitreduktion
( ) von
auf gibt. Deshalb ist mindestens genauso schwer lösbar wie jedes andere
Problem aus der Klasse NP. Probleme, welche die zweite Bedingung erfüllen, nennt man
NP-schwer (vgl. [WEG05, S.46]).
Definition 2.39: ,,Ein Optimierungsproblem heißt NP-schwer, wenn das zugehörige
Entscheidungsproblem NP-vollständig ist ([BOR01, S.423])".
Bislang ist kein Polynomzeitalgorithmus zur Lösung eines NP-vollständigen bzw. NP-
schweren Problems und somit aller NP-vollständigen bzw. aller NP-schweren Probleme
bekannt (vgl. [COR07, S.971]). Zu entscheiden, ob ein rationales Ungleichungssystem
(vgl. 2.33 mit
, ) eine ganzzahlige Lösung besitzt ist NP-
vollständig. Das Lösen eines (gemischt) ganzzahligen linearen Programms ist NP-
23
schwer. Man kann also nicht davon ausgehen, eine beweisbar optimale Lösung in
polynomieller Laufzeit zu finden. Das Gleiche gilt für binäre Programme (vgl. [SCH98,
S.245ff.] & [COO71, S.151ff.]). Exakte Verfahren zur Lösung von (gemischt) ganzzahligen
linearen Programmen durchsuchen den gesamten Lösungsraum. Daher garantieren sie,
dass nach endlicher, aber im schlechtesten Fall exponentieller Laufzeit die optimale
Lösung gefunden wird (vgl. [SCH98, S.360ff.]). Das exakte Verfahren, welches hier
beschrieben werden soll, ist das Branch-and-Bound-Verfahren nach dem Algorithmus
von Dakin (1965):
Algorithmus 1 (vgl. [DAK65, S.250ff.]):
Input: Ein (gemischt oder rein) ganzzahliges lineares Programm
mit rationalen
Daten (vgl. Definition 2.33 & 2.34)
Output: Eine optimale Lösung oder die Meldung, dass es keine zulässige Lösung gibt
1. Initialisierung:
a. Setze die untere Schranke:
-
b. Setze die Kandidatenliste = {
}
c. Setze 0
d. Lege Speicherplatz für die beste bisher gefundene Lösung
an
2. IF = { } THEN STOP und gib aus:
a. IF
= -: Es gibt keine zulässige Lösung
b. IF
> -:
ist optimaler Zielfunktionswert
3. Branching: IF { } THEN wähle
4. Bounding: Löse das zu gehörende relaxierte Maximierungsproblem
5. IF
= { } or IF
ist unbeschränkt auf
THEN STOP und gehe zu (2)
6. IF
{ } and
ist beschränkt auf
THEN
ist optimaler Punkt für
und
=
ist optimaler Zielfunktionswert von
7. IF
THEN entferne aus , gehe zu (2)
8. IF
and
erfüllt alle Ganzzahligkeitsbedingungen THEN setze
und
. Entferne aus , gehe zu (2)
9. IF
and
verletzt mindestens eine Ganzzahligkeitsbedingung
(
) THEN entferne aus und setze:
24
{ |
floor
}
{ |
ceil
}
Setze + 2 und gehe zu (2)
Ergänzt man einen Branch-and-Bound-Algorithmus um Schnittebenenverfahren, so
spricht man von einem Branch-and-Cut Verfahren. Hierbei sei vor allem auf die Arbeit
von Johnson und Padberg verwiesen, die zeigten, dass auch große binäre Programme
anhand von Branch-and-Cut-Algorithmen gelöst werden können. Dabei wurde der
Branch-and-Bound-Algorithmus um Schnittebenenverfahren, um ein Presolving sowie
um primale Heuristiken ergänzt. Das Presolving sorgt für eine bessere Formulierung des
(gemischt) ganzzahligen Programms. Dies bedeutet, dass das MIP durch eine
Umformulierung einfacher zu lösen ist. Die Heuristiken werden vor allem im Bereich
,,Bounding" verwendet (vgl. [JOH83, S.803ff.]). Auf Schnittebenenverfahren wird an
dieser Stelle nicht eingegangen. Hierzu vergleiche man beispielsweise [GOM60] und
[GOM63, S.269ff.].
Die derzeit besten Softwarepakete im Bereich ganzzahlige Optimierung verwenden
Branch-and-Cut-Algorithmen (vgl. [GUR14 (1)]). Zur Lösung der binären Programme in
Kapitel 5 und 6 wird das äußerst leistungsfähige Softwarepaket GUROBI OPTIMIZATION
(vgl. [GUR14 (2)]) verwendet.
25
3 Datenerfassung
Inhalt dieses Kapitels sind die für das gegebene Optimierungsproblem notwendigen
Daten. Hierbei wird zusätzlich auf die Erfassung der Daten eingegangen.
3.1 Die Staffeleinteilung des Bayerischen Fussball-Verbandes
Der Bayerische Fussball-Verband nimmt jedes Jahr rechtzeitig vor Beginn der neuen
Saison die Einteilung der Vereine in die verschiedenen Staffeln der Landesliga vor:
Spielordnung BFV: § 10 Einteilung in Spielklassen: (1) Die Mannschaften der Vereine
werden in die Spielklasse eingeteilt, die ihnen aufgrund der letzten Verbandsrunde
zusteht ([BFV14 (1), S.6]).
Die Einteilung der verschiedenen Staffeln ist in § 10 (2) der Spielordnung des BFV
geregelt:
Die Zusammenfassung der gemeldeten Mannschaften in die einzelnen Spielgruppen
nehmen die Spielleiter nach geographischen, spieltechnischen und verkehrstechnischen
Gegebenheiten vor ([BFV14 (1), S.6]).
Für die Saison 2013/2014 ergaben sich durch die Einteilung des BFV die nachfolgenden
Gruppen (vgl. [BFV14 (2)]). Für die spätere Modellierung wird jeder Mannschaft eine
Nummer zugeordnet. Da es insgesamt 90 Mannschaften sind, eignen sich
sinnvollerweise die Zahlen von 1 bis 90. Die einem Verein zugeordnete Nummer ist
jeweils hinter dem Verein in Klammern aufgeführt. Beispielsweise bedeutet TuS
Frammersbach (1), dass dem TuS Frammersbach die Nummer 1 zugeordnet wird.
Landesliga Nordwest: TuS Frammersbach (1), FC Viktoria Kahl (2), SV Garitz (3), FT
Schweinfurt (4), 1. FC Augsfeld (5), 1. FC Sand (6), TSV Karlburg (7), FC Blau-Weiß
Leinach (8), TSV Lengfeld (9), ASV Rimpar (10), Würzburger FV II (11), DJK Don Bosco
Bamberg (12), SpVgg Stegaurach (13), FVgg Bayern Kitzingen (14), TSV Abtswind (15),
TSV Kleinrinderfeld (16), SpVgg Ansbach (17), TSV Neustadt/Aisch (18)
26
Landesliga Nordost: SV Friesen (19), 1. FC Burgkunstadt (20), TSV Neudrossenfeld
(21), BSC Bayreuth (22), 1. FC Trogen (23), SpVgg Oberkotzau (24), FC Vorwärts
Röslau (25), TSV Kirchenlaibach-Speichersdorf (26), 1. FC Strullendorf (27), SV Pettstadt
(28), SV Buckenhofen (29), ASV Pegnitz (30), ASV Vach (31), FSV Stadeln (32), SG Quelle
Fürth (33), TSV Buch (34), Dergahspor Nürnberg (35), ASV Veitsbronn-Siegelsdorf (36)
Landesliga Mitte: SV Mitterteich (37), SV Etzenricht (38), 1. SC Feucht (39), SC
Ettmannsdorf (40), DJK Vilzing (41), ASV Cham (42), 1. FC Bad Kötzting (43), SpVgg Lam
(44), ASV Burglengenfeld (45), TSV Kareth-Lappersdorf (46), SV Fortuna Regensburg
(47), FC Tegernheim (48), VfB Bach (49), SV Burgweinting (50), TSV Bad Abbach (51),
TV Schierling (52), SpVgg Ruhmannsfelden (53), SpVgg GW Deggendorf (54)
Landesliga Südost: FC Gerolfing (55), FC Ergolding (56), 1. FC Passau (57), TSV
Waldkirchen (58), TuS 1860 Pfarrkirchen (59), SV Hebertsfelden (60), SE Freising (61),
TSV Eching (62), VfB Hallbergmoos (63), TSV Ampfing (64), SV Erlbach (65), TSV
Dachau (66), SC Kirchheim (67), FC F. Markt Schwaben (68), TG-Ataspor München (69),
FC Deisenhofen(70), TuS Holzkirchen (71), SV Kirchanschöring (72)
Landesliga Südwest: Spfr. Dinkelsbühl (73), TSV Nördlingen (74), FC Gundelfingen
(75), SC Bubesheim (76), TSV Aindling (77), TSV Gersthofen (78), TSV 1862 Friedberg
(79), SV Mering (80), TSG Thannhausen (81), FV Illertissen II (82), SC
Oberweikertshofen (83), SC Fürstenfeldbruck (84), TSV Landsberg (85), FC Memmingen
II (86), TSV Ottobeuren (87), SpVgg Kaufbeuren (88), TSV Kottern (89), VfB Durach (90)
Schließlich wird auch noch den einzelnen Staffeln eine Nummer von 1 bis 5 zugeordnet,
denn dies vereinfacht die Modellierung in Kapitel 4, 5 und 6:
Landesliga Nordwest (1), Landesliga Nordost (2), Landesliga Mitte (3), Landesliga
Südost (4), Landesliga Südwest (5)
Bemerkung 3.1: Im Januar 2014 gab der 1.FC Augsfeld bekannt, dass er seine Mannschaft
mit sofortiger Wirkung aus dem Spielbetrieb zurückzieht (vgl. [FUP14]). Dieser
Umstand hat auf das in 1.2 dargestellte Problem keinerlei Auswirkung, da die
Gruppeneinteilung und die Spielplanerstellung vor der Saison stattfinden und nicht
mehr durch Ereignisse während der Saison, wie zum Beispiel einem Rückzug,
beeinflusst werden.
Die nachfolgende Abbildung 8 soll die vom BFV vorgenommene Einteilung geografisch
auf einer Landkarte veranschaulichen.
27
Abbildung 8: Die Staffeleinteilung des BFV (aus [FUP13 (1)])
28
3.2 Rahmentermine und Spielpläne
In diesem Abschnitt wird auf den Rahmenterminkalender der Landesliga Bayern und die
vom BFV erstellten Spielpläne eingegangen. Spieltage, die unter der Woche stattfinden,
sind in der nachfolgenden Übersicht rot markiert.
Spieltag
1
2
3
4
5
6
7
8
9
Datum
20.7/
21.7
24.7/
25.7
27.7/
28.7
3.8/
4.8
10.8/
11.8
14.8/
15.8
17.8/
18.8
24.8/
25.8
31.8/
1.9
Spieltag
10
11
12
13
14
15
16
17
18
Datum
7.9/
8.9
14.9/
15.9
21.9/
22.9
28.9/
29.9
5.10/
6.10
12.10/
13.10
19.10/
20.10
26.10
27.10
2.11/
3.11
Spieltag
19
20
21
22
23
24
25
26
27
Datum
9.11/
10.11
16.11/
17.11
23.11/
24.11
30.11/
1.12
8.3/
9.3
15.3/
16.3
22.3/
23.3
29.3/
30.3
5.4/
6.4
Spieltag
28
29
30
31
32
33
34
Datum
12.4/
13.4
19.4/
20.4
26.4
27.4
3.5/
4.5
10.5/
11.5
17.5/
18.5
24.5/
25.5
Abbildung 9: Rahmentermine der Landesliga Bayern (eigene Darstellung nach [BFV13
(2)])
Man erkennt, dass 32 Spieltage am Wochenende angesetzt sind. Die Spieltage 2 und 6
werden unter der Woche ausgetragen. An diesen beiden Terminen soll keine
Mannschaft länger als 60 Minuten fahren müssen. An allen anderen Spieltagen darf (und
muss teilweise) die Fahrtdauer länger als eine Stunde betragen, um eine zulässige
Einteilung und einen zulässigen Spielplan generieren zu können.
Für die Spielplanerstellung im Amateurbereich wird vom DFB das starre Schema aus
Abbildung 10 vorgeschlagen. Jedem Team der Liga wird dabei eine Zahl zwischen 1 bis
18 zugeordnet. Der Spielplan ist im doppelten DRRT - Format erstellt. Da nur die Teams
zu den Kennziffern zugeteilt werden, ist es nur bedingt möglich Wünsche der Vereine zu
berücksichtigen, denn zunächst muss eine Zuteilung von den Vereinen zu den Nummer
gefunden werden, so dass an den Spieltagen 2 und 6 keine Fahrt länger als eine Stunde
dauert. Wie dies bei einem starren Spielplan funktioniert wird in Kapitel 6 erörtert.
29
Zudem werden dort auch Methoden, welche die Wünsche der Vereine berücksichtigen,
vorgestellt.
Spieltage 1/18
2/19
3/20
4/21
5/22
6/23
7/24
8/25
9/26
Partien
1-17
3-14
5-12
7-10
9-8
11-6
13-4
15-2
18-16
2-13
4-11
6-9
8-7
10-5
12-3
14-18
16-1
17-15
1-15
3-10
5-8
7-6
9-4
11-2
13-17
16-14
18-12
2-9
4-7
6-5
8-3
10-18
12-16
14-1
15-13
17-11
1-13
3-6
5-4
7-2
9-17
11-15
14-12
16-10
18-8
2-5
4-3
6-18
8-16
10-14
12-1
13-11
15-9
17-7
1-11
3-2
5-17
7-15
9-13
12-10
14-8
16-6
18-4
2-18
4-16
6-14
8-12
10-1
11-9
13-7
15-5
17-3
1-9
3-15
5-13
7-11
10-8
12-6
14-4
16-2
18-17
Spieltage 10/27
11/28
12/29
13/30 14/31 15/32 16/33 17/34
Partien
2-14
4-12
6-10
8-1
9-7
11-5
13-3
15-18
17-16
1-7
3-11
5-9
8-6
10-4
12-2
14-17
16-15
18-13
2-10
4-8
6-1
7-5
9-3
11-18
13-16
15-14
17-12
1-5
3-7
6-4
8-2
10-17
12-15
14-13
16-11
18-9
2-6
4-1
5-3
7-18
9-16
11-14
13-12
15-10
17-8
1-3
4-2
6-17
8-15
10-13
12-11
14-9
16-7
18-5
1-2
3-18
5-16
7-14
9-12
11-10
13-8
15-6
17-4
2-17
4-15
6-13
8-11
10-9
12-7
14-5
16-3
18-1
Abbildung 10: Vom DFB vorgeschlagener starrer Spielplan für 18 Mannschaften (eigene
Darstellung nach [DFB11 (2)])
Der vorgeschlagene Spielplan muss wie folgt interpretiert werden: In der Zeile Spieltage
stehen zwei Ziffern, welche durch einen Querstrich / getrennt sind. Die erste Zahl
bezeichnet den Hinrundenspieltag, die zweite den Rückrundenspieltag. In der Spalte
direkt unterhalb der Spieltage sind dann die am jeweiligen Spieltag auszutragenden
Begegnungen aufgeführt, wie sie in der Hinrunde gespielt werden. In der Rückrunde
wird jeweils das Heimrecht getauscht. Dieser Spielplan hat die kleinstmögliche Anzahl
30
an Breaks (48)
3
, die man in einer Liga mit 18 Teams erreichen kann, wenn Heim- und
Auswärtsspiele einer Mannschaft möglichst oft abwechselnd stattfinden sollen.
Bei genauer Betrachtung fällt bei den vom BFV erstellten Spielplänen auf, dass sie im
gespiegelten DRRT Format erstellt sind. Jedoch spielt der 1.FC Augsfeld in der
Landesliga Nordwest an den drei aufeinanderfolgenden Spieltagen 17, 18 und 19
auswärts (vgl. [FUP13 (2)]). Dies sollte bei einer Spielplanerstellung nicht passieren. Es
sollten maximal 2 Heim- oder Auswärtsspiele in Folge angesetzt werden (vgl. [BFV14
(1)]). Sollte der Grund für die drei Auswärtsspiele in Folge eine Platzsperre bei Augsfeld
oder einem der drei Gegner gewesen sein, hätte man anhand der in Abschnitt 6
dargestellten Methoden der diskreten Optimierung einen anderen Spielplan konzipieren
können, der kein Team drei Mal in Folge auswärts spielen lässt. Des Weiteren hat der
Spielplan der Landesliga Nordwest mehr Breaks als nötig wären (vgl. [FUP13 (2)]).
Auch dies vermeiden die später ausgeführten Optimierungsmodelle.
Bemerkung 3.2: Spielausfälle und damit verbundene Nachholspiele sind natürlich im
Vorfeld einer Saison nicht bekannt. Daher werden diese im weiteren Verlauf der
Ausarbeitung nicht berücksichtigt. Es sei aber angemerkt, dass sich als ein möglicher
Nachholtermin das erste Märzwochenende (1.3/2.3) im Jahr 2014 eignen würde.
3.3 Fahrtstrecken und Fahrtzeiten
Zur Ermittlung der Fahrtstrecken und der Fahrzeiten wurde der Microsoft
Routenplanungsdienst bing verwendet (vgl. [BIN14]). Dabei wurde angenommen, dass
die Fahrtstrecke von Spielort A nach Spielort B bzw. von Spielort B nach Spielort A
identisch sind. Diese Symmetrie wurde ebenfalls bei den Fahrtzeiten unterstellt. Der
Grund hierfür ist zum Einen, dass dadurch der Aufwand bei der Datenermittlung
halbiert wurde. Zum Anderen benötigt man für die in Abschnitt 2.2 vorgestellte
graphentheoretische Modellierung des Problems aus 1.2 keinen Digraphen mit Hin- und
Rückkanten zwischen je zwei Knoten. Vielmehr genügt, wie in den Ausführungen in 2.2
beschrieben, eine ungerichtete Kante zwischen je zwei Knoten in einem ungerichteten,
vollständigen Graphen. Darüber hinaus wird durch diese Vereinfachung auch in der
3
siehe hierzu Kapitel 6
Details
- Seiten
- Erscheinungsform
- Originalausgabe
- Jahr
- 2014
- ISBN (eBook)
- 9783956363719
- ISBN (Paperback)
- 9783956367151
- Dateigröße
- 6.9 MB
- Sprache
- Deutsch
- Institution / Hochschule
- Friedrich-Schiller-Gymnasium Marbach – Mathematisches Institut
- Erscheinungsdatum
- 2014 (Oktober)
- Note
- 1,3
- Schlagworte
- Fußball Bayern Sport angewandte Mathematik binäre Mathematik Landesliga
