Deutsch

Unter der fortschreitenden Privatisierung des ÖPNV-Marktes in Deutschland und immer tiefer greifenden Kürzungen der öffentlichen Subventionen, ist ein ökonomischer und möglichst effizienter Ressourceneinsatz für die betroffenen ÖPNV-Unternehmen überlebenswichtig. Um diese komplexe Aufgabe zu lösen, werden immer häufiger computergestützte Planungswerkzeuge auf Basis der mathematischen Optimierung eingesetzt. Allerdings verfolgen solche Planungstools bei der Ressourceneinsatzplanung, ähnlich zu der manuellen Planung, eine streng sequenzielle Vorgehensweise: Zuerst werden Umläufe für Fahrzeuge geplant und darauf basierend Dienste für Fahrer. Dies kann eine Einschränkung des Lösungsraums bedeuten. Eine simultane Behandlung der Umlauf- und Dienstplanung bietet dagegen mehr Freiheitsgrade und stellt zusätzliches Einsparpotenzial dar. Im Rahmen der vorliegenden Arbeit wurden unterschiedliche Modelle und Verfahren zum Lösen integrierter Umlauf- und Dienstplanungsprobleme mit mehreren Depots entwickelt und untersucht. Neben einer vollständigen Integration der beiden Planungsprobleme wurde ein teilintegrierter Ansatz vorgestellt, der wesentlich bessere Ergebnisse als die in der heutigen Praxis verbreitete sequentielle Planung liefert und gleichzeitig für große Probleminstanzen einsetzbar ist. Weiterhin sind alle entwickelten Verfahren miteinander kombinierbar und bieten somit dem Planer ein flexibles Instrument zur Lösung der Umlauf- und Dienstplanungsprobleme mit unterschiedlichen Anforderungen an die Lösungszeit und -Qualität.

English

Due to the increasing privatisation of the public transport market in Germany and drastic reduction of the subsidies, an economical and efficient use of given resources is crucial for public transport companies. In order to manage such a complex task, they often use computed-aided planning tools based on the mathematical optimization. However, such tools pursue a sequential approach similar to the manual planning: vehicle scheduling first and crew scheduling afterwards. This process can restrict the solution space. On the contrary, the integration of both planning steps provides additional flexibility that can lead to the gains in efficiency. This thesis deals with the development and analysis of several models and solution approaches which can be applied to solve integrated vehicle and crew scheduling problems with multiple depots considering a variable degree of integration. In addition to a complete integration of both planning problems, a new partial integrated approach is presented. It outperforms the traditional sequential planning, and is applicable for large problem instances. Furthermore, all presented approaches can be combined with each other offering a flexible framework for solving vehicle and crew scheduling problems with different requirements on the solution time and quality.