Uni-Logo

Master-Projektgruppe
Optimierte Sportliga-Terminplanung
(OptimiST)


Inhalt:

Im Rahmen dieser Projektgruppe soll ein System zur optimierten Planung von Sportligen entstehen. Dabei werden verschiedene Teilprobleme aus dem Bereich der Sportligaplanung betrachtet und Algorithmen hierfür implementiert, getestet sowie visualisiert.

Das Grundproblem für die Planung einer Sportliga lässt sich wie folgt formulieren: Gegeben ist eine Liga bestehend aus einer Menge an Mannschaften, wobei jede Mannschaft eine festgelegte Anzahl an Spielen gegen jede andere spielen soll. Um alle Spiele auszutragen, stehen Runden (Spieltage) zur Verfügung, wobei in jeder Runde jede Mannschaft maximal ein Spiel hat. Außerdem muss für jedes Spiel das Heimrecht festgelegt werden, d.h. bei welchem Gegner das Spiel stattfindet. Ein Spielplan für 8 Mannschaften und 7 Runden sieht beispielsweise so aus:

Plan

Bei der Spielplanung gibt es im Allgemeinen eine sehr große Anzahl von Nebenbedingungen die berücksichtigt werden sollen (z.B. möglichst gleichmäßige Verteilung von Heim- und Auswärtsspielen, Unverfügbarkeiten von Mannschaften bzw. Spielstätten zu bestimmten Terminen, möglichst gleichmäßige Verteilung von Spielpaarungen über den gesamten Saisonverlauf, Fairnessaspekte, usw.). Gesucht ist ein gültiger Spielplan, der möglichst viele Nebenbedingungen einhält.

Die zur Lösung dieser Probleme angewandten Techniken sind z.B. graphentheoretische Überlegungen, Lineare Programmierung, Constraint Programming, Lokale Suche, Genetische Algorithmen.

Plan

Konkrete Anwendung:

Wir wollen im Sommersemester damit starten, ein System zur automatischen Planung von Tischtennisligen zu entwickeln. Dabei geben die Mannschaften zunächst über eine Webapplikation ihre Daten ein (mögliche Termine für Heimspiele, unmögliche Auswärtsspieltermine, maximale Anzahl an Heimspielen des Vereins an einem Tag, etc.). Danach wird basierend auf diesen Daten und einstellbarer Kriterien ein optimierter Spielplan berechnet und angezeigt.

Teilaufgaben:

Im darauf folgenden Wintersemester sollen je nach Interessen der Teilnehmer verschiedene Erweiterungen bzw. andere Sportligaplanungsprobleme im Vordergrund stehen.


Literatur:


Materialien:


Organisatorisches:

Die Veranstaltung findet im Rahmen des Master-Studiengangs "Informatik" statt, der die Teilnahme an einer Projektgruppe über 2 Semester für insgesamt 24 ECTS-Leistungspunkte vorsieht. Vorkenntnisse zur Optimierung sind von Vorteil, aber nicht unbedingt notwendig, da sich die Teilnehmer gemeinsam in die Optimierungsmethoden einarbeiten. Zur Erteilung des Scheines ist eine regelmäßige Teilnahme an den Präsenzterminen notwendig, sowie die Bearbeitung der Projektaufgaben in Kleingruppen nach freier Zeiteinteilung. Weiterhin finden regelmäßige Kurzpräsentationen des Entwicklungsfortschritts statt. Die entwickelten Methoden werden mit praxisrelevanten Daten getestet und evaluiert. Die Ergebnisse der Projektgruppe werden dokumentiert und in einer öffentlichen Abschlusspräsentation vorgestellt.