Gleichzeitige Planung von Fahrzeugen und Besatzungen in städtischen Nahverkehrssystemen

Dieses Papier stellt einen exakten Ansatz zur Lösung des Problems der gleichzeitigen Planung von Fahrzeugen und Besatzungen in städtischen Nahverkehrssystemen vor. Wir betrachten den Fall eines einzigen Depots mit einer homogenen Fahrzeugflotte. Dieser Ansatz basiert auf einer Mengenpartitionierungsformulierung für das Fahrerscheduling-Problem, die Nebenbedingungen für die Busrouten integriert. Der vorgeschlagene Lösungsansatz besteht aus einem Spaltengenerierungsprozess (nur für die Besatzungspläne), der in ein Branch-and-Bound-Schema integriert ist. Die Nebenbedingungen für die Busse garantieren, dass eine optimale Fahrzeugzuweisung anschließend in polynomialer Zeit abgeleitet werden kann. Eine rechnerische Studie zeigt, dass dieser Ansatz die vorherigen Methoden in der Literatur für eine Reihe zufällig generierter Instanzen übertrifft. Eine heuristische Version des Lösungsansatzes wird ebenfalls vorgeschlagen und an größeren Instanzen getestet.