Diese Dissertation behandelt mathematische Optimierungsmodelle und -methoden zur Ressourceneinsatzplanung mit gleichzeitiger Berücksichtigung von Kosteneffizienz und Robustheit beim Einsatz der Ressourcen. Im Anwendungsfeld des ÖPNV werden Lösungsansätze zur Umlaufplanung für Fahrzeuge und zur Dienstplanung für Fahrer entwickelt, die eine Beschränkung aktueller Ansätze aufheben: Bisher wird in Optimierungsansätzen zur Ressourceneinsatzplanung hauptsächlich eine reine Minimierung der geplanten Kosten des Ressourceneinsatzes verfolgt. Dies führt üblicherweise zu straffen Plänen, die bei ihrer Ausführung eher anfällig für Verspätungen sind. Aufgrund fehlender Pufferzeiten und der Abhängigkeiten zwischen Umläufen und Diensten können dann - ohne Eingriff - selbst kleine Verspätungen zu kaskadierenden Verspätungseffekten führen. Um die Funktionsfähigkeit der Pläne trotz äußerer Einflüsse zu gewährleisten, können in der Planung proaktiv mögliche Verspätungen antizipiert und ihre Auswirkungen berücksichtigt werden. Eine solche robuste Planung gegen Störungen und Verspätungen ist jedoch für den gemeinsamen Einsatz von Fahrzeugen und Fahrern kaum untersucht. In dieser Arbeit werden die gegenseitigen Abhängigkeiten zwischen Umlauf- und Dienstplänen berücksichtigt und ein Baukasten mit neuen Lösungsansätzen vorgeschlagen. Diese beziehen die potenzielle Propagation möglicher Verspätungen in die Planung ein, bei gleichzeitiger Verfolgung von Kosteneffizienz. Dabei berücksichtigen die Ansätze in verschiedenem Maße die Verknüpfung der Planungsebenen Fahrplan-, Umlauf- und Dienstplanung. Es wird untersucht, in welchem Ausmaß die verschiedenen Planungsmethoden zu Plänen mit unterschiedlicher Qualität bezüglich der Zielsetzungen Robustheit und Kosteneffizienz führen. In den Lösungsansätzen werden netzwerkfluss- und pfadbasierte Modellformulierungen basierend auf Time-Space-Netzwerken kombiniert. Zum Lösen wird Column Generation in Kombination mit Lagrange- Relaxation genutzt. Dabei werden die Pricing-Probleme zur Bestimmung robuster und effizienter Umläufe und Dienste als ressourcenbeschränkte Kürzeste-Wege- Probleme formuliert. Die berechneten Pläne werden zusätzlich durch stochastische Simulation evaluiert. Diese bildet eine reine Bewertung der erwarteten Verspätungspropagation als auch eine Bewertung bei Einbeziehen dispositiver Maßnahmen während der Planausführung ab. Die Ergebnisse unterstreichen die Relevanz der kombinierten Betrachtung von Umlauf- und Dienstplanung und des Einbeziehens potenzieller Verspätungspropagation in die Planung. Mit den vorgeschlagenen Ansätzen kann die erwartete Verspätungspropagation im Vergleich zu rein kostenminimierender Planung drastisch reduziert werden ohne zusätzliche Kosten. Dabei führt das Abbilden von Propagationseffekten innerhalb der Lösungsverfahren zu einer adäquaten Verteilung von Pufferzeiten in den Plänen inklusive passender, robuster Verknüpfung von Fahrten und Aufgaben unterschiedlicher Ressourcen. Zusätzlich werden durch die Analyse der Planstrukturen der verschiedenartig erstellten Ressourceneinsatzpläne Prinzipien erfolgreich robust effizienter Pläne identifiziert.
This thesis deals with mathematical optimization models and methods for resource scheduling with simultaneous consideration of cost-efficiency and robustness during operations. In the field of public transit, solution approaches are developed for vehicle scheduling and crew scheduling that overcome a particular limit of current approaches: Current optimization approaches mainly aim at pure minimization of planned costs for resource usage. This usually results in tight schedules which are more susceptible to delays during operations. Due to the lack of buffer times and due to dependencies between scheduled vehicles and drivers – without intervention – even small delays may cause cascading additional delays. In order to ensure the functionality of the computed schedules despite external factors, possible delays and their effects should already be considered in the planning phase. However, to date there is only little research assessing robust scheduling against disruptions and delays affecting usage of both vehicles and crews. In this work, the mutual dependencies between vehicle and crew schedules are considered and a modular system with new solution approaches is proposed. The approaches consider the propagation of possible delays during scheduling while simultaneously aiming at cost-efficient resource schedules. In addition, the planning stages vehicle scheduling and crew scheduling and aspects of timetabling are integrated to different extends. It is examined to what extend the various scheduling approaches result in schedules with different qualities in terms of the objectives robustness and cost-efficiency. In the proposed solution approaches network flow based model formulations are combined with path based formulations based on Time-Space-Networks. As solution method column generation is used in combination with Lagrangean relaxation. The pricing problems for the generation of robust and efficient vehicle blocks and duties are modelled as resource constrained shortest path problems. The computed schedules are evaluated with the help of a stochastic simulation. This simulation incorporates a pure evaluation of the expected propagated delay as well as an evaluation when dispatching strategies are considered during operation of the schedules. The results stress the relevance of the combined consideration of vehicle and crew scheduling and the consideration of possible delay propagation when scheduling resources. Compared to pure cost- efficient scheduling, the proposed approaches are able to decrease the expected delay propagation drastically without additional costs. Modelling delay propagation effects within the solution methods results in an adequate distribution of buffer times in the schedules including the construction of suitable, robust links between trips and tasks of different resources. Further, based on the analysis of the variously computed resource schedules and their structures, principles of successful robust efficient schedules are identified.
