Elektro


Für das Carsharing stellen Elektrofahrzeuge aus verschiedenen Gründen eine besondere Herausforderung dar. Eine der Schwierigkeiten ist, dass der Ladestand und relativ lange Ladezeiten bei Buchungswünschen von Kunden berücksichtigt werden müssen. Wie schwierig dieses Problem ist, wie wir es lösen können und welche Parameter die stärksten Auswirkungen auf die Komplexität haben, haben wir in diesem Projekt untersucht.

Mithilfe verschiedener Reduktionen und eigener Algorithmen, haben wir Zeitkomplexitäten für verschiedene Problemvarianten bewiesen.
Wir haben dabei zwischen Entscheidungs- und Optimierungsproblemen unterschieden:

  • Können alle Buchungswünsche mit den gegebenen Autos erfüllt werden?
  • Wie viele Buchungswünsche können maximal erfüllt werden?
Wie wir sehen, ist das Problem bereits für zwei Autos schwer zu lösen.

Lösungen

OCNB

Im Projekt ist der Algorithmus One-Car-N-Bookings (OCNB) entstanden. Dieser Algorithmus findet in polynomieller Zeit eine optimale Lösung für ein Auto. Die Funktionsweise ist im Folgenden beschrieben.

  1. Buchungen in einen Graphen transformieren
  2. Nacheinander alle Knoten traversieren
  3. Für jeden Pfad ein Label mit aktueller Länge und Reichweite anlegen
  4. Pro Knoten nur die besten Pfade behalten
  5. Der längste Pfad entspricht der optimalen Buchungsmenge

Auswertung

Wir haben auch untersucht, wie viele Aufträge Elektroautos im Gegensatz zu Benzinautos erfüllen können, sowie den Einfluss, den die Reichweite und Ladegeschwindigkeit darauf haben. Hier stehen Elektroautos mit 230 Kilometer Reichweite im Vergleich mit Benzinautos. XCYR bezeichnet hier die mehrfache Ausführung des OCNB-Algorithmus, womit auf mehrere Autos gebucht werden kann. Wie man sieht, nähern sie sich bereits bei sehr kleinen Ladegeschwindigkeiten den Ergebnissen von Benzinern an. Bei 40km/h Ladegeschwindigkeit, was ein normaler Wert für moderne Elektroautos ist, sind sie fast gleichauf. Dennoch haben wir weiter untersucht, ob durch Benutzung schneller Lademodi bessere Ergebnisse erziehlt werden können. Dies ist eine praxisrelevante Fragestellung, da solche oft möglich, aber mit Kosten verbunden sind. Es hat sich gezeigt, dass die Nutzung wenig Gewinn erbringt.