Vielerorts sind sie mittlerweile fester Bestandteil des Stadtbilds - die E-Scooter. Als Alternative zu den üblichen individuellen und öffentlichen Nahverkehrsmitteln warten sie vor allem in den Zentren größerer Städte auf ihre Fahrer:innen und können innerhalb des vom Anbieter freigegebenen Bereiches an beliebigen Stellen abgestellt werden. 

Über den Ladevorgang muss sich der:die Nutzer:in keine Gedanken machen: Die E-Scooter werden in der Regel vom Anbieter mit aufgeladenen Akkus versorgt oder abends eingesammelt und morgens vollgetankt neu positioniert.

Eine kostengünstige und weniger personalintensive Alternative könnten fest installierte Ladestationen sein, an denen die Geräte abgestellt werden. Die Herausforderung liegt aufgrund der individuellen Bewegungsmuster in der Positionierung der Infrastruktur - wohin mit den Ladestationen?

Um einen ersten Ansatz zu ermitteln, bieten sich Verfahren an, die einzelne Scooter auf Basis ihrer Standorte zu Clustern zusammenfassen und so mögliche Gruppen für Ladestationen bilden. Um ein Clusterverfahren sinnvoll anwenden zu können, werden möglichst realistische und damit aussagekräftige Daten benötigt. Für diese Analyse werden beispielhaft die Scooter eines Anbieters unseres Münsteraner Standortes betrachtet. Die Daten bilden den tatsächlichen letzten Standort eines Tages für alle E-Scooter ab, deren Akku noch zu maximal 75 % geladen ist - insgesamt 536 Fahrzeuge, die sich über das gesamte Stadtgebiet verteilen.

 

 Abstellort der E-Scooter
 

Auf die Ausgangssituation werden verschiedene Algorithmen angewendet, welche die 536 E-Scooter auf Basis ihrer Geodaten segmentieren und damit eine erste Zuordnung zu einer Ladestation vornehmen. Die zwei ausgewählten Algorithmen K-Means und DBSCAN sind relativ bekannt und verbreitet, gehen bei der Clusterbildung aber unterschiedlich vor.

 

K-Means

K-Means verwendet eine vorgegebene Anzahl von Clustern und verteilt die Clusterzentren zunächst zufällig, um die Datenpunkte dann dem nächstgelegenen Zentrum zuzuordnen. Anschließend werden die Clusterzentren neu berechnet und die Punkte wieder neu zugewiesen - so lange, bis es keine Änderungen mehr gibt.

Da die Startpunkte für die Ladestationen (Clusterzentren) zu Beginn des Algorithmus zufällig gewählt werden, kann es bei mehrfacher Ausführung mit unveränderten Parametern zu unterschiedlichen Ergebnissen kommen.

Hier werden 15 Cluster verwendet, denen alle E-Scooter eindeutig zugeordnet werden. Die Menge der einem Zentrum zugeordneten Punkte wird dabei als Polygon dargestellt, die Farbe der Punkte stellt die Zuordnung zum geografisch nächstgelegenen Zentrum dar.

 


Clusterergebnis K-Means

 

Wie sich an den unterschiedlichen Farben zwischen Punkt und Bereich erkennen lässt, kommt es in den Randbereichen der Cluster dabei zu nicht-optimalen Zuordnungen: Einige wenige Punkte werden nicht dem nächstgelegenen Clusterzentrum zugewiesen. Ursache dieses Verhaltens ist, dass der K-Means-Algorithmus nicht auf das Clustern von Geodaten ausgelegt ist - für die Positionierung der Ladestationen ist die Unschärfe aber akzeptabel. Für die weitere Betrachtung werden die 33 betroffenen E-Scooter dem nächstgelegenen Clusterzentrum zugeordnet.

 

DBSCAN

Anders als K-Means arbeitet Density-Based Spatial Clustering of Applications with Noise (DBSCAN) nicht mit einer vorgegebenen Anzahl an Clustern, sondern bildet diese selbst aufgrund der Dichte der Punkte - E-Scooter, die in innerhalb eines anzugebenden Radius Epsilon eines anderen Fahrzeugs liegen, bilden mit diesem ein Cluste­r. Entscheidend ist also die Beziehung der Punkte untereinander und nicht die Relation zu einem Zentrum.

Außerdem kann gesteuert werden, wie groß eine Menge an Punkten mindestens sein muss. Punkte, die außerhalb von Epsilon liegen oder zu einem Cluster gehören, dass kleiner als der Schwellwert ist, werden als Noise (Rauschen) bezeichnet.

Für eine Clusterung mit Epsilon = 400 Metern und einer minimalen Clustergröße von 6 E-Scootern ergibt sich folgendes Bild:

 


Clusterergebnis DBSCAN 

 

Die Verwendung der Parameter ist eine kleine Gratwanderung: Auffällig ist das große Innenstadtcluster, wo die E-Scooter insgesamt sehr dicht positioniert sind. An den Außenbereichen ist bereits relativ viel Rauschen (hellgrüne Punkte) zu sehen.

Um allen Bereichen gerecht zu werden, werden alle Scooter im Innenstadtbereich nochmals und mit anderen Parametern (Epsilon = 250 m, Min. Clustergröße = 8) neu geclustert.

Da DBSCAN lediglich die Positionierung der Scooter untereinander betrachtet, spielen Clusterzentren keine Rolle. Für die Ladestationen werden diese als geografische Mittelpunkte der Cluster neu berechnet. Daraus ergeben sich die folgenden Cluster (das Innenstadtcluster ist zur Orientierung noch eingezeichnet):

 

 Cluster und Ladestationen DBSCAN 

 

Durch das dichtebasierte Verfahren ist das Clusterzentrum oft nicht die nächstgelegene Ladestation: Während die Cluster bei K-Means zentrisch um die Ladestation gebildet werden, kann es hier beispielsweise vorkommen, dass ein längliches Cluster entsteht, das nah an eine andere Ladestation heranreicht.

Da es um eine initiale Platzierung der Ladestationen geht, wird für das weitere Vorgehen davon ausgegangen, dass alle E-Scooter an der nächstgelegenen aufgeladen werden - auch die Scooter, die als Rauschen eingestuft wurden.

 

Vergleich der Ergebnisse

Die Anzahl der Ladestationen ist mit 15 identisch, bereits auf den ersten Blick wurden diese aber an unterschiedlichen Orten platziert.

Nur marginale Unterschiede gibt es bei der Größe der einzelnen Cluster: Beim Ergebnis mit DBSCAN sind zwei Ladestationen mehr im Bereich bis 19 Scooter vorhanden sind. Um diese auszugleichen, ist eine sehr große Station geplant, die bis zu 120 potenziell Ladwillige aufnehmen müsste.
K-Means-basiert fallen die Cluster in ihrer Größe etwas gleichmäßiger aus, aber auch hier entsteht eine große Station, der mehr als 90 Scooter zugeordnet werden. 


Scooter je Ladestation (Histogramm)

 

Ein besonders aus Sicht der Fahrer:innen spannender Aspekt bei der Betrachtung ist die Entfernung der E-Scooter zur Ladestation, der letztendlich maßgeblich für die Nutzung der Ladestationen sein könnte. Diese liegt im Mittel bei K-Means bei 543 Metern Luftlinie, bei DBSCAN sind es 595 Meter.

Im Boxplot wird zudem deutlich, dass die Standardabweichung bei DBSCAN deutlich höher ist, die Entfernungen also stärker schwanken, und mehr Scooter größere Entfernungen zur Ladestation zu bewältigen hätten.

An dieser Stelle wird deutlich, dass 15 Stationen sich gut für die Verdeutlichung der Verfahren eignen, für die Menge der E-Scooter im realen Einsatz aber zu gering sein könnte. 


Entfernung zur Ladestation (Boxplot) 

Unser Fazit

Für eine initiale Platzierung von Ladestationen liefern sowohl K-Means als auch DBSCAN gute und brauchbare Ergebnisse.

Im Anwendungsfall „Ladestationen für E-Scooter“ hat K-Means etwas die Nase vorn. Grund dafür könnte die Verwendung von Clusterzentren sein, so dass sich keine gestreckten Verbünde wie das Innenstadtcluster ergeben, die dann mehrstufig bearbeitet werden.

Aufgrund der Entfernungen von durchschnittlich mehr als 500 Metern bis zur nächsten Ladestation erscheint die Anzahl der Ladestationen grundsätzlich zu gering. Für ein detailliertes Bild sind mehr Annahmen erforderlich: Wie viele Ladestationen sollen platziert werden bzw. was ist die optimale Anzahl an Ladestationen bei K-Means (Stichwort “Ellbow-Plot”) und wie viele Scooter kann eine Ladestation gleichzeitig aufnehmen? Auch gemischte Strategien aus Ladestationen in Ballungsgebieten und Akkutausch oder Einsammeln für einzelne Gefährte erscheinen sinnvoll und können eine strategische Rolle spielen.

Zudem sind gerade bei DBSCAN Optimierungen möglich: Die Parameter bieten ebenso wie die Berechnung der Ladestation für einen Cluster, z. B. als gewichteter Mittelpunkt, noch Potenzial.

Der Anwendungsfall zeigt, dass Clusterverfahren einen guten Einstieg in die Problemlösung bieten und veranschaulicht beispielhaft, wie wir bei BBHT im Bereich Business Intelligence & Data Analytics arbeiten und welche spannenden Felder, fernab von unserem Branchenfokus „Banken & Versicherungen“, erkundet werden können.

 

Florian Joßbächer
Autor: Florian Joßbächer
Florian Joßbächer arbeitet als Projektmanager und Business Analyst bei der BBHT Beratungsgesellschaft mbH & Co. KG. Bei unterschiedlichen Kunden vor allem in der Banken- und Versicherungsbranche konnte er sein Wissen einbringen und den Projekten zum Erfolg verhelfen.

Wir nutzen Cookies auf unserer Website. Einige von ihnen sind essenziell für den Betrieb der Seite, während andere uns helfen, diese Website und die Nutzererfahrung zu verbessern (Tracking Cookies). Sie können selbst entscheiden, ob Sie die Cookies zulassen möchten. Bitte beachten Sie, dass bei einer Ablehnung womöglich nicht mehr alle Funktionalitäten der Seite zur Verfügung stehen.