[Back]


Diploma and Master Theses (authored and supervised):

B. M. Kim:
"Iterated Local Search for the Traveling Tournament Problem";
Supervisor: N. Musliu; Institut für Informationssysteme, 2012; final examination: 2012-11-19.



English abstract:
The problem of finding optimal schedules for professional sports leagues has attracted interests of many researchers in recent years. On the one hand, sport scheduling is an economically important class of combinatorial optimization applications, since sport leagues generate considerable amount of revenue for major radio and television networks, whose profits also depend on the quality of schedules. On the other hand, sport scheduling poses a very challenging optimization problem which involves issues of both feasibility and optimality.
The Traveling Tournament Problem (TTP) is a challenging sport scheduling problem abstracting the features of major league baseball (MLB) in the United States. The objective of the TTP is to find a double-round-robin tournament schedule minimizing the total distance traveled by the teams and satisfying at the same time the TTP-specific constraints.
To solve TTP, we propose a metaheuristic approach based on Iterated Local Search (ILS) framework. Iterated Local Search is a simple but yet powerful metaheuristic which has shown very good results for different classes of optimization problems. First, we develop a basic ILS algorithm for the TTP to assess the applicability of the ILS-principle to the TTP. Based on the insights gained by analyzing the basic variant, we further optimize and extend the basic version to improve the performance. One particularly important optimization is the definition of efficient algorithm for incremental evaluation which speeds up the computation considerably.
We conduct extensive computational experiments on selected TTP benchmark-sets and compare our results with those obtained by current state-of-the-art approaches in literature. For the NL-x benchmark-set, our ILS algorithm is able to solve the smaller instances [NL4,NL6,NL8] to optimality in only few seconds. For larger instances [NL10,NL12,NL14], our algorithm exhibits better average performance than most of other compared approaches being only second to the current best-performing Simulated Annealing approach. In general, our results show that our ILS algorithm is competitive with current state-of-the-art approaches in the literature.

German abstract:
Das Problem des Findens von optimalen Turnierplänen für professionelle Sportligen hat in letzter Zeit Aufmerksamkeit vieler Wissenschaftler erregt. Die Planung von optimalen Sportplänen ist eine wirtschaftlich wichtige Antwendung kombinatorischer Optimierung, weil die Sportligen heutzutage wichtige Einnahmequellen für große Fernsehsender und Turnierveranstalter darstellen, wobei der erzielte Profit auch von der Qualität der Spielpläne abhängt.
Das Traveling Tournament Problem (TTP) ist ein schwieriges Sportplanungsproblem, welches die besonderen Merkmale von amerikanischen Major League Baseball (MLB) abstrahiert. Das Ziel des TTP ist die Minimierung der gesamten Reisedistanz der teilnehmenden Teams, während TTP spezifische Einschränkungen erfüllt bleiben müssen.
Wir stellen ein metaheuristisches Verfahren basierend auf Iterated Local Search Framework zur Lösung des TTP vor. Iterated Local Search ist ein simples aber gleichzeitig mächtiges Heuristikverfahren, das für viele verschiedene Optimierungsprobleme gute Ergebnisse gezeigt hat. Wir entwickeln zuerst eine Basisvariante des ILS, mit der wir die Anwendbarkeit der ILS- Prinzipien fuer das TTP beurteilen. Basierend auf den Erkenntnissen aus der Analyse der ersten Variante verfeinern und optimieren wir den Basis-ILS weiter. Eine der wichtigsten Optimierungen ist dabei die Definition einer inkrementellen Evaluierungsfunktion, was die Geschwindkeit des Algorithmus deutlich steigert.
Wir führen ausführliche Experimente mit unserem Algorithmus durch und vergleichen die Resultate mit den aus der Literatur. Die Ergebnisse mit der NL-x Benchmark-set zeigen, dass unser Algorithmus die kleineren Instanzen [NL4,NL6,NL8] in wenigen Sekunden optimal lösen kann. Für größere Instanzen [NL10,NL12,NL14] zeigt unser Verfahren bessere und stabilere Durchschnittsleistung als die meisten Verfahren aus der Literatur, wobei nur das aktuell beste state-of-the-art Verfahren basierend auf Simulated Annealing klar bessere Ergebnisse als unsere Methode zeigt. Insgesamt zeigen die Ergebnisse, dass unser ILS-Algorithmus mit den besten state-of-the-art Algorithmen aus der Literatur für das TTP gut konkurrieren kann.

Created from the Publication Database of the Vienna University of Technology.