Routing in der Elektromobilität

Diplomarbeit von Vinh Yen Cao

Einleitung:

In der heutigen Zeit führt die Knappheit an nicht erneuerbaren Energieressourcen in vielen Bereichen zu einem Trend umweltschonender Technologien. Daher ist es nötig, umzudenken und Methoden zu entwickeln, welche das Hauptaugenmerk nicht ausschließlich auf das Erzielen von hohen Geschwindigkeiten und Zeitgewinn legen, sondern vor allem den Aspekt der sparsamen Nutzung von Ressourcen beachten.

Dieser Bereich schließt auch den effizienten Gebrauch von Traktionsbatterien, deren Energie zur Fortbewegung von Elektrofahrzeugen genutzt wird, in der Elektromobilität mit ein. Mit aktuellen Batterietechnologien lassen sich Elektromotoren realisieren, die schon energieeffizienter als Verbrennungsmotoren sind, jedoch ermöglichen sie den Fahrzeugen nur verhältnismäßig geringe Reichweiten. Hauptsächlich liegt dies daran, dass Batterien vergleichsweise viel Platz im Fahrzeug benötigen, da sie eine etwa um den Faktor 100 geringere Energiedichte besitzen als fossile Ressourcen wie Benzin oder Diesel. Daher hat die optimale Ausnutzung der Energie für die Mobilität bei batteriebetriebenen Fahrzeugen eine größere Bedeutung als bei herkömmlichen Fahrzeugen.

Ein möglicher Ansatzpunk für eine Verbesserung ist, eine für Elektrofahrzeuge optimal geführte Navigation durch energiebasiertes Routing zu nutzen. Dies hat den Vorteil, dass im Gegensatz zur Berechnung von kürzesten oder schnellsten Routen auf die Minimierung des Energieverbrauchs geachtet wird. Ein solches Routing ist jedoch sehr komplex und von vielen Faktoren abhängig, wie das folgende Szenario aufzeigt.

Viele Elektrofahrzeuge haben durch die begrenzte Batteriekapazität im Vergleich zu Fahrzeugen mit Verbrennungsmotor nur eine geringe Reichweite. Das Fahrzeugmodell smart fortwo electric drive des Herstellers Smart, welches vollständig elektrisch angetrieben wird, besitzt eine Reichweite von etwa 135 km mit einer vollen Batterieladung, was beispielsweise einer Fahrt von Aachen nach Antwerpen entspräche. Dieser Wert wird jedoch nur vom Hersteller als Richtwert angegeben: In der Praxis werden solche Angaben sehr selten erreicht, in den meisten Fällen liegen sie darunter. Es gibt viele Gründe dafür, warum die Richtwerte des Herstellers bezüglich des Energieverbrauchs und der Reichweite oft nicht mit den Erfahrungen aus der Praxis übereinstimmen.

Steigungen:

Bei hohen Steigungen wird erheblich mehr Energie für die Anfahrt benötigt. Ebene Strecken können sich daher positiv auf den Zustand der Traktionsbatterie und die Reichweite auswirken. Außerdem könnten die Schubkräfte, die durch Fahrten mit Gefälle entstehen, für Energierückgewinnungssysteme genutzt werden.

Fahrgeschwindigkeit:

Eine höhere Geschwindigkeit bedeutet in der Regel eine höhere Belastung der Traktionsbatterie und somit eine schnellere Entladung. Der Energieverbrauch ist bei niedrigen Geschwindigkeiten für die gleiche Zeitspanne geringer.

Stadt- oder Autobahnfahrt:

Innerhalb von Städten stellen Ampeln oder verhältnismäßig viele Kurvenstücke auf einer Route unterschiedliche Anforderungen an das Fahrzeug, da beispielsweise Brems- oder Beschleunigungsvorgänge im Stadtverkehr häufiger vorkommen als bei Autobahnfahrten.

Individuelle Fahrweise:

Starkes Beschleunigen oder Abbremsen sowie überhöhte Geschwindigkeiten können zu einem höheren Energieverbrauch führen, wohingegen defensives Fahrverhalten energieeffizienter ist.

Zusätzliches Gewicht:

Anhänger, Beifahrer oder Gepäck beeinflussen durch Erhöhung der Nutzlast mitunter die aufzubringende Energie zur Fortbewegung.

Eines der Probleme, die daraus resultieren, ist die Frage nach der sichergestellten Ankunft an ein Ziel, welches im schlechtesten Fall unmittelbar an der Grenze der Reichweitenangaben des Fahrzeugs liegt. Möchte eine reisende Person mit einem smart fortwo electric drive von Aachen nach Antwerpen fahren, dann könnte eine weniger batterieschonende Fahrt dazu führen, dass das Fahrzeug nicht über genug Energie verfügt, um sicherzustellen, dass der Reisende auch in Antwerpen ankommt.

Ein anderes Problem ergibt sich dann, wenn ein Fahrer mehrere aufeinander folgende Strecken abfahren möchte, aber aus Kostengründen versucht, die Anzahl der Zwischenladungen zu minimieren. Beispiele dafür sind Taxifahrten, ambulante Fahrdienste oder Mietfahrzeuge. Wenn in diesem Fall ungünstige Routen gewählt würden, könnte es eine geringere Anzahl von abgefahrenen Strecken zur Folge haben, bis eine nächste Ladung der Traktionsbatterie nötig ist.

Eine Möglichkeit, diese Probleme zu lösen, ist, vor einer Fahrt einen energiesparenden Weg zu einem Ziel zu bestimmen. Dies kann durch den Einsatz von Routing-Verfahren realisiert werden, die eine optimierte Route für elektrobetriebene Fahrzeuge berechnen. Durch die Reichweitenverlängerung kann entweder ein Fahrzeug eine zusätzliche Distanz zurücklegen oder die überschüssige Energie als Puffer verwendet werden.

Ein Routing-Verfahren analysiert verschiedene Pfade von einem Startpunkt zu einem Ziel und wählt den optimalen Pfad anhand einer Metrik aus. Im Fall der Elektrofahrzeuge ist es daher für Anwender wichtig, dass eine bezüglich des Energieverbrauchs optimale Route für die Fahrt ausgewählt wird. Strecken, die beispielsweise über Gebirgspässe führen, sind für ein solches Fahrzeug nicht optimal, da sie aufgrund der Steigung sehr viel Energie verbrauchen und daher den Ladezustand der Batterie stark vermindern. Ein Umweg, der über eine Strecke mit wenig Höhenunterschied führt, wäre gegebenenfalls ein energiesparenderer Pfad.

Eng mit dem Thema der Routing-Algorithmen verknüpft ist die Navigation im Automobilbereich. Hier haben Navigationsgeräte, wie von den Herstellern Navigon oder TOMTOM, die Aufgabe, den Benutzer mittels eines optimalen Pfads von einer aktuellen Position zu einem bestimmten Ziel zu lotsen. Der Benutzer kann dabei angeben, nach welchen Kriterien eine Route berechnet werden soll. Häufig werden hier die kürzesten oder die schnellsten Wege berechnet. Diese Metriken sind nicht immer optimal: Die Bestimmung von Pfaden für Fahrzeuge, deren Energiekapazität nur begrenzt ist und deren Energieverbrauch einen kritischen Faktor darstellt, stimmt daher in vielen Fällen nicht mit den optimalen Pfaden üblicher Metriken überein, weil der Energieverbrauch überhaupt nicht mit in die Berechnung einbezogen wird.

Die Konsequenz ist, dass die Benutzung einer energiesparenden Strecke eine geringere Entladung der Batterie zur Folge hätte und somit die Reichweite des Fahrzeugs und die Effizienz der Batterie erhöht werden würde.

Um eine effizientere Ausnutzung der Batterie bezüglich der Energie und der Reichweite zu erzielen, wird in dieser Arbeit ein Werkzeug entwickelt, das eine optimale Route für Elektrofahrzeuge bezüglich des Energieverbrauchs ermittelt. Dadurch ergibt sich eine übergeordnete Einteilung der Arbeit in drei Aufgaben. Im ersten Schritt soll ein passender Routingalgorithmus ausgewählt und angepasst werden, der eine optimale Route für Elektrofahrzeuge bestimmt. Danach soll dem Benutzer diese Route visuell präsentiert werden, so dass er von seiner aktuellen Position auf dem berechneten Pfad zum Zielort gelangen kann. Zuletzt soll der angewandte Algorithmus mit einem Elektrofahrzeug verifiziert und optimiert werden.

Inhaltsverzeichnis:

1.	Einleitung	1
1.1	Szenario	1
1.2	Ziel dieser Arbeit	3
1.2.1	Entwurf eines Routingalgorithmus	3
1.2.2	Darstellung einer Route	4
1.2.3	Verifizierung des Verfahrens mit einem Elektrofahrzeug	4
1.3	Gliederung dieser Arbeit	4
2.	Elektromobilität	7
2.1	Elektrofahrzeugkonzepte	7
2.1.1	Personenkraftfahrzeuge	8
2.1.2	Zweiradfahrzeuge	11
2.1.3	Schienenfahrzeuge	12
2.2	Probleme bei Elektrofahrzeugen	12
2.2.1	Leistungsfähigkeit von Traktionsbatterien	12
2.2.2	Reichweitenbeschränkung der Elektrofahrzeuge	14
2.2.3	Ladeinfrastruktur für Elektrofahrzeuge	15
2.3	Anforderungen für das energiebasierte Routing	16
3.	Navigation	17
3.1	Problemstellung in der Navigation	17
3.2	Routing	19
3.2.1	Routingstrategien für treibstoffbetriebene Kraftfahrzeuge	19
3.2.2	Routingstrategien für andere Verkehrsteilnehmer	22
3.3	Suchverfahren in Graphen	23
3.3.1	Uninformierte Suche	24
3.3.2	Heuristische Suche	26
4.	Theoretischer Lösungsansatz	29
4.1	Skizzierung des Lösungsansatzes	29
4.2	Abbilden eines Straßennetzes in eine Graphenstruktur	31
4.3	Aufstellen einer Metrik auf Basis von Einflussfaktoren	32
4.3.1	Fahrzeugspezifische Einflussfaktoren	32
4.3.2	Umweltspezifische Einflussfaktoren	34
4.3.3	Konstruktion eines Fahrzeugmodells aus den fahrzeugspezifischen Einflussfaktoren	36
4.3.4	Konstruktion eines Weltmodells aus den umweltspezifischen Einflussfaktoren	39
4.3.5	Komposition einer Metrik zur Bestimmung der gesuchten Route	40
4.4	Auswahl eines Suchalgorithmus	43
4.4.1	Konstruktion einer Heuristikfunktion	43
4.4.2	Beweis für die Gültigkeit der konstruierten Heuristikfunktion	45
4.4.3	Algorithmus zur Routenberechnung	47
5.	Praktische Umsetzung	49
5.1	Allgemeine Beschreibung der Implementierung	49
5.2	Architektur des Zielsystems	50
5.3	Komponenten des Zielsystems	52
5.3.1	Graphical User Interface	52
5.3.2	Heuristisches Suchverfahren	53
5.3.3	Objektrelationales Datenbanksystem	54
5.4	Verwendete Frameworks und Technologien	54
5.4.1	GeoTools	54
5.4.2	Geographische Daten von OpenStreetMap	56
5.4.3	Höhenbezogene Daten von SRTM	57
5.4.4	PostgreSQL mit PostGIS als geospatiale Datenbankerweiterung	58
5.5	Interaktionsdiagramme der Komponenten	61
5.6	Realisierung	63
5.6.1	Aufbereiten der geodäsischen Daten	63
5.6.2	Entwurf der JAVA-Klassen	65
5.6.3	Darstellung der Route	67
5.7	Probleme	68
6.	Evaluation	69
6.1	Konfiguration der Metrik auf Basis eines Elektrofahrzeug	69
6.1.1	Konfiguration der Parameter des Fahrzeugmodells	70
6.1.2	Konfiguration der Funktionen des Fahrzeug- und des Weltmodells	73
6.2	Verifizierung der Metrik auf Basis der Parametrierung	75
7.	Diskussion und Ausblick	77
7.1	Ausblick	78
8.	Anhang	79
	Abbildungsverzeichnis	85
	Tabellenverzeichnis	87
	Literaturverzeichnis	89

Textprobe:

Kapitel 3, Navigation:

Heutzutage findet man in vielen Bereichen Verfahren zur Navigation, die die geleitete Führung zu einem Ziel als Aufgabe hat. Diese Verfahren werden beispielsweise bei Navigationsgeräten für Automobile genutzt und bieten dem Nutzer automatische Routenbeschreibungen und -führungen und somit eine erhebliche Steigerung des Komforts. Es ist zudem möglich, dass eine Route hinsichtlich verschiedener Aspekte optimiert werden kann, wie der Minimierung der Routenlänge oder der Fahrzeit. Die Anwendbarkeit lässt sich nicht nur auf die Automobilnutzer beschränken: Navigationsgeräte werden außerdem in der Schifffahrt oder im Flugverkehr eingesetzt, aber auch bei Fahrradfahrern oder Fußgängern finden sie Verwendung.

Im Folgenden wird auf den Teilbereich des Routings eingegangen, insbesondere welche verschiedenen Anforderungen an das Routing gestellt werden und welche Strategien entwickelt worden sind. Des Weiteren werden Eigenschaften und Bedeutung von Landkarten bezüglich der Navigation erläutert. Im letzten Abschnitt werden abschließend Verfahren vorgestellt, die anhand einer Landkarte eine Route zwischen zwei Punkten berechnen, und deren Vor- und Nachteile näher betrachtet.

3.1, Problemstellung in der Navigation:

Die Navigation ist ein Hilfsmittel zur Bestimmung und Einhaltung eines optimalen Wegs zu einem Ziel. Auch wenn die Definition der Navigation altertümlich ist und vor allem früher in der Schifffahrt verwendet wurde, unterscheidet sich die Beschreibung der Problematik im Vergleich zu heute grundsätzlich nicht.

‘Die Navigation (lat. navigatio, -onis ‘Schifffahrt’) ist ein Verfahren zur Positions- und Kursbestimmung [...] sowie Planung, Durchführung und Überwachung von Bewegungen auf einem vorbestimmten Weg von einem Ausgangspunkt zu einem definierten Ziel’.

Die Aufgaben, die bei der Navigation gelöst werden sollen, werden im Allgemeinen in drei Teilbereiche gegliedert:

Ortsbestimmung:

Die Position eines Fahrzeugs muss eindeutig bestimmt werden können. In üblichen Verfahren werden häufig Koordinatensysteme eingesetzt, wie beispielsweise durch die Angabe der Position durch geographische Längen- und Breitengrad. Dabei unterscheidet man hauptsächlich zwischen zwei- und dreidimensionalen Positionsdaten, die zusätzlich Höheninformationen enthalten.

Eine Möglichkeit, ein solches Koordinatensystem zu realisieren, ist die Verwendung des Global Positioning System (GPS), eines amerikanischen, satellitengestützten Ortungssystems. Ähnliche Systeme stellen das russische Projekt GLONASS oder das europäische System Galileo dar. Ihre Funktionsweise beruht darauf, dass die Empfangsgeräte mit einer Mindestanzahl von Satelliten kommunizieren und anhand der Laufzeiten von Kontrollnachrichten die Position des Geräts berechnen.

Ein Nachteil des GPS ist die nicht mögliche Ortung bei fehlender, direkter Verbindung zwischen Satelliten und Empfangsgerät. Dies tritt beispielsweise beim Versuch auf, GPS in Gebäuden zu nutzen. Daher verwendet man alternative Technologien wie Bluetooth, RFID, W-LAN, Zigbee oder andere Standards, die nicht satellitengestützt sind, sondern auf Abstandsberechnungen zwischen verschiedenen Sende- und Empfangsstationen innerhalb von kurzen Distanzen beruhen und keinen direkten Sichtkontakt benötigen.

Der Gebrauch von Landmarks ist eine weitere Möglichkeit, eine Ortung und eine Führung zu realisieren, indem man die Entfernung zu bestimmten Objekten in der Umgebung zur Berechnung miteinbezieht. Dabei werden diese Objekte mit einer GPS-Angabe versehen und zusätzlich mit einer Beschreibung in Form eines Textes oder eines Bilds verknüpft, um dem Benutzer Anhaltspunkte für seinen Aufenthaltsort zu geben.

Routenberechnung:

Für einen Reisenden reicht die Ortsbestimmung nicht aus, um zu einem Zielort zu gelangen. Zusätzlich muss dem Nutzer eine Route angegeben werden, die den Weg zum Ziel beschreibt. Die Voraussetzungen für die Berechnung einer Route sind zum einen das Vorliegen einer Landkarte mit Streckenbeschreibungen, wie Weglängen, Höhen oder Geschwindigkeitsbeschränkungen, und zum anderen die Kenntnis über die Position des Ziels. Mit diesem Wissen hat man die Möglichkeit, durch Suchalgorithmen eine Route zwischen Ausgangsposition und Ziel zu berechnen. Die Verfahren, die eingesetzt werden können, werden in Kapitel 3.3 beschrieben. Die Routenberechnung wird nachfolgend in dieser Arbeit als Routing bezeichnet.

Einhalten des vorbestimmten Wegs:

Unter Umständen kann der Reisende von seiner vorbestimmten Route abweichen, so dass eine neue Berechnung nötig ist oder diese Situation dem Benutzer signalisiert wird. Dies ist zum Beispiel der Fall, wenn Strecken nicht mehr passierbar sind und der Benutzer deshalb der Route nicht mehr folgen kann. Das Abweichen von der Route würde man mit einer kontinuierlichen Ortsbestimmung erkennen, die mit der berechneten Route abgeglichen wird. Diese Teilaufgabe der Navigation wird in dieser Arbeit aber nicht weiter vertieft.

Wo früher Sternenbilder und ungenaue Seekarten für die drei oben genannten Teilaufgaben bei der Navigation in der Schifffahrt ausreichend waren, erfüllen Navigationsgeräte mit wesentlich präziserem, digitalem Kartenmaterial, Suchalgorithmen und Satellitenortung die Anforderungen heutiger Zeit. Vor allem die Zeitersparnis und die Genauigkeit bei der Berechnung sowie die Benutzerfreundlichkeit und Anwendbarkeit für verschiedene Nutzergruppen sprechen für die Weiterentwicklung im Bereich der Navigation. Da man durch Satelliten- oder Funktechnik schon sehr präzise Positionsangaben erhalten kann, ist das Potential für eine Verbesserung im Bereich der Lokalisation im Allgemeinen eher gering. Daher wird sich der Fortschritt in der Forschung auf die Optimierung des Routings konzentrieren.

3.2, Routing:

Ein Teilbereich der Navigation ist das Routing, welches das Problem der Suche nach einem optimalen Weg von der aktuellen Position zum Zielort beschreibt. Speziell im Bereich der Informatik berechnet ein Routing- oder auch Suchalgorithmus einen optimalen Pfad von einem Startknoten (Quelle) zu einem Zielknoten (Senke) in einem Graphen, was somit eine mögliche Herangehensweise zur Lösung eines Routings darstellt. Optimalität bedeutet in diesem Fall, dass dabei genau der Pfad gewählt wird, der am kostengünstigsten bezüglich einer vordefinierten Metrik ist. Eine Metrik ist ein numerisches Maß für die Güte einer Verbindung. Gängige Metriken im Netzwerkbereich sind beispielsweise:

- Anzahl der Hops.

- Verzögerung oder Kosten in der Übertragung.

- Größe der Kapazitäten.

- Verlässlichkeit.

Im Straßenverkehr spielt Routing eine ebenso große Rolle. Dabei wird auf Basis einer Straßenkarte, die aus der Sicht der Informatik einem gerichteten Graph entspricht, ein Routing-Algorithmus angewendet, um einen optimalen Weg zwischen zwei Punkten zu finden, wobei dies in der Regel der Start- und Endpunkt einer Fahrt sind. Diese Algorithmen werden in Navigationsgeräten eingesetzt, jedoch unterscheiden sich die Implementierungen, die sich nach der Anwendergruppe richten.