Die Disponierung von Heim- und Auswärtsspielen. Home Away Pattern in Sports Leagues Scheduling


Bachelorarbeit, 2016
41 Seiten, Note: 2,0
S. Fröhlich (Autor)

Leseprobe

Inhaltsverzeichnis

1 Einleitung

2 Grundlagen
2.1 Spielplanungsprobleme
2.2 Round Robin Turniere
2.2.1 Single Round Robin Turniere
2.2.2 Double Round Robin Turniere
2.3 Home Away Pattern
2.4 Breaks

3 Methoden
3.1 Dekompositionsstrategien
3.1.1 Methode 1: First-Sehedule-Then-Break
3.1.2 Methode 2: First-Break-Then-Sehedule
3.2 Graphentheorie
3.3 Mathematische Modellierung
3.4 Vergleich der Methoden und Auswahl

4 Charakterisierung machbarer Home Away Pattern mit minimaler Pau­senanzahl
4.1 Maehbarkeitsproblem von Spielplänen
4.2 Notwendige Bedingungen zur Konstruktion durchführbarer Spielpläne ,
4.3 Notwendige Bedingungen für eine minimale Pausenanzahl
4.4 Ergebnisse
4.5 Fazit

5 Schlussfolgerung und Ausblick

Literatur- und Quellenverzeichnis

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

Abbildungsverzeichnis

1 Gespiegeltes Double Round Robin Turnier

2 Vollständiger, ungerichteter Graph K

3 Turniergraph für 6 Teams

4 1-Faktorisierungen für K

5 Beispiele anwendungsorientierter Literatur zur Spielplanoptimierung , ,

Tabellenverzeichnis

1 SRRT mit n = 3 Teilnehmern

2 Home Away Pattern für 4 Teams

3 Vergleich balanciertes & unausgeglichenes Home Away Pattern

4 Home Away Pattern für 6 Teams

5 Zuordnung der Teams

6 Mögliche Spielpläne

7 Nicht machbares HAP

8 Verifikation der Bedingung

9 HAP mit minimaler Pausenanzahl

10 Unsortierter, gerechter Spielplan

11 Sortierter, gerechter Spielplan

12 Resultat des Computerexperiments

13 Nicht durchführbares Home Away Pattern für n =14

1 Einleitung

In den letzten Jahren hat Sport wirtschaftlich enorm an Bedeutung zugenommen. Pro­fessionelle Sportligen werden von Millionen Fans weltweit verfolgt und zeigen durch hohe Investitionsbereitschaft in Sportler und TV-Übertragungsrechte die wachsende Attraktivität der Branche, Analog zu der steigenden medialen Präsenz hat auch die Komplexität der Planung und Optimierung von Spielplänen in Sportligen zugenom­men, Eine Vielzahl zu lösender technischer, logistiseher und Fairnessaspekte hat das Forsehungsinteresse in den letzten fünf Jahrzehnten stetig wachsen lassen und so ein neues Forschungsgebiet begründet,[1]

Diese Ausarbeitung, welche insbesondere die Planung von Heim- und Auswärtsspielen und denen sieh daraus ergebenden Spielplänen behandelt, soll Aufschluss darüber geben, wie die zahlreichen, teils konfliktären Anforderungen verschiedener Interessengruppen bei der Planung beachtet werden können. Dafür werden verschiedene Lösungsstrategien, traditionelle Methoden basierend auf Graphen und neuere Ansätze betrachtet, die mit Hilfe mathematischer Modellierungen softwaregestützt implementiert werden können. Überwiegend wird dabei mit Quellen von Bartseh et al, (2006) [2] und Werners und Wülfing (2007) [52] Bezug auf die erste Fußball-Bundesliga genommen, da diese auf das mit Abstand größte öffentliche Interesse in Deutschland stößt.

Eine essentielle Voraussetzung bei der Erstellung eines Bundesliga-Turnierplans ist die abwechselnde Disponierung der Heim- und Auswärtsspiele, in der Fachliteratur auch als „Constraint-Minimum Break-Problem“ bekannt. Ein gutes Home Away Pattern (HAP) soll die Benachteiligung einzelner Teams verhindern, die entstehen würde, wenn eine Mannschaft mehrmals nacheinander auswärts spielen müsste,[2]Dabei ist zu beachten, dass aus einem erzeugten HAP auch ein machbarer Spielplan erstellt werden kann. Deshalb wird anhand von Forschungen von Mivashiro et al, (2003) [37] und Briskorn (2008a) [5] nach Bedingungen gesucht, die Home Away Pattern aufweisen müssen, um als Grundlage für Spielpläne fungieren zu können.

Um die Vorgehens weise zur Erstellung von Spielplänen zu erläutern, werden zunächst in Kapitel 2 die grundlegenden Begriffe erklärt. Anschließend folgt in Kapitel 3 ein Über­blick über die wichtigsten Lösungsstrategien und Ansätze, Nachfolgend wird sieh in Ka­pitel 4 den Eigenschaften von durchführbaren Heim- und Auswärtsmustern gewidmet. Zu guter Letzt folgt in Kapitel 5 eine Zusammenfassung der wichtigsten Erkenntnisse und ein Ausblick auf zukünftige Entwicklungen,

2 Grundlagen

2.1 Spielplanungsprobleme

Spielplanungsprobleme gehören zu den klassischen Zuordnungsproblemen, Mannschaf­ten sollen in einem bestimmten Zeitraum gegeneinander antreten. Zudem muss der Austragungsort bestimmt werden.

Generell können Spielplanungsprobleme in zeitlich restriktive und zeitlich flexible Sach­verhalte unterteilt werden. Während ersteres einen festgelegten Planungshorizont mit einer möglichst minimalen Anzahl an Perioden (Spieltagen) aufweist, verfügen zeitlich flexible Turniere über ein größeres Zeitintervall an Spieltagen als nötig wäre, um alle Partien ausgetragen zu können,[3]Dementsprechend kann es Vorkommen, dass Teams an manchen Spieltagen aussetzen, während bei zeitlich restriktiven Systemen, jede Mann­schaft an jedem Spieltag antritt,[4]Beispiele für zeitlich flexible Turniere sind die NBA und verschiedene Crieketturniere,[5]Oftmals sind zeitlich flexible Pläne auch in unprofes­sionellen Ligen anzutreffen,[6]Im weiteren Verlauf dieser Arbeit soll sieh aber vor allem mit zeitlich restriktiven Planungsproblemen beschäftigt werden, weil diese in den pro­fessionellen Fußballligen eine wichtigere Rolle spielen und aufgrund ihrer Restriktionen schwieriger zu planen sind.

Insbesondere wird dabei auf die deutsche Fußball-Bundesliga Bezug genommen. Die erste deutsche Fußball-Bundesliga besteht aus 18 Teilnehmern, die an 34 Spieltagen gegeneinander antreten,[7]Ein Spieltag ist hierbei nicht zu verwechseln mit einem ge­wöhnlichen Kalendertag, Ein Spieltag in der Bundesliga findet in der Regel am Wo­chenende von Freitag bis Sonntag statt. In wenigen Ausnahmefällen finden einzelne Partien bestimmter Spieltage auch an Wochentagen statt, um Mannschaften, die an in­ternationalen Wettbewerben (z.B, Europa League oder Champions League) teilnehmen, genug Erholungszeit zwischen den Spielen zu ermöglichen. An jedem Spieltag finden 9 Begegnungen statt. Insgesamt ergeben sich somit also 9 · 34 = 306 zu organisierende Fußballspiele,[8]Seit der Saison 2008/09 kommen noch zwei Relegationsspiele am Ende der Saison hinzu,[9]

2.2 Round Robin Turniere

In vielen Sportarten, wie auch in den meisten Fußballligen, werden Partien als soge­nannte Round Robin Turniere (RRT) organisiert,[10]Ein Round Robin Turnier ist eine Abfolge von Spielen, bei der jede der n Mannschaften einmal oder mehrmals gegen jedes andere der verbleibenden n — 1 Teams antritt. Je nachdem wie viele Runden i zustande kommen, wird zwischen Single Round Robin Turnieren (SRRT) und Double Round Robin Turnieren (DRRT) differenziert,[11]

2.2.1 Single Round Robin Turniere

In einem Single Round Robin Turnier (SRRT) trifft jeder Teilnehmer nur ein einziges Mal auf jeden anderen Gegner, d.h, es gibt nur eine Runde und somit gilt i = 1, Bei einer geraden Anzahl von n Teams in einem SRRT ergeben sich also i · (n — 1) = 1-(n—1) = n— 1 Spieltage s mit jeweils | Partien, Insgesamt sind (^) •i = Spiele

zu organisieren,[12]Round Robin Turniere kommen in der Praxis häufig vor. Nahezu alle professionellen europäischen Fußballligen sind als RRT mit gerader Teilnehmeranzahl organisiert,[13]Auch der FIFA Soccer World Cup ist als SRRT organisiert, bevor die Plav- off-Phase beginnt,[14]Für die Verifikation der Formeln soll die Weltmeisterschaft 2014 als Beispiel verwendet werden. An dem Turnier nahmen in der Endrunde 32 Nationen teil. Diese wurden in 8 Gruppen mit jeweils n = 4 Teilnehmern unterteilt, in denen jeder gegen jeden einmal antrat. Somit gab es nur eine Runde i, mit 4 — 1 = 3 Spieltagen, an denen 2 = 2 Partien stattfanden. Summa summarum wurden in den jeweiligen Gruppen (4) · 1 = [4],([4]-[1])’[1] = 6 Partien ausgetragen. Ungerade Teilnehmerzahlen lassen sich aber nicht immer verhindern. Besonders in Amateurligen sind nicht immer genug Teilnehmer vorhanden, um eine Liga mit einer geraden Anzahl zu bilden. Die Problematik ungerader Teilnehmerzahlen liegt darin, dass pro Spieltag immer ein Team pausieren muss,[15]Um ein Round Robin Turnier mit einer nicht geraden Menge zu planen, ist der einfachste Weg, einen Dummy hinzuzunehmen. Damit kann angenommen werden, dass die Anzahl der Teilnehmer gerade ist, ohne die allgemeine Gültigkeit des Modells zu gefährden,[16]In Tabelle 1 wird dies verdeutlicht. Es gibt einen Satz von drei Mannschaften M = A,B, C. Um das SRRT lösen zu können, wird D als Dummy angenommen. Ein Team, welches mit D kombiniert wird, setzt aus,Infolgedessen würde beispielsweise an Spieltag 1 Team C aussetzen. Mit dieser Annahme können ungerade Teilnehmeranzahlen genauso wie gerade geplant werden, ohne die allgemeine Gültigkeit zu gefährden,[17]

2.2.2 Double Round Robin Turniere

Double Round Robin Turniere (DRRT) beschreiben Wettkämpfe, bei denen eine Mann­schaft zweimal gegen alle übrigen Teilnehmer spielt, Typischerweise trifft eine Mann­schaft ž einmal auswärts und einmal zuhause auf Gegner j. Es ergeben sich somit t = 2 Runden bei 2 · (n — 1) Spieltagen. Es werden (/() · 2 Partien ausgetragen,[18]Double Round Robin Turniere sind aufgrund ihrer Fairness eine sehr beliebte Turnierform, Indem je­dem Teilnehmer die Möglichkeit gegeben wird, sieh in der Rüekrunde zu revanchieren, können spielerische Schwächen an einzelnen Tagen ausgeglichen werden. Aus diesem Grund sind die meisten europäischen Fußballligen Double Round Robin Turniere, Die erste und zweite deutsche Fußball-Bundesliga sind gespiegelte DRRT, welche einen Spe­zialfall darstellen,[19]

Gespiegelte Double Round Robin Turniere sind aufgrund ihrer Einfachheit beliebt, da sie mit dem gleichen Aufwand wie Single Round Robin Turniere erstellt werden können. Sie bestehen aus zwei identischen SERT, bei denen in Hin- und Rüekrunde lediglich die Heimreehte vertauscht werden,[20]In Tabelle 1 wird dies am Beispiel der ersten Bun­desliga in der Saison 2015/16 verdeutlicht. Die zuerst genannte Mannschaft hat ein Heimspiel gegen das als zweites angegebene Team, In der Hinrunde hatte somit Bayern München am ersten Spieltag ein Heimspiel gegen den Hamburger Sport-Verein, Auch in der ersten Periode der Rüekrunde, also dem 18, Spieltag, wurde diese Paarung gespielt. Es kam zur Vertauschung des Heimreehtes, sodass die Partie in Hamburg stattfand. Auch alle anderen Paarungen des ersten Spieltages traten am 18, Spieltag wieder mit getauschtem Heimreeht auf,

Abbildung in dieser Leseprobe nicht enthalten

Quelle: Eigene Darstellung in Anlehnung an Bundesliga (2015a) fl 1]

Neben dem gespiegeltem Modus sind die bekanntesten noch Englische und Französische Turnierformen. Das Englische System wird kurioser Weise nicht in England, aber zum Beispiel in Österreich eingesetzt. Dabei ist der erste Spieltag der Rückrunde gleich dem letzten der Hinrunde, sodass Spieltag s aus der Hinrunde n + s in der Rückrunde mit s = 1, 2,..., n — 2 entspricht. Das Französischen System wird in Frankreich, Luxemburg, Russland und Tschechien gespielt. Dabei sind die Spiele des ersten und letzten Spieltages identisch, genau wie die Spielpaarungen in den Perioden n — 1 + s und s + 1 mit s = 1, 2,, n — 2 gleich sind, bis auf das vertauschte Heimrecht.[21]

Für die Planung von Round Robin Turniere gibt es zahlreiche Möglichkeiten, denen sich in Kapitel 3 gewidmet wird.

2.3 Home Away Pattern

Eine essentielle Frage zur Erstellung von Round Robin Turnieren stellt die Bestimmung des Heimrechtes dar. Welche Mannschaft in welcher Periode dieses Recht ausübt, wird mit sogenannten Home Away Pattern dargestellt.

Ein Home-Away-Pattern (HAP) ist die Abfolge von Heim- und Auswärtsspielen für ein bestimmtes Team i. In einer n x (n — 1) Matrix wird dargestellt, in welcher Periode s Team i heim bzw. auswärts spielt,[22]„H“ steht hierbei für „at Home“ und somit für die Heimspiele, während „A“ synonym für „Awav“ steht und die Auswärtsspiele bezeichnet. Daher auch die Bezeichnung Home Away Pattern, Zum Beispiel bedeutet AHAHHA, dass Team i in Runde 1,3,6 und auswärts spielt und in Runde 2,4,5 ein Heimspiel hat,[23]Spielen nun 4 Teams in einem Round Robin Turnier, könnte sieh beispielsweise folgende Matrix ergeben:

Tabelle 2: Home Away Pattern für 4 Teams

Abbildung in dieser Leseprobe nicht enthalten

Quelle: vgl. Miyashiro, R,; Iwasaki, H,; Matsui, T, (2003) [37]

Diese Matrix gibt nun für jedes Team an, an welchem Spieltag s heim bzw, auswärts gespielt wird. Beispielsweise spielt Team 3 in den Runden 1 und 2 zu Hause und in Run­de 3 auswärts. Aus Fairnessgründen ist es gewünscht, dass eine Mannschaft die Hälfte ihrer Spiele zu Hause spielen kann. Wenn n ungerade ist, ist die Anzahl der Heimspie­le gleich derer der Auswärtsspiele, Für eine gerade Anzahl an Teilnehmern gilt, dass es entweder |_n-[1] J Heimspiele und |~n-[1] ] Auswärtsspiele gibt oder anders herum,[24]Es gibt verschiedene Kategorien von Heim- und Auswärtsmustern, Von machbaren oder durchführbaren HAP spricht man, wenn aus vorgegebenen Heim- und Auswärtsmustern ein Spielplan erzeugt werden kann,[25]In weniger professionellen Ligen verfolgt man oft die Zielsetzung, ein ausgeglichenes Home Away Pattern zu erzeugen. Bei einem ausge­glichenem HAP für Team i gilt, dass die Abweichung der Heim- und Auswärtsspiele Δί := hi — ai nicht mehr als 1 ergibt, also \Δί| < 1 mit Vi = 1,..., n gilt,[26]Wenn es sich in einem ausgeglichenem Heim- und Auswärtsmuster um eine ungerade Anzahl an Teil­nehmern n handelt, ergibt sich für Δί immer Null. Bei geradem n gilt Δί G {+1, — 1}, In Tabelle 3 wird dies noch veranschaulicht.

Abbildung in dieser Leseprobe nicht enthalten

Auch der Spielplan der Bundesliga ist ein ausgeglichenes Heim- und Auswärtsmuster.

2.4 Breaks

Breaks, auch Pausen genannt, bezeichnen eine Unterbreehnung der abwechselnden Heim- und Auswärtsspiele. Aus unterschiedlichen Gründen sollen diese soweit wie möglich ver­mieden werden. Beispielsweise konnte naehgewiesen werden, dass sieh Breaks negativ auf die Besucherzahlen auswirken, was Vereine natürlich vermeiden wollen.[27]Jedoch wurde 1981 von de Werra [17] gezeigt, dass es mindestens n — 2 Pausen in einem SERT mit gerader Teilnehmerzahl geben muss, da es höchstens zwei Teams gibt, die ohne eine Pause auskommen, wenn sie folgende Home Away Pattern besitzen: AHAHA- HA und HAHAHAH.[28]DRRT haben mindestens 2n — 4 Breaks und gespiegelte DRRT haben wenigstens 3n — 6 Unterbrechungen.[29]Somit besitzt die Bundesliga als gespiegel­tes Double Round Robin Turnier minimal 3 · 18 — 6 = 48 Breaks. Würde die Bundesliga nur ein einfaches DRRT sein, könnte eine minimale Anzahl von 2 · (18 — 2) = 32 er­reicht werden. Wenn die Teilnehmerzahl n = 4 ist, können auch aufeinanderfolgende Breaks verhindert werden.[30]Gerechte Spielpläne verhindern, dass ein Team mehrere aufeinanderfolgende Breaks hat.[31]Es gibt unterschiedliche Zielsetzungen in Bezug auf die Unterbrechungen. Wenn die Zielsetzung lautet gerechte Spielpläne zu erzeugen, soll verhindert werden, dass ein Team bedeutend mehr Unterbrechungen hat als andere. Ein gerechter Spielplan hat bei einem SRRT mindestens n und bei einem DRRT 2n U nterbreehungen.[32]

Breaks sind unerwünscht, da sie die Fairness von Turnieren beeinflussen können.

Es leuchtet ein, dass schwächere Mannschaften nicht drei Auswärtsspiele hintereinan­der gegen absolute Topmannsehaften haben sollen. Ein schlechtes Heim- und Auswärts­muster kann die Ergebnisse durch Carry Over Effekte verzerren. Ein Carrv-Over-Effekt entsteht, wenn Team A an Spieltag 1 gegen Team В spielt und in der darauffolgenden Runde gegen Team C spielt. War В nun ein schwerer Gegner, könnte daraus ein Vor­teil für C entstehen,[33]Je nach Zielsetzung und Liga wird die Qualität von Heim- und Auswärtsmustern unterschiedlich bewertet. Es lässt sieh somit pauschal keine allgemein gültige Definition für ein gutes Home Away Pattern geben. Dennoch soll das Home Away Pattern möglichst keinen Einfluss auf den Turnierverlauf nehmen. Deswegen haben vie­le Sportligen, wie unter anderem die Bundesliga, das Ziel, das „Constraint-Minimum Break Problem“ zu lösen, womit sieh in Kapitel 3 näher beschäftigt wird.

3 Methoden

Zur Lösung von Spielplanungsproblemen existieren unterschiedliche Ansätze: Dekom­positionsstrategien, ganzzahlige Programmierung, Spaltengenerierung, Benders Schnit­te, Constraint-Programmierung, heuristische Suche, Metaheuristiken und dazugehörige Hybride,[34]

In diesem Kapitel soll ein Teil der verschiedenen Lösungsansätze am Beispiel der Bun­desliga dargestellt werden. Es soll ein Überblick über die wichtigsten Anforderungen, Interessengruppen und Restriktionen der Bundesliga vermittelt werden und Aufschluss darüber gegeben werden, warum die Erstellung eines Home Away Pattern eine entschei­dende Rolle spielt,

3.1 Dekompositionsstrategien

Zur Lösung von Spielplanungsproblemen wird in der betrachteten Literatur häufig auf sogenannte Dekomposisationsstrategien zurüekgegriffen, Dekomposisationsstrate- gien zielen darauf ab, das aufwendige Hauptproblem der Spielplanerstellung in zwei einfacher zu lösende Teilprobleme zu zerlegen, die durch Heuristiken oder exakte Al­gorithmen gelöst werden können. Aufgrund ihrer Effizienz werden Dekomposisationss­trategien in verschiedensten Sportarten genutzt,[35]Je nachdem, ob erst das Home Away Pattern oder die Gegnerzuteilung vorgenommen wird, lassen sieh zwei Methoden un­terscheiden,

3.1.1 Methode 1: First-Schedule-Then-Break

Michael A, Trick beschreibt in seinem Paper “A Sehedule-then-Break Approach to Sports Timetabling“ [49] eine Methode, um Round Robin Turniere mit Heim- und Auswärtsspielen festzulegen, bei der zuerst die jeweils gegeneinander spielenden Mann­schaften in einem sogenannten Gegnerplan festgelegt werden und in einer zweiten Phase der Austragungsort bestimmt wird. Um in der ersten Phase den Gegnerplan zu erstel­len, benutzt er Constraintprogrammierung, Das Home Away Pattern wird dann mög­lichst gut mit ganzzahliger linearer Optimierung an den Gegnerplan angepasst. Dieser Ablauf ist vor allem dann sinnvoll, wenn es hauptsächlich Anforderungen an den Spiel­plan gibt, die nicht das Home Away Pattern betreffen. Beispielsweise ist es in einigen Sportligen üblich, bereits vor der eigentlichen Erstellung des Spielplans, Begegnungen für bestimmte Perioden festzulegen. Das kann zum Beispiel Vorkommen, wenn Fern­sehsender nur bestimmte Topspiele an gewissen Spieltagen übertragen, wie es in de deutschen Basketball-Bundesliga der Fall ist,[36] Damit wird die Festlegung der Spiel­paarungen zum kritischsten Element der Spielplanerstellung, Ein weiterer Grund diese Methode vorzuziehen ist, dass Carry-Over-Effekte bei der Planung des Gegnerplans vermieden werden können, Russell [45] hat 1980 gezeigt, wenn die Anzahl der Teams n eine Potenz von 2 ist, Carry-Over-Effekte gleichmäßig auf die Teams verteilt werden können. Zudem hat er eine Heuristik entwickelt, mit der die Varianz von Carry-Over- Effekten minimiert werden kann, wenn die Anzahl der Mannschaften keine Potenz von zwei ist, also n = 2“ mit a = 1,..., œ gilt. Nachdem die Spielpaarungen zugeordnet wur­den, muss ein Home Away Pattern erstellt werden. Dabei soll die Anzahl der Breaks minimiert werden, da dies aber nicht das Hauptziel ist, erfolgt dieser Schritt erst re­lativ spät, Post und Woeginger [40] konnten mit einem polynomialen Zeitalgorithmus zeigen, dass es für jeden Gegnerplan mit n Mannschaften ein Home Away Pattern mit maximal n(n4-[2]) Pausen gibt ,[37] Es gibt aber auch Gegnerpläne, die nicht mit weniger als n(n6-[1]) Unterbreehnungen gespielt werden können,[38] Im Fall der Fußball-Bundesliga muss jedoch eine anderere Dekomposisationsstrategie verwendet werden, da die über­wiegenden Anforderungen, das Heim- und Auswärtsmuster betreffen, und das Hauptziel in der Miminierung der Anzahl der Breaks besteht,

3.1.2 Methode 2: First-Break-Then-Schedule

Die „First-Break-Then-Schedule“-Methode kann als Gegenteil des „First-Schedule-Then- Break“-Ansatzes gesehen werden. Ist das Hauptziel bei der Spielplanerstelleung die Mi­nimierung der Breaks und betreffen Anforderungen an den Spielplan überwiegend das Heim- und Auswärtsmuster, macht es Sinn, erst dieses zu bestimmen und anschließend die Gegner zuzuteilen. Diese Dekomposisationsstrategie kommt also überwiegend bei „Constraint-Minimum-Break-Problemen“ vor und kann in vier Phasen eingeteilt wer­den:[39]

1, Home Away Pattern generieren
2, Ein HAP auswählen und Platzhalter zuordnen
3, Mit ausgewählten HAP einen Spielplan erstellen
4, Platzhalter tatsächlichen Mannschaften zuordnen

Die Schritte können beliebig variiert und zusammengefasst werden. Grundsätzlich gilt bei Dekomposistionsstrategien jedoch, je kritischer und wichtiger ein Aspekt ist, desto früher wird dieser gelöst,[40]Das Hauptproblem dieses Ansatzes ergibt sieh dadurch, dass nicht aus jedem Home Away Pattern ein machbarer Spielplan erzeugt werden kann. Beispielsweise könnten zwei Mannschaften niemals gegeneinander antreten, wenn sie identische Heim- und Auswärtsmuster aufweisen,[41]Auf weitere Ausführungen über die Problematik der Erstellung machbarer HAP und deren Eigenschaft soll an dieser Stelle auf Kapitel 4 verwiesen werden.

In der Literatur wird der „First-Break-Then-Schedule“-Ansatz oft beschrieben [16] [20] [29] [35] [38] [42] [46] [47] [48] und auch für die Erstellung eines Bundesliga Spielplans ge­nutzt [52], Dabei treten viele Variationen im Hinblick auf die Methode auf, Nemhauser und Trick (1998) [38] haben zum Beispiel ein College Baseketball Turnier geplant. Zur Lösung des HAP haben sie mit Hilfe von ganzzahliger Programmierung gute Ergebnisse erzielt. Sie konnten zeigen, dass mit einer Kombination aus Enumeration und ganz­zahliger Programmierung bessere und vorallem weniger zeitaufwendige Lösungen für machbare HAP erzeugt werden können, als mit kombinatorischen Design Techniken,[42]Henz (2001) [29] hat dieses Szenario aufgegriffen und mit Finite-Domain-Constraint- Programmierung noch bessere Ergebnisse hinsichtlich der Reehenzeit erzielen können. Generell sind Dekomposisationsstrategien nicht als feste Vorgehensweise zu sehen, son­dern eher als eine Lösungsstrategie, bei der die Phasen flexibel an das Problem angepasst werden,

3.2 Graphentheorie

Es gibt viele verschiedene Ansätze um Spielpläne zu generieren. Traditionelle Metho­den basieren auf kombinatorischem Designs mithilfe von Graphen,[43]Bereits Anfang der 80er Jahre veröffentlichte Dominique de Werra als einer der ersten mehrere Forschungs­ergebnisse dazu,[44]Heutzutage bilden Graphen die Grundlage für viele Algorithmen, Um diese besser zu verstehen, soll hier am Beispiel der Bundesliga das Prinzip dahinter erläutert werden. Tatsächlich wurde der kombinatorische Ansatz von Sehreuder [48] für die Erstellung der professionellen dänischen Fußball Liga angewendet. Um aus einem Graphen einen Spielplan zu erzeugen, sind zwei Schritte im Rahmen einer Dekomposi- sationsstrategie notwendig. Zuerst wird das Home Away Pattern erstellt, welchem dann in einem zweiten Schritt die Vereine zugeordnet werden,[45]Bei Erstellung des Heim- und Auswärtsmusters kann mit Faktorisierungen oder Färbungen gearbeitet werden.[46] Faktorisierungen F1,..., Fn-1 teilen nicht benachbarte Kanten des Graphens in verschie­dene Teilmengen auf.[47] Zur Erstellung eines Bundesligaspielplans betrachtet man einen vollständigen Graphen Kn mit n Knoten. Bei einem vollständigen, ungerichteten Gra­phen ist jeder Knoten mit jedem anderen durch eine Kante verbunden. Dies ist eine wichtige Voraussetzung, da jede Mannschaft einmal gegen jede andere antreten soll.[48] Jeder Knoten repräsentiert eine Mannschaft, sodass im Fall der Bundesliga ein vollstän­diger Graph Ki8 mit n =18 Teams betrachtet werden muss. Eine Kante zwischen den Knoten ¿und j mit i, j G {1,.., 18} stellt ein Spiel zwischen den Gegnern ¿und j dar. Um nun ein Home Away Pattern mit einem Graphen anzufertigen, braucht man n — 1 Farben. Jede Farbe steht für einen Spieltag. Damit ein Plan zulässig ist, müssen alle in einen Knoten führenden Kanten unterschiedliche Farben haben. Betrachtet man nun in Abbildung 2 einen vollständigen Graphen für 18 Mannschaften, werden die Nach­teile dieser Methode deutlich. Ein Graph mit sovielen Knoten ist sehr unübersichtlich, weshalb der Algorithmus anhand eines Graphen mit nur 6 Knoten erklärt werden soll.

Damit ein Home Away Pattern erstellt werden kann, ist zudem ein vollständiger ge­richteter Graph, welcher auch als Turniergraph bezeichnet wird, notwendig,[49]Ein Pfeil (i,j) würde bedeuten, dass Team j i hat,[50]Dies kann man auch mit orientierten Faktorisierungen Ё^,..., Ï-; angeben, wobei jede einen der fünf Spielta­ge darstellt. Zusätzlich wird jeder Spieltag durch eine Farbe repräsentiert, Abbildung 3 zeigt einen Turniergraphen, der einen zulässigen Spielplan darstellt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3: Turniergraph für 6 Teams

f1 = (4, 3); (5, 2);(1,6) = (6, 4); (3, 5); (2,1) = (4, 2); (1, 5); (6, 3) = (5, 4); (2, 6); (3,1) f5 = (4,1); (6, 5); (2, 3)

Quelle: Eigene Darstellung in Anlehnung an 1511 S.271

Nacheinander wurden alle Kanten eingefärbt bis schließlich ein vorläufiger Spielplan entstanden ist. Das Prinzip dahinter kann verdeutlicht werden, wenn man Knoten 6 und alle ihm indizenten Pfeile aus dem Graphen entfernt. Das sich daraus ergebene Fünfeck sieht folgendermaßen aus:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4: 1-Faktorisierungen für K5

Quelle: Eigene Darstellung in Anlehnung an |51| S.278 ff, & |21| S.467

[...]


[1]Kendall, G. et al., S. (2010), S.40 f. [31]

[2]Werners, B.; Wülfing, T. (2007), S.4 [521]

[3] Briskorn, D.; Drexl, A.; Spieksma, F. C. R. (2010), S.366 [7] i.V.m. Drexl, A.; Knust, S. (2007), S.465 [21]

[4] Nemhauser, G. L; Trick, Μ. A. (1998), S.l [381 i-V.m. Kendall, G. et al. (2010), S.5 [311

[5] siehe [I] [3] [54] [55]

[6] Knust, S.; von Thaden, M. (2006), S.355 [34]

[7] Werners, B.; Wülfing, T. (2007), S.2Û9 [52]

[8] Ortlieb, C. R et al. (2013), S.19 [39)

[9] Frankfurter Allgemeine (2007) [26]

[10] Goossens, D. R.; Spieksma, F. C. R. (2012), S.643 [28]

[11] Horbach, A.; Bartsch, T. & Briskorn, D. (2012), S.117 [30]

[12] Kendall, G. et al. (2010), S.5 [31]

[13] Goossens, D. R.; Spieksma, F. C. R. (2012), S.643 [28]

[14] Briskorn, D.; Drexl, A.(2009), S.84 [6]

[15] Kendall, G. et al. (2010), S.5 [31]

[16] Briskorn, D.; Drexl, A.(2009), S.84 [6] i.V.m. Briskorn, D.; Drexl, A.; Spieksma, F. C. R. (2010), S.366 [71 & Della Croce, F. D.; Tadei, R. & Asioli, R S.(1992), S.351 [15]

[17] Kidd, M.P. (2010), S.126 f. [33]

[18] Kendall, G. et al. (2010), S.5 [31]

[19] Werners, В.; Wülfing, T. (2007), S.210 [52]

[20] Briskorn, D.; Drexl, A.(2009), S.84-85 [6] i.V.m. Horbach, A.; Bartsch, T. & Briskorn, D. (2012), S. 117 [30]

[21] Goossens, D. R.; Spieksma, F. C. R. (2012), S.646 [28]

[22] Kendall, G.; Knust, S.; Ribeiro, C.C. (2010), S.6 [31]

[23] Burke, E. K.; Rudová, H. (2007), S.137 [14]

[24] Knust, S.; von Thaden, M. (2006), S.356 [34]

[25] Rasmussen, R. V.; Trick, M. A. (2006), S.3 [41]

[26] Knust, S.; von Thaden, M. (2006), S.356 [34)

[27] Forrest, D.; Simmons, R. (2006) [25] i.V.m. Goossens, D. R.; Spieksma, F. C. R. (2012) S.646 [28]

[28] Goossens, D. R.; Spieksma, F. C. R. (2012), S.646 [28] i.V.m. de Werra, D. (1981) [17]

[29] de Werra, D. (1981) [17]

[30] de Werra, D. (1981), [17] i.V.m. Goossens, D. R.; Spieksma, F. C. R. (2012), S. 646 [28] & Werners, B.; Wülfing, T. (2007), S.211 [52]

[31] Goossens, D. R.; Spieksma, F. C. R. (2012), S. 646 [28] i.V.m. Miyashiro, R.; Iwasaki, H.; Matsui, T. (2003), S.85 [37]

[32] de Werra, D. (1980) [16]

[33] Trick, M. A. (2001) S.4 [491

[34]Kendall, G. et al. (2010), S.41 [311

[35]Knust, S.; Lücking, D. (2009), S. 2939 [351

[36] Westphal, S. (2014), S.499 [531

[37] Brouwer, A. E.; Post, G. F.; Woeginger, G. J. (2008) S.1066 [8] i.V.m. Post, G.; Woeginger, G. J. (2006): S. 165 [40]

[38] Post, G.; Woeginger, G. J. (2006) S. 165 [40)

[39] Werners, B.; Wülfing, T. (2007), S.211 [52) i.V.m. Rasmussen, R. V.; Trick, M. A. (2006), S.9 [41)

[40] Trick, Μ. A. (2001), S.3 [49]

[41] Briskorn, D. (2008), S.22 [4]

[42] Nemhauser, G. L; Trick, Μ. A. (1998) S.8 [38]

[43] Kendall, G. et al. (2010), S.6 [31]

[44] Drexl, A.; Knust, S. (2007), S.466 [21) i.V.m. [16][17][18][19][20]

[45] Schreuder, J. A. M. (1992), S. 306 [48] i.V.m. van Ween. A.; Sehreuder, J. A. M. (1998) [50]

[46]Bartsch, T.; Drexl, A.; Kröger, S. (2006) S.1922 |2j

[47]de Werra, D. (1981) S.381 [17J i.V.m. Drexl, A.; Knust, S. (2007) S.466 [21J

[48]Vöcking, B. et al. (2008) S.276, [51]

[49]Büsing, C. (2010), S.134 [91]

[50]de Werra, D. (1981) S.381 [171

Ende der Leseprobe aus 41 Seiten

Details

Titel
Die Disponierung von Heim- und Auswärtsspielen. Home Away Pattern in Sports Leagues Scheduling
Hochschule
Universität Hamburg
Note
2,0
Autor
Jahr
2016
Seiten
41
Katalognummer
V340796
ISBN (eBook)
9783668307377
ISBN (Buch)
9783668307384
Dateigröße
1840 KB
Sprache
Deutsch
Schlagworte
Home Away Pattern, Bundesliga, Fußball, Heim-und Auswärtsmuster, Spielplanung, mathematische Modellierung
Arbeit zitieren
S. Fröhlich (Autor), 2016, Die Disponierung von Heim- und Auswärtsspielen. Home Away Pattern in Sports Leagues Scheduling, München, GRIN Verlag, https://www.grin.com/document/340796

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Die Disponierung von Heim- und Auswärtsspielen. Home Away Pattern in Sports Leagues Scheduling


Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden