Towards Intelligent Control of Vehicle Depot Parking and Dispatching

Abstract

Betriebshöfe für Fahrzeuge stellen eine anspruchsvolle reale Umgebung für Online-Entscheidungen dar. Fahrzeuge werden häufig platzsparend hintereinander in Spuren abgestellt. Diese Anordnung führt jedoch zu Blockierungsrestriktionen: Nur das vorderste Fahrzeug einer Spur kann direkt ausfahren. Dadurch beeinflusst jede Parkentscheidung, ob zu einem späteren Zeitpunkt geeignete Fahrzeuge für geplante Umläufe verfügbar sind. Die Situation wird zusätzlich komplexer, wenn auch Fahrzeugtypen, Ladezustand der Batterien, Ladevorgänge, heterogene Spur- und Flächenlayouts sowie betriebliche Störungen wie Verspätungen berücksichtigt werden müssen.

Ziel dieser Arbeit ist die Untersuchung robuster Entscheidungsstrategien für die Echtzeitsteuerung von Fahrzeugdepots. Der Fokus liegt auf der Auswahl geeigneter Aktionen für ankommende und abfahrende Fahrzeuge sowie auf notwendigen Umsetzbewegungen innerhalb des Depots, um betriebliche Verklemmungen oder Deadlocks zu vermeiden. Aufbauend auf einem bestehenden Java-basierten Framework und Simulator soll untersucht werden, ob sich allgemeinere und besser übertragbare Strategien entwickeln lassen, die nicht von depotspezifischen Heuristiken abhängen. Mögliche Richtungen umfassen interpretierbare regelbasierte oder suchbasierte Verfahren, Machine-Learning- bzw. KI-basierte Ansätze oder hybride Kombinationen daraus.

Hintergrund

Effiziente Betriebsabläufe in Depots sind entscheidend für einen zuverlässigen öffentlichen Verkehr, insbesondere vor dem Hintergrund des zunehmenden Einsatzes elektrischer Fahrzeuge. In vielen Depots werden Fahrzeuge hintereinander in Spuren geparkt. Diese Struktur nutzt den verfügbaren Platz effizient aus, bringt jedoch starke betriebliche Einschränkungen mit sich, da nur das erste Fahrzeug einer Spur unmittelbar zur Ausfahrt verfügbar ist. Eine ungünstige Parkentscheidung kann deshalb dazu führen, dass ein ankommendes Fahrzeug nicht eingeparkt werden kann oder ein geplanter ausgehender Umlauf nicht durch ein geeignetes Fahrzeug bedient werden kann.

Neben diesen Erreichbarkeitsrestriktionen muss die Depotsteuerung auch die Kompatibilität von Fahrzeugtypen, den Ladezustand der Batterie, Ladevorgänge, unterschiedliche Fahrzeuglängen, heterogene Parklayouts sowie Störungen wie Verspätungen oder vorübergehend nicht verfügbare Stellplätze berücksichtigen. Da Entscheidungen online und unter strengen Laufzeitvorgaben getroffen werden müssen, handelt es sich um ein praktisch hoch relevantes und zugleich rechnerisch anspruchsvolles diskretes Optimierungsproblem.

Ein bestehendes Software-Framework sowie ein Benchmarker in Java sind bereits vorhanden. Die aktuellen Basisansätze funktionieren für ein bestimmtes Depot-Setting gut, basieren jedoch auf Heuristiken, die speziell auf dieses Depot zugeschnitten sind und daher möglicherweise nur eingeschränkt verallgemeinerbar sind. Ziel dieser Arbeit ist es deshalb, alternative Strategien zur Aktionsauswahl zu untersuchen, die robuster sind und sich besser auf unterschiedliche Depots und Betriebsbedingungen übertragen lassen.

Informationen

• Masterarbeit für 1 Person (Bachelorarbeit auch möglich)
• 30% Theorie, 70% Umsetzung

Voraussetzungen

Idealerweise Kenntnisse in einigen der folgenden Bereiche:

• Algorithmen und Datenstrukturen
• Diskrete Optimierung / Operations Research
• Suchverfahren
• Machine Learning / KI
• Java-Programmierung

Ziel & Umfang der Arbeit

Ziel der Arbeit ist die Entwicklung und Evaluation einer robusten Strategie zur Online-Steuerung von Fahrzeugdepots, die sich besser auf unterschiedliche Depots und Betriebsbedingungen übertragen lässt als bestehende heuristische Ansätze. Erwartet wird eine implementierte und experimentell validierte Methode, die Echtzeitentscheidungen für das Einparken, Bereitstellen und Umsetzen von Fahrzeugen zuverlässig unterstützt und dabei Lade- sowie betriebliche Restriktionen berücksichtigt. Die Arbeit soll zur praktischen Automatisierung von Depotprozessen beitragen und eine Grundlage für skalierbarere und besser übertragbare Entscheidungsunterstützungssysteme im öffentlichen Verkehr schaffen.

Literaturrecherche
Untersuchung bestehender Ansätze aus den Bereichen diskrete Optimierung, Online-Entscheidungsfindung, Suchalgorithmen sowie Machine Learning / KI zur Lösung eingeschränkter betrieblicher Planungsprobleme.

Methodenentwicklung
Analyse des bestehenden Frameworks und der vorhandenen Basisansätze. Entwurf, Implementierung und Verbesserung einer neuen Strategie zur Aktionsauswahl in Echtzeit. Mögliche Richtungen sind White-Box-Verfahren wie regelbasierte oder suchbasierte Methoden, Black-Box-Ansätze aus KI bzw. Machine Learning oder hybride Verfahren, die beide kombinieren. Nach einer ersten Analyse kann die vielversprechendste Richtung ausgewählt werden.

Evaluation
Vergleichende Analyse der entwickelten Methode mit bestehenden Basisansätzen unter Verwendung des vorhandenen Simulators und Benchmarkers. Die Evaluation sollte mehrtägige Simulationen, reale Depotinstanzen und gegebenenfalls zusätzliche synthetische Depotlayouts umfassen. Relevante Leistungskennzahlen sind unter anderem Zulässigkeit/Feasibility, Robustheit gegenüber Störungen, Laufzeitverhalten und die Fähigkeit, Deadlocks zu vermeiden.

Bewerben

Interessiert? Dann schicke uns deinen Lebenslauf zusammen mit einer kurzen Darlegung deiner Motivation für diese Thesis an thesis@scs.ch.