Optimierte Platzierung von Ladevorrichtungen für E-Fahrzeuge

Abstract

Batterie-Elektrofahrzeuge leiden an einer kurzen Reichweite und benötigen daher ein dichtes Netzwerk von Ladestationen. Um die Kosten zu senken und ein sorgloses Laden gewährleisten zu können, ist eine robuste Platzierung erforderlich. In dieser Ausarbeitung wird das Problem der Platzierung von Ladestationen untersucht. Dabei wird eine minimale Anzahl an Ladestationen gesucht sodass diese alle kürzesten Pfade einer bestimmten Mindestlänge abdecken. Dazu wurde in dieser Ausarbeitung ein Verfahren entwickelt, das auf hierarchischen Hub-Labels basiert. Dabei wird aus dem Hub-Labeling das entsprechende Hitting-Set extrahiert, welches der Menge der Ladestationen entspricht. Des Weiteren wurde die Korrektheit dieses Verfahrens nachgewiesen. Ergänzend wurden einige Heuristiken und erste Verbesserungen untersucht. Schließlich wurde die Laufzeit und Qualität des implementierten Verfahrens ausführlich auf verschiedenen Graphen mit unterschiedlichen Permutationen getestet. Der Algorithmus liefert dabei eine vielfache Laufzeitverbesserung bei etwas schlechteren Ergebnissen im Vergleich zu anderen Verfahren.