Das NP-Problem der Elektromobilität

Informatiker aus Hongkong haben gezeigt, dass die optimale Verteilung von Ladestationen für E-Autos leider nicht einfach und elegant zu berechnen ist. Man muss verschiedene Strukturen durchprobieren.

Der Markt für Elektroautos kommt allmählich in Schwung. Tesla Motors fertigt in seiner kalifornischen Fabrik 500 Wagen pro Woche, 21.000 sollen es insgesamt in diesem Jahr werden. Dazu kommen Modelle wie der Nissan Leaf, der BMW i3, der Ford Focus Electric und der Honda Fit EV. Doch trotz wachsender Auswahl gibt es gute Gründe, noch nicht auf ein Elektromobil umzusteigen. Einer der wichtigsten: Es gibt nirgendwo eine auch nur annähernd ausreichende Anzahl von Ladestationen. Bei Reichweiten von 200, 250 Kilometern muss man schon planen, wo es langgeht. Drauflos fahren gibt es nicht.

Eine Ladeinfrastruktur muss her, keine Frage. Eine naheliegende Idee wäre, einfach an jeder existierenden Tankstelle Stromanschlüsse für den E-Auto-Akku zu errichten. Eine gute Idee wäre es nicht, denn das Laden der E-Mobile dauert immer noch so lange, dass sich recht bald Schlangen bilden würden. Hinzu kommt, dass – wenn man von Städten einmal absieht – die vorhandenen Tankstellen kein ideales Netz für die derzeitigen Reichweiten ergeben würden.

Deshalb haben sich Albert Lam und seine Kollegen von der Hong Kong Baptist University das Problem theoretisch vorgeknöpft: Wie sähe eine ideale räumliche Verteilung von Ladestationen aus? Und eine nicht ganz so schöne Antwort gefunden: Das Problem ist mathematisch gesehen „NP-schwer“ (NP steht für nichtdeterministische Polynomialzeit). Das bedeutet, dass es keine Abkürzung gibt, um rasch Lösungen zu finden. Man muss das Problem erschöpfend durchrechnen.

Immerhin haben Lam und Kollegen einige Algorithmen entwickelt, mit denen sich Lösungen für verschiedene Szenarien finden lassen.

Zunächst einmal formulierten die Informatiker das Problem so, dass es sich handhaben lässt. Hierzu nahmen sie ein Netz aus Ladestationen an und definierten einige Randbedingungen für dessen Betrieb. Die erste Randbedingung ist offensichtlich: Ein neu vollgeladenes Fahrzeug muss mit der Strommenge irgendeine andere Station erreichen können. Der Abstand zwischen den Stationen darf also nicht über der Reichweite liegen.

Die zweite Randbedingung folgt aus der Anzahl der E-Mobile in der Umgebung der Ladestation: Die lokale Nachfrage muss von dieser Station und zu einem geringen Anteil von benachbarten Ladestationen bewältigt werden können. Der Anteil ergibt sich aus der Bereitschaft der Fahrer, nicht nur die eigene Station anzufahren. Eine Konsequenz daraus lautet bereits: Je kleiner dieser Bruchteil ist, desto dichter müssen die Ladestationen gebaut werden.

Die dritte und letzte Randbedingung legt fest, dass die Ladestationen das gesamte Stadtgebiet abdecken müssen. Man muss also von jedem beliebigen Stadtteil in einen beliebigen anderen gelangen können, indem man notfalls auch nachlädt. „Diese Bedingungen garantieren zusammengenommen, dass die Stationen jeden Winkel der Stadt für sämtliche E-Autos abdecken“, fassen Lam und Kollegen den Ansatz zusammen.

Die Algorithmen, die sie entwickelt haben, fangen im Wesentlichen an, erst einmal Ladestationen zufällig über ein Stadtgebiet zu verteilen. In einem Testlauf wird dann überprüft, ob das Netz die drei Kriterien erfüllt. Tut es das, und haben weitere Kriterien einen Minimalwert, ist diese Verteilung eine gültige Lösung. Eleganter und effizienter wäre es natürlich, einen raschen Lösungsweg zu haben – doch das geht aufgrund der NP-Schwierigkeit des mathematischen Problems nicht.

Im dritten Teil ihrer Arbeit wendete die Gruppe um Lam ihre Methode auf das Stadtgebiet von Hongkong an. Dort plant die Stadtregierung bereits, mittelfristig Busse und Taxis sowie einen Teil der anderen Fahrzeuge auf Elektroantrieb umzustellen. Also wird Hongkong Ladestationen errichten müssen. Hierfür haben Lam und seine Mitstreiter verschiedene Netzstrukturen ermittelt. Die könnten in Zukunft noch aktualisiert werden, wenn neue Bedingungen hinzukommen, etwa die Verkehrsdichte auf den Straßen der chinesischen Metropole. Die wird noch einige Aufgaben zu erledigen haben, um die Elektrowende anzuschieben – die optimale Verteilung der Ladestationen können die Stadtväter nach der Arbeit von Lam und Kollegen immerhin abhaken.

Das Paper:
Lam, Albert et al.: „Electric Vehicle Charging Station Placement: Formulation, Complexity, and Solutions“, arXiv.org ()