English

Vehicle and crew scheduling are two major planning problems arising in public bus transport companies. Briefly stated, these problems aim at assigning vehicle itineraries to scheduled trips and crews itineraries to tasks resulting from the vehicle schedule. Traditionally, both planning steps have been approached sequentially where vehicle schedules are determined before crew schedules. In this thesis, however, we focus on the integrated consideration of vehicle and crew scheduling. The integration of both planning steps discloses additional flexibility that can lead to gains in efficiency compared to sequential planning. Until recently it was not possible to solve real-world integrated vehicle and crew scheduling problems with several depots within reasonable time and guaranteed solution quality. Still, large instances with complex duty feasibility rules cannot be tackled in an integrated manner. We formulate the integrated vehicle and crew scheduling problem as combinatorial optimization problem. The basis of our mathematical formulation is a time-space network representation of the underlying vehicle scheduling problem that has led to promising results in literature. We solve the integrated problem with column generation in combination with Lagrangian relaxation. In this thesis, we propose an approach for the column generation pricing problem that involves two novel network formulations for a decomposed pricing problem. We show that the network complexity of our approach is beneficial compared to other approaches previously exposed in literature. We apply a dynamic programming method to solve the pricing problem. In this context, we discuss known as well as novel adaptations of preprocessing and acceleration techniques that are essential to solve large problem instances. Furthermore, we discuss three solution methods to construct integer solutions, namely a Lagrangian heuristic, a branch-and-bound method, and a novel heuristic branch-and-price method. Our computational results indicate that our method outperforms other approaches from literature in terms of computational time and solution quality. For well-known benchmark instances, we presented previously unknown solutions and were able to tackle the largest instances so far. Furthermore, we present a novel hybrid evolutionary algorithm for the multiple-depot integrated vehicle and crew scheduling problem that combines mathematical programming techniques with an evolutionary algorithm. Our computational results show that the algorithm performs worse than the best known integrated approach, but its solution quality increases with the problem size. However, our approach discloses significant savings compared to the traditional sequential approach without requiring a fully integrated solution method. Finally, we consider practical rules and regulations arising in public transport companies in Germany. We suggest extensions and modifications of our modelling and solution approach to cover these practical extensions. Moreover, we consider the case where timetables consist of many trips serviced everyday together with some exceptions that do not repeat daily. Traditional optimization methods for vehicle and crew scheduling in such cases usually produce schedules that contain irregularities which are not desirable in practice. We propose a solution method which improves regularity while partially integrating the vehicle and crew scheduling problems.

Deutsch

Busumlauf- und Dienstplanung sind zwei wesentliche Planungsprobleme von Unternehmen im öffentlichen Personennahverkehr (ÖPNV). In der Umlaufplanung werden die vom Fahrplan vorgegebenen Personenbeförderungsfahrten den vorhandenen Fahrzeugen zugeordnet. In der Dienstplanung wird jeder Fahrzeugaktivität der vorher erzeugten Fahrzeugumläufe ein Fahrer zugeordnet. Beide Planungsprobleme wurden in der Vergangenheit meist sequenziell gelöst: Fahrzeugumlaufpläne werden vor den Dienstplänen bestimmt. In dieser Arbeit betrachten wir hingegen die integrierte Planung von Umlauf- und Dienstplänen. Es ist bekannt, dass die Integration beider Planungsschritte zu Effizienzgewinnen im Vergleich zur sequenziellen Planung führen kann. Bis vor Kurzem war es nicht möglich, kleine bis mittlere integrierte Probleme aus der Praxis mit vertretbarem Zeitaufwand und garantierter Lösungsqualität zu lösen. Nach wie vor können große Praxisinstanzen mit komplexen Dienstzulässigkeitsregeln nicht durch integrierte Ansätze gelöst werden. Wir formulieren das integrierte Umlauf- und Dienstplanungsproblem als kombinatorisches Optimierungsproblem. Die Basis unserer Formulierung bildet eine Time-Space-Netzwerkmodellierung des zugrunde liegenden Umlaufplanungsproblems, die in der Literatur zu viel versprechenden Ergebnisse führte. Wir lösen die integrierten Modelle mit einer Kombination von Spaltengenerierung und Lagrange Relaxation. In dieser Arbeit stellen wir für den Pricing-Schritt zwei neuartige Netzwerkformulierungen für ein dekomponiertes Pricing-Problem vor. Wir zeigen, dass die Netzwerkkomplexität unserer Formulierungen günstig im Vergleich zu anderen Ansätzen aus der Literatur ist. Wir verwenden dynamische Programmierung zur Lösung der Pricing-Probleme. In diesem Zusammenhang beschreiben wir bekannte sowie neue Anpassungen von Preprocessing- und Beschleunigungstechniken, die zur Lösung großer Instanzen notwendig sind. Weiterhin stellen wir drei Methoden zur Generierung von zulässigen (ganzzahligen) Lösungen vor: eine Lagrange-Heuristik, eine Branch-and-Bound-Methode sowie eine neuartige, heuristische Branch-and-Price-Methode. Die Ergebnisse auf realen und künstlichen Instanzen zeigen, dass im Vergleich zu anderen Methoden aus der Literatur unser Ansatz in Bezug auf Lösungszeit und Lösungsqualität überlegen ist. Auf bekannten Benchmark-Instanzen konnten wir bisher unbekannte Lösungen präsentieren sowie die bisher größten Instanzen lösen. Weiterhin stellen wir für das integrierte Problem eine neue hybride, evolutionäre Methode vor, die Techniken der mathematischen Programmierung mit einem evolutionären Algorithmus verbindet. Dieser Ansatz ist unserer vorherigen Methode zwar unterlegen, zeigt allerdings deutliche Effizienzgewinne im Vergleich zu einer sequenziellen Planung. Schließlich beschreiben wir Erweiterungen und Modifikationen unseres Verfahrens, die es erlauben alle wesentlichen gesetzlichen Regelungen zur Dienstzulässigkeit in Deutschland abzubilden. Zudem betrachten wir den Fall mit unregelmäßigen Fahrplänen, wo viele Passagierfahrten täglich und einige Ausnahmen nicht täglich durchgeführt werden. Mit traditionellen Optimierungsansätzen für die Umlauf- und Dienstplanung entstehen dabei in der Praxis unerwünschte unregelmäßige Dienstpläne für Busfahrer. Wir schlagen Verfahren vor, die die Konstruktion von kosteneffizienten Dienstplänen mit deutlich verbesserter Regelmäßigkeit erlauben.