English

Been obliged to act market-oriented instead of the traditional monopolistic approach, public transport companies focus on efficient use of resources, especially vehicles. The vehicle scheduling problem, arising in public transport bus companies, addresses the task of assigning buses to cover a given set of timetabled trips with consideration of additional requirements, such as multiple depots and vehicle types as well as depot capacities. An optimal schedule is characterized by minimal fleet size and minimal operational costs including costs for unloaded trips and idle time, spent outside from depot. Operations research based decision support systems play hereby a crucial role. Different models and procedures were developed for the optimization of the vehicle usage. In the context of this thesis, we refer to all models that represent connections explicitly as "connection-based" models. As connection-based multidepot vehicle scheduling models inherently include a very large number of arcs, such models of practical dimensions with thousands of trips and multiple depots often can not be solved with standard optimization software packages. This work proposes a time-space-based network model instead of a connection-based one. This leads to a crucial size reduction of the corresponding mathematical models compared to well-known connection-based network flow or set partitioning models. The proposed modeling approach enables us to solve real-world multi-depot problem instances with thousands of scheduled trips by direct application of standard optimization software. In order to solve very large practical instances we propose a two-phase method which produces near-optimal solutions. One developed heuristic reduces the model size by fixing a part of the original variables, so that it is possible to solve the reduced problem to optimality. The basic idea of the heuristic is first to solve a number of simplified models, for example a single-depot vehicle scheduling problem for each depot, and then to search for common chains of trips in each of the solutions. If the same sequence of trips is included in each solution, we denote it as a stable chain and assume that it may occur in the optimal global solution as well. Furthermore, various practical requirements, arising in different public transport companies, are taken into account, so that the savings induced by the approach of this work can be realized in practical applications. Thus, we introduce the concept of depot groups for the case that a bus may return in the evening into another depot than it started in the morning. The modeling approach considers depot and vehicle type capacities, bus lines and time windows for the timetabled trips. Several practical side constraints are considered in the postprocessing phase, where we construct an optimal vehicle schedule from the optimal network flow via flow decomposition. In the context of a co-operation with the software development company PTV AG, we designed and implemented a software component which supports public transport planners in constructing schedules for buses. The presented methods are integrated in commercial systems of the PTV AG and are already used in the planning of the vehicle schedules of several public transport companies.

Deutsch

Um sich im ÖPNV-Markt in Hinblick auf die fortschreitende Privatisierung und die aktuelle schwierige Wirtschaftslage behaupten zu können, müssen Verkehrsunternehmen immer stärker an den Anforderungen dieses Marktes orientieren. Die Fahrpläne werden dem Beförderungsbedarf angepasst und sollen mit den vorhandenen Ressourcen möglichst kostengünstig bedient werden. Im Rahmen der Fahrzeugeinsatzplanung, die auf einem fest vorgegebenen Fahrplan basiert, werden alle Fahrten eines Tages den Fahrzeugen zugewiesen. Ein Fahrzeugumlaufplan wird erstellt; die darin enthaltenen Leerfahrten und Standzeiten verursachen die operativen Kosten des Fahrzeugeinsatzes. Diese gilt es, zusammen mit den fixen Kosten für benötigte Fahrzeuge, zu minimieren. Bei der Erstellung kostenminimaler Umlaufpläne spielen Werkzeuge zur Entscheidungsunterstützung eine entscheidende Rolle. Diese Werkzeuge basieren oft auf den Modellen und Methoden aus Operations Research. In der Operations Research Literatur sind einige Modelle und Verfahren für die Optimierung des Fahrzeugeinsatzes beschrieben. Diese Modelle, die alle zulässigen Verknüpfungen zwischen Fahrplanfahrten explizit berücksichtigen, werden im Kontext dieser Arbeit connection-basierte Modelle genannt. Weil connectionbasierte Netzwerkmodelle eine sehr große Anzahl von Kanten beinhalten, können große Mehrdepot-Probleminstanzen aus der Praxis häufig nicht mit Standardoptimierungspaketen gelöst werden. Im Gegensatz zu den existierenden Ansätzen erfolgt die Modellierung in der vorliegenden Arbeit auf Basis von einem Time-Space-Netzwerk anstelle von connection-basierten Netzwerken. Diese Modellierungstechnik ermöglicht es, auch extrem große reale Umlaufplanungsprobleme mit mehreren Depots und vielen Tausend Fahrten mit Standard-Optimierungssoftware innerhalb einer akzeptablen Zeitspanne optimal zu lösen. Um die Lösungszeiten weiter zu reduzieren beziehungsweise um extrem große Probleminstanzen lösen zu können, die mit keinem existierenden exakten Verfahren lösbar sind, werden approximative Modelle und Verfahren erarbeitet. Dabei werden einige Fahrten im Vorfeld der Optimierung zu Teilumläufen miteinander verknüpft. Auf diese Weise kann der Lösungsraum der mathematischen Modelle erheblich reduziert werden, ohne sich zu weit von der optimalen Lösung zu entfernen. Ergebnisse für verschiedene Instanzen weisen eine sehr gute Lösungsqualität auf. Das vorgeschlagene Modell wird darüber hinaus um spezielle Anforderungen ergänzt, die sich beim praktischen Einsatz der Methoden in verschiedenen ÖPNV-Betrieben ergeben. Möglich ist nun eine Berücksichtigung von Kapazitäten verschiedener Art, wie Stellplatzkapazitäten, Begrenzungen in der Fahrzeugflotte sowie feste Vorgaben für die Anzahl von Fahrzeugen bestimmter Typen in bestimmten Depots. Im Modell werden außerdem eine umlauf- oder volumenbezogene Vergabe von Fahrleistungen an Fremdunternehmen sowie zeitliche Verschiebeintervalle für Fahrten zwecks Fahrzeugeinsparung integriert. Ein zusätzlicher Focus der Arbeit liegt auf der Berücksichtigung weiterer praktischer Aspekte bei der Bildung der Umläufe in der Flussdekomposition. Auf Wunsch des ÖPNV-Planers können die Fahrzeugeinsatzpläne in Bezug auf die Linienreinheit verbessert werden, ohne dabei auf die Kostenoptimalität zu verzichten. Die vorgestellten Methoden wurden in die kommerziellen Betriebsplanungssysteme der PTV Planung Transport Verkehr AG integriert und werden in der Planung des Fahrzeugeinsatzes mehrerer ÖPNV-Unternehmen verwendet.