English

The scheduling of vehicles is a central task in the planning process of public transport. By generating efficient schedules, transport companies are able to increase their productivity. In general the goal of scheduling vehicles is to assign a feasible route to each vehicle so that every trip can be serviced and the overall costs are minimized. Moreover there are different problem extensions like the consideration of multiple depots, different vehicle types or time windows for trips. There are a number of research publications which consider the optimization of vehicle scheduling problems with practical extensions. However, they only consider the vehicle scheduling problem in the context of operational planning. In this thesis new possible applications of optimization methods for vehicle scheduling as well as their individual requirements are presented. For solving these applications, an optimization framework is developed, which contains a number of new, specialized solution methods. In addition, further real-life challenges for vehicle scheduling optimization like the avoidance of a black-box-behavior or the applicability for larger planning problems in the future are considered. The thesis gives an analysis for the behavior of real and artificial problem instances and presents characteristics of different modeling approaches. The applicability of the optimization framework is validated through extensive numerical tests.

Deutsch

Die Planung des Fahrzeugeinsatzes stellt eine wesentliche Aufgabe im Planungsprozess des öffentlichen Personennahverkehrs dar, um durch eine effiziente Nutzung der Fahrzeuge die Produktivität eines Verkehrsunternehmens zu steigern. Ziel der Fahrzeugeinsatzplanung ist es, die verfügbaren Fahrzeuge zur Bedienung eines festgelegten Fahrplans mit möglichst geringen Kosten einzuteilen. Es existieren unterschiedliche praxisrelevante Problemerweiterungen wie die Berücksichtigung mehrerer Fahrzeugdepots, unterschiedlicher Fahrzeugtypen oder Zeitfenster für die Bedienung von Fahrten. Die Optimierung des Fahrzeugeinsatzes wurde in der Vergangenheit bereits in vielen Veröffentlichungen diskutiert und Lösungsansätze für die bekannten Problemstellungen gegeben. Bisherige Forschungen zielen auf die Optimierung der operativen Planung ab. Die vorliegende Arbeit identifiziert neue Einsatzmöglichkeiten von Optimierungsmethoden für die Fahrzeugeinsatzplanung und beschreibt ihre individuellen Anforderungen. Zur Lösung der Problemstellungen im Kontext unterschiedlicher Einsatzgebiete ist ein Methodenframework mit einer Vielzahl von neuen, speziell ausgerichteten Optimierungsmethoden entwickelt worden. Die Methoden berücksichtigen darüber hinaus aktuelle Herausforderungen an Umlaufoptimierungsmethoden wie die Vermeidung eines Black-Box-Verhaltens gegenüber einem Planer sowie die nachhaltige Einsetzbarkeit für zukünftig zu erwartende größere Problemstellungen. Erstmalig werden die Eigenschaften von realen und künstlichen Probleminstanzen analysiert und Kennzahlen für Eignung unterschiedlicher Modellierungen gegeben. Die Eignung des Frameworks wird anhand umfangreicher numerischer Tests validiert.