Energiebasiertes Routing für die Elektromobilität

Inhaltsverzeichnis

1 Einleitung
1.1 Szenario
1.2 Ziel dieser Arbeit
1.2.1 Entwurf eines Routingalgorithmus
1.2.2 Darstellung einer Route
1.2.3 Verifizierung des Verfahrens mit einem Elektrofahrzeug
1.3 Gliederung dieser Arbeit

2 Elektromobilität
2.1 Elektrofahrzeugkonzepte
2.1.1 Personenkraftfahrzeuge
2.1.2 Zweiradfahrzeuge
2.1.3 Schienenfahrzeuge
2.2 Probleme bei Elektrofahrzeugen
2.2.1 Leistungsfähigkeit von Traktionsbatterien
2.2.2 Reichweitenbeschränkung der Elektrofahrzeuge
2.2.3 Ladeinfrastruktur für Elektrofahrzeuge
2.3 Anforderungen für das energiebasierte Routing

3 Navigation
3.1 Problemstellung in der Navigation
3.2 Routing
3.2.1 Routingstrategien für treibstoffbetriebene Kraftfahrzeuge
3.2.2 Routingstrategien für andere Verkehrsteilnehmer
3.3 Suchverfahren in Graphen
3.3.1 Uninformierte Suche
3.3.2 Heuristische Suche

4 Theoretischer Lösungsansatz
4.1 Skizzierung des Lösungsansatzes
4.2 Abbilden eines Straßennetzes in eine Graphenstruktur
4.3 Aufstellen einer Metrik auf Basis von Einflussfaktoren
4.3.1 Fahrzeugspezifische Einflussfaktoren
4.3.2 Umweltspezifische Einflussfaktoren
4.3.3 Konstruktion eines Fahrzeugmodells aus den fahrzeugspezifischen Einflussfaktoren
4.3.4 Konstruktion eines Weltmodells aus den umweltspezifischen Ein- flussfaktoren
4.3.5 Komposition einer Metrik zur Bestimmung der gesuchten Route
4.4 Auswahl eines Suchalgorithmus
4.4.1 Konstruktion einer Heuristikfunktion
4.4.2 Beweis für die Gültigkeit der konstruierten Heuristikfunktion .
4.4.3 Algorithmus zur Routenberechnung

5 Praktische Umsetzung
5.1 Allgemeine Beschreibung der Implementierung
5.2 Architektur des Zielsystems
5.3 Komponenten des Zielsystems
5.3.1 Graphical User Interface
5.3.2 Heuristisches Suchverfahren
5.3.3 Objektrelationales Datenbanksystem
5.4 Verwendete Frameworks und Technologien
5.4.1 GeoTools
5.4.2 Geographische Daten von OpenStreetMap
5.4.3 Höhenbezogene Daten von SRTM
5.4.4 PostgreSQL mit PostGIS als geospatiale Datenbankerweiterung .
5.5 Interaktionsdiagramme der Komponenten
5.6 Realisierung
5.6.1 Aufbereiten der geodäsischen Daten
5.6.2 Entwurf der JAVA-Klassen
5.6.3 Darstellung der Route
5.7 Probleme

6 Evaluation
6.1 Konfiguration der Metrik auf Basis eines Elektrofahrzeug
6.1.1 Konfiguration der Parameter des Fahrzeugmodells
6.1.2 Konfiguration der Funktionen des Fahrzeug- und des Weltmodells
6.2 Verifizierung der Metrik auf Basis der Parametrierung

7 Diskussion und Ausblick
7.1 Ausblick

8 Anhang

Abbildungsverzeichnis

Tabellenverzeichnis

Literaturverzeichnis

1 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 Elektromobili- tä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 [FWS09]. Daher hat die optimale Ausnutzung der Energie für die Mobilität bei batteriebetriebenen Fahrzeugen eine größere Bedeutung als bei herkömmlichen Fahr- zeugen.

Ein möglicher Ansatzpunk für eine Verbesserung ist, eine für Elektrofahrzeuge opti- mal 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 Mi- nimierung des Energieverbrauchs geachtet wird. Ein solches Routing ist jedoch sehr komplex und von vielen Faktoren abhängig, wie das folgende Szenario aufzeigt.

1.1 Szenario

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 ange- trieben 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 Zwischen- ladungen 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 Elektrofahr- zeuge 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 A]ufgabe, 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.

1.2 Ziel dieser Arbeit

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 passen- der 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.

1.2.1 Entwurf eines Routingalgorithmus

Für die Aufgabe, eine optimale Route zu bestimmen, wird ein Algorithmus benötigt, welcher einen optimalen Pfad von einem Startpunkt zu einem Ziel berechnet. Im We- sentlichen besteht der Entwurf dieses Verfahrens aus zwei Schritten: Zuerst muss ei- ne Streckenanalyse vorgenommen werden, die die Güte von Teilstrecken bezüglich des Energieverbrauchs angibt. Auf dieser Basis wird dann ein Algorithmus zur Bestimmung der Gesamtstrecke eingesetzt.

Schritt 1: Streckenanalyse Anfangs werden Teilstrecken, wie beispielsweise einzelne Straßenabschnitte, bezüglich des Energieverbrauchs bewertet. Voraussetzung für diese Analyse ist, Faktoren, die das Entladeverhalten der Batterie beeinflussen, zu finden und diese zu strukturieren. Die zu beachtenden Faktoren werden in zwei Gruppen unterteilt, die jeweils in ein Weltmodell und ein Fahrzeugmodell abgebil- det werden. Diese Modelle bilden zusammen eine Metrik und sind die Grundlage zur Bewertung einer Strecke beziehungsweise einer Route bezüglich des Energie- verbrauchs.
Schritt 2: Algorithmus zur Routenbestimmung Nachdem eine gültige Metrik aufge- stellt wurde, muss nun eine Route berechnet werden. Eine Route wird als eine Aneinanderreihung von Teilstrecken bezeichnet, die einen Start- und Zielpunkt besitzt. Der zu verwendende Algorithmus soll dabei eine optimale Route ausge- ben, die auf der vorherigen Streckenanalyse basiert. Suchalgorithmen können auf dieser Basis eine solche Route bestimmen.

1.2.2 Darstellung einer Route

Es ist nötig, die berechnete Gesamtstrecke mit einem Werkzeug zu visualisieren und dem Benutzer Anweisungen für seine Fahrt mitzuteilen. Eine effektive Möglichkeit ist die Implementierung einer Benutzeroberfläche mit einer digitalen Straßenkarte, um eine Analogie zur klassischen Faltkarte zu schaffen. Hauptaufgabe soll dabei die Darstellung einer Route sein.

Das zu benutzende Kartenmaterial soll schon in digitaler Form vorliegen. Als eine mögliche Quelle bietet sich das Open Source-Projekt OpenStreetMap ⁴ [RTC10] an, welches einen freien Zugriff auf die Datensätze erlaubt und für viele Orte ausreichend detaillierte Karten zur Verfügung stellt.

1.2.3 Verifizierung des Verfahrens mit einem Elektrofahrzeug

Der theoretische Ansatz der Routenberechnung soll mit einem batteriebetriebenen Motorroller verifiziert werden. Durch ein Abfahren von Teststrecken sollen Positions- und Energieverbrauchsdaten aufgenommen und zu der theoretischen Berechnung in Beziehung gesetzt werden. Dies hat den zusätzlichen Vorteil, dass eine Konfigurierung für den theoretischen Ansatz vorgenommen werden kann.

1.3 Gliederung dieser Arbeit

Diese Arbeit gliedert sich im Weiteren wie folgt:

Kapitel 2 analysiert die Anforderungen in der Elektromobilität und Probleme der Elek- trofahrzeuge. Daraus werden Anforderungen abgeleitet, um energiebasiertes Rou- ting zu realisieren.

Kapitel 3 stellt grundlegende Ideen des Routings dar. Zudem werden uniformierte und heuristische Suchverfahren vorgestellt, die bei Graphen und beim Routing einge- setzt werden können.

Kapitel 4 beschreibt den theoretischen Lösungsansatz für die in Kapitel 2 gestellten Anforderungen an das System. Dabei wird insbesondere auf die konstruierten Modelle und die Heuristikfunktion eingegangen, die als Metrik für den Suchalgo- rithmus dienen.

Kapitel 5 beinhaltet die praktische Ausarbeitung des in Kapitel 4 beschriebenen Ver- fahrens und die Komponenten zur Darstellung der optimalen Route.

Kapitel 6 bewertet die Evaluationsergebnisse des Verfahrens durch einen Vergleich mit Testfahrten mit einem Elektrofahrzeug.

Kapitel 7 betrachtet abschließend das implementierte System und beschreibt weitere mögliche Anwendungsgebiete.

2 Elektromobilität

Aus umweltpolitischen und ökonomischen Gründen wird in naher Zukunft die Elektro- mobilität eine wichtige Rolle im Bereich der Automobilindustrie einnehmen. Großen Einfluss darauf möchte die deutsche Bundesregierung nehmen: Im Jahr 2009 stellte sie einen nationalen Entwicklungsplan für die Elektromobilität vor und benannte konkrete Ziele für die Etablierung von Elektrofahrzeugen. So wird in Deutschland versucht, eine nachhaltigere und energieeffizientere Verkehrsinfrastruktur zu schaffen, indem im Jahr 2020 eine Million beziehungsweise im Jahr 2030 fünf Millionen Zulassungen für Elek- trofahrzeuge errreicht werden sollen [Ent09]. Des Weiteren haben auch interantionale Richtlinien wie die Begrenzungen der CO2-Emissionen großen Einfluss auf die Weiter- entwicklung von Technologien in der Elektromobilität, vor allem das aus dem Weltkli- magipfel in Kyoto resultierende Kyoto-Protokoll [Ern10, GAE98] und die vom Welt- klimarat IPCC (Intergovernmental Panel on Climate Change) postulierte 2 ◦ Celsius- Grenze zum Schutz des Weltklimas [SSO+09] wirken darauf ein. Aus diesen Gründen versuchen viele Automobilunternehmen, neue Elektrofahrzeugmodelle am Markt zu po- sitionieren, die sich hinsichtlich der Fahrzeugkonzepte stark unterscheiden.

Um einen Überblick darüber zu geben, werden am Anfang dieses Kapitels die verschiedenen Fahrzeugkonzepte in der Elektromobilität und deren Vorzüge und Funktionsweise beschrieben. Nachfolgend wird auf die Gründe eingegangen, weswegen es für Elektrofahrzeuge schwierig sein wird, sich als Alternative zu treibstoffbetriebenen Fahrzeugen zu etablieren. Daraus wird auch ersichtlich, aus welchem Grund die Verbesserung der Leistung und eine effizientere Nutzung der Batterie die wichtigsten Faktoren in der Weiterentwicklung des Bereichs Elektromobilität darstellen.

2.1 Elektrofahrzeugkonzepte

Heutzutage prägen unterschiedliche Typen von Elektrofahrzeugen das Stadtbild und bieten in vielen Bereichen des Personentransports ausreichende Leistungen, vor allem bei der Energieeffizienz und Umweltverträglichkeit. Diesbezüglich profitieren Elektro- fahrzeuge vor allem von der Tatsache, dass sie keine lokalen CO2-Emissionen erzeugen. In vielen Städten wurden bereits Pilotprojekte gestartet, bei denen Elektrofahrzeuge zur Vermietung bereitgestellt werden und Ladesäulen installiert wurden, wie die Pro- jekte E-mobility Berlin ¹ oder smartlab ² in Aachen, die von verschiedenen Unternehmen unterstützt werden.

Aber auch die private Nachfrage nach Elektrofahrzeugen und der Umsatz von solchen wird mittelfristig ansteigen, wie beispielsweise die Oliver Wyman-Studie „ Elektromobi lität 2025 “ [wym09] belegt. Darin zeigt sich ein erhöhter Bedarf, die Forschung im Bereich der Elektrofahrzeuge weiter zu fördern.

Auf die verschiedenen Fahrzeugkonzepte in der Elektromobilität und deren Eigenschaften wird nachfolgend eingegangen.

2.1.1 Personenkraftfahrzeuge

Die gängigste Form unter den Fahrzeugkonzepten stellen Personenkraftfahrzeuge dar. Aktuell tätigen Automobilhersteller große Investitionen, um die Forschung und Weiter- entwicklung in der Elektromobilität zu fördern. Somit können sie ihre Produktpalette um verschiedene Elektrofahrzeugmodelle erweitern, die jedoch zum großen Teil entwe- der noch in geringen Stückzahlen in Großversuchen eingesetzt werden oder kurz vor der Markteinführung als Serienfahrzeug stehen. Die Personenkraftfahrzeuge kann man hinsichtlich ihrer Technik in folgende Kategorien einteilen, die jeweils vom relativen Fahranteil durch einen Elektromotor und von der Antriebsart abhängen.

Hybridfahrzeuge Klassische Hybridfahrzeuge sind eine weit verbreitete Form von Fahr- zeugen in der Elektromobilität. Für ihren Antrieb können zwei verschiedene Ener- giequellen eingesetzt werden: ein Verbrennungsmotor und eine Traktionsbatterie. Als Hauptmerkmal besitzt eine Traktionsbatterie einen Speicher von 1 bis 10 kWh, der nur während der Fahrt durch den Verbrennungsmotor aufgeladen wer- den kann. Obwohl Hybride hauptsächlich über diesen Verbrennungsmotor an- getrieben werden, kann die Treibstoffeinsparung durch die Hybridform je nach verwendeter Technologie zwischen 5% und 20% [Nau06] liegen, wodurch sich drei Klassifizierungen aufgrund des Fahranteils des Elektromotors ergeben.

Ein Mikrohybrid wird durch eine Starterbatterie gekennzeichnet, die zur Start- Stopp-Automatik-Funktion genutzt und über ein Energierückgewinnungssystem wieder aufgeladen wird. Durch das Ausschalten des Motors im Standbetrieb und des Startens über die Batterie, wird eine kleine Einsparung erzielt. Bei einem Mildhybrid unterstützt ein Elektromotor den Verbrennungsmotor zur Leistungs- steigerung, wohingegen ein Vollhybrid auch rein elektrisch fahren kann.

Neben der Unterscheidung durch den Fahranteil, können Hybridfahrzeugen auch durch die verwendete Antriebsart differenziert werden. Bei einem seriellen Hy- bridantrieb hängt ausschließlich ein Elektromotor am Antriebsstrang des Fahr- zeugs und wird durch eine Leistungselektronik (Umrichter) geregelt. Ein zusätzli- cher Verbrennungsmotor schaltet sich nur dann ein, falls die Leistung der Batterie nicht mehr ausreichend ist, und erzeugt anstelle der Batterie den Strom für den Elektromotor über einen elektrischen Generator. Die Vorteile dieser Antriebsform sind die Verkleinerung des Verbrennungsmotors und der hohe Wirkungsgrad des Antriebs, der durch die ausschließliche Verwendung des Elektromotors erreicht

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1: Aufbau eines seriellen Hybridfahrzeugs.

LE=Leistungselektronik, GE=elektrischer Generator, BAT=Batterie, EM=Elektromotor, VM=Verbrennungsmotor wird. Jedoch erlaubt er aufgrund seiner geringeren Maximalleistung keine hohen Geschwindigkeiten.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.2: Aufbau eines parallelen Hybridfahrzeugs.

VM=Verbrennungsmotor, LE=Leistungselektronik, BAT=Batterie, EM=Elektromotor

Im Gegensatz dazu wirken bei einem parallelen Hybridantrieb Verbrennungs- und Elektromotor direkt auf den Antriebsstrang des Fahrzeugs. Primär wird der Elektromotor als Antrieb benutzt, es können aber auch beide Motoren gleich- zeitig verwendet werden. Durch die Leistungsaddition beider Motoren lassen sie sich jeweils in ihrer Größe verkleinern, was zu einer Gewichtsreduzierung führt („ Downsizing “)[Nau06]. Lässt die Leistung der Batterie im Fahrzeug jedoch nach, so dient der Verbrennungsmotor zeitweise zum Antrieb des Fahrzeugs und zum Aufladen der Batterie, wodurch im Schluss eine Verringerung des Treibstoffverbrauchs erreicht werden kann.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.3: Aufbau eines Mischhybridfahrzeugs.

LE=Leistungselektronik, GE=elektrischer Generator, BAT=Batterie, EM=Elektromotor, VM=Verbrennungsmotor

Ein anderer Ansatz ist der Mischhybridantrieb, welcher eine Kombination aus seriellem und parallelem Hybridantrieb darstellt. Diese Antriebsart besitzt zwei Modi, die dem seriellen und parallelen Hybrid entsprechen: Zum einen kann das Fahrzeug vollständig von einem Elektromotor angetrieben werden, indem der Ver- brennungsmotor dazu dient, die Batterie zu laden. Zum anderen besteht die Mög- lichkeit des parallelen Hybridantriebs, zu dem manuell oder automatisch gewech- selt werden kann. Dies hängt davon ab, ob eine höhere Fahrgeschwindigkeit ge- wünscht wird oder eine leere Batterie während der Fahrt geladen werden soll. Dadurch können die Vorzüge beider Antriebsarten genutzt werden.

Plug-in Hybrid Im Vergleich zu klassischen Hybriden besitzen Plug-in Hybrid-Fahrzeuge eine Batterie mit größerem Energiespeicher³ und können somit als deren konse- quente Weiterentwicklung aufgefasst werden. Ihr Speicher beträgt 5 bis 20 kWh und kann im Gegensatz zu dem von klassischen Hybridfahrzeugen aus einem Stromnetz geladen werden. Dadurch kann eine Reichweite von bis zu 80 km er- reicht werden, ohne Treibstoff zu verwenden. Strecken, die darüber hinaus gehen, werden durch einen herkömmlichen Verbrennungsmotor überbrückt. Man geht davon aus, dass der Ansatz von Plug-in Hybriden in Zukunft eine tragende Rolle einnehmen wird, da über 80% aller Fahrten die Reichweite, die mit einer Batterie ermöglicht wird, nicht übersteigt⁴ [EFK+10]. Als allgemeiner Kritikpunkt dieses Fahrzeugkonzepts ist zu erwähnen, dass das Fahrzeug Treibstoff mit transportiert, der vor allem bei kurzen Strecken nicht verwendet wird.

Elektroautomobil Bei reinen Elektrofahrzeugen ist kein Verbrennungsmotor mehr inte- griert, daher beziehen sie ihre Energie ausschließlich aus einer Traktionsbatterie. Deren Speichergröße liegt aktuell zwischen 20 und 50 kWh und die Batterie wird wie bei einem Plug-in-Hybrid aus dem Stromnetz geladen. Ökonomisch betrachtet kann man aktuell Reichweiten von bis zu 200 km sinnvoll realisieren. Es sind zwar höhere Reichweiten technisch möglich, jedoch nur mit leistungsstärkeren Batteri- en, wodurch diese Automobile im Vergleich zu Fahrzeugen, die mit Treibstoff an- getrieben werden, unverhältnismäßig teurer werden. Auf diese Problematik wird in Kapitel 2.2.1 näher eingegangen.

Reine Elektroautomobile und Plug-in Hybride werden möglicherweise langfristig Fahrzeuge mit Verbrennungsmotoren aus dem Automobilmarkt verdrängen, da sie durch Umweltförderprogramme, wie die Agenda „Elektromobilität 2020“ der Bundesregierung, subventioniert werden. Zudem besagen verschiedene Studien, dass der „ peak oil “, der Höchststand der weltweiten Erdölförderungsmenge pro Jahr, in den nächsten 15 Jahren erreicht sein wird [Age10] oder schon überschritten worden ist [Pri08]. Daher lässt die resultierende, weltweite Erdölverknappung und -verteuerung auf diese Entwicklung zu alternativen Technologien schließen.

2.1.2 Zweiradfahrzeuge

Im Bereich der elektromotorisierten Zweiradfahrzeuge stehen das Pedelec (Pedal Elec- tric Cycle) und der Elektromotorroller im Mittelpunkt. Sie besitzen nur eine ungefähre Reichweite von bis zu 80 Kilometern und sind für den Stadtverkehr sowie für Kurzstre- cken konzipiert.

Pedelecs besitzen im Gegensatz zu Fahrrädern eine zusätzliche Batterie, die für eine Tretverstärkung genutzt wird [Brü99]. Die gespeicherte Energie der eingesetzten Bat- terien beträgt bis zu 650 Wh. Der integrierte Elektromotor zur Verstärkung wird erst eingeschaltet, wenn über einen Sensor eine aktive Pedalenbewegung durch den Fahrer erkannt wird. Pedelecs werden durch ihre Vorteile häufig innerhalb von Städten einge- setzt, daher bieten bereits viele Unternehmen wie die Deutsche Bahn AG ⁵ oder SIXT ⁶ Mietstationen für Pedelecs an.

Zu der Klasse der Elektromotorroller (kurz: Elektro-Roller) gehört beispielsweise der Roller e-max 110s ⁷, welcher einen elektrischen Motor besitzt. Dieser wird über eine Batterie mit einem Speicher von ungefähr 2,8 kWh angetrieben und ersetzt einen Ver- brennungsmotor vollständig in seiner Funktion. Die Reichweite gibt der Hersteller mit rund 50 km für eine Ladung an. Die Tatsache, dass der Roller von der Versicherungs- und Führerscheinklasse zu den Motorrädern mit 50 ccm Hubraum zählt, sowie die Emissi- onsfreiheit und die geringen Fahrtkosten⁸ sind im Sinne der Anwender ausschlaggebende Gründe für eine solche Anschaffung.

In China haben sich Elektro-Roller auf dem Markt bereits durchgesetzt: Durch ein Verbot von Motorrollern mit Verbrennungsmotoren in Shanghai und in Peking ist der Umsatz der batteriebetriebenen Variante von 15.000 Stück im Jahr 1997 auf 1.000.000 Stück im Jahr 2002 angewachsen, bei steigender Tendenz [Wei04, Cro02]. Daher ist abzusehen, dass der Elektro-Roller in China zukünftig „das Fahrrad ablösen und das Rückgrat der Massenmobilität darstellen“ wird [Ern10], und dass vergleichbare Ent- wicklungen aus denselben Gründen auch in Deutschland zu erwarten sind.

2.1.3 Schienenfahrzeuge

Elektrobetriebene Schienenfahrzeuge zählen heute zu den Standardverkehrsmitteln im Personen- und Gütertransport. Zu diesem Bereich zählen Straßenbahnen, unterirdische Bahnen oder Schnellbahnen, wie der ICE oder der Transrapid der Deutschen Bahn AG, die alle die benötigte Energie aus einem Stromleitungsnetz beziehen. Da die In- frastruktur der Bahnen schon weitreichend ausgebaut ist, konzentriert sich beispiels- weise die Agenda „Elektromobilität 2020“ der deutschen Bundesregierung nur auf die Elektrifizierung des Individualverkehrs, „obwohl es [zwischen Schienen- und Individual- verkehrsmittel] interessante Anknüpfungspunkte gibt“, wie die Zusammenführung von Bahnhöfen, Mietstationen für Elektroautos und Pedelecs [Ern10] oder das Aufladen während der Fahrt durch elektrische Oberleitungen⁹. Im weiteren Verlauf dieser Arbeit werden Schienenfahrzeuge aber nicht weiter thematisiert, da sie nur der Vollständigkeit halber an dieser Stelle erwähnt werden.

2.2 Probleme bei Elektrofahrzeugen

Batteriebetriebene Fahrzeuge haben im Vergleich zu Kraftfahrzeugen mit Verbrennungsmotoren noch einige Nachteile, die behoben werden müssen, um eine echte Alternative für potentielle Nutzer darzustellen. Hauptprobleme sind die noch nicht ausgereifte Batterietechnologie für Elektrofahrzeuge, die daraus resultierende geringe Reichweite sowie die vergleichsweise hohen Kosten in der Produktion und Anschaffung. Zudem müssen noch Aspekte bezüglich der benötigten Infrastruktur beachtet werden. Im Folgenden werden diese Probleme näher erläutert.

2.2.1 Leistungsfähigkeit von Traktionsbatterien

Traktionsbatterien sind zwar in der Lage, Fahrzeuge innerhalb einer bestimmten Reich- weite zu bewegen, jedoch bestehen aktuell noch Zweifel über die Alltagstauglichkeit der Batterietechnologie für Plug-in Hybrid- oder Elektrofahrzeuge, vor allem in den folgen- den Bereichen:

- Energiedichte
- Kosten
- Langlebigkeit
- Zuverlässigkeit
- Sicherheit

Es ist zwar eher unwahrscheinlich, dass all diese Problembereiche mittelfristig aus- reichend gelöst werden, aber erst dann würden sich Traktionsbatterien in Fahrzeugen rentieren [And08]. Gelingt dies nicht, wird sich das Fahr- und Tank- bzw. Ladeverhalten der Benutzer ändern müssen, da im Moment die Diskrepanz zwischen der gebotenen Leistung und den Benutzeranforderungen, die an die Traktionbatterie gestellt werden, zu groß ist [AKB10]. Erst wenn die Diskrepanz ausreichend überbrückt wird, indem bes- sere Technologien zur Verfügung stehen oder die Anforderungen abgeschwächt werden, können auch elektrobetriebene Fahrzeuge für Käufer preislich und funktional attraktiv werden. Einen allgemeinen Leistungsüberblick der Batterietypen liefern die Angaben in Tabelle 2.1.

Abbildung in dieser Leseprobe nicht enthalten¹⁰

Tabelle 2.1: Leistungsvergleich der Batterietypen [Bra07]

Das aktuell gravierendste Problem bei der Entwicklung von Traktionsbatterien ist de- ren geringe Energiedichte. Daher benötigen Traktionsbatterien im Fahrzeug vergleichs- weise viel Platz, da sie eine etwa um den Faktor 100 geringere Energiedichte besitzen als fossile Treibstoffe wie Benzin oder Diesel [FWS09]. Bei einer angenommenen Strecke von 200 km würden für ein Elektrofahrzeug ungefähr 30 kWh benötigt werden, wodurch sich ein Gewicht von 250 kg für Lithium-Ionen-Batterien ergäbe. Bei treibstoffbetrie- benen Fahrzeugen würden 15 bis 20 Liter beziehungsweise 12 bis 15 kg Benzin für die gleiche Streckenlänge genügen. Das Verhältnis zwischen den Gewichten des Benzin und der Batterie liegt hier jedoch deutlich unter dem Faktor 100 der Energiedichte, da der Wirkungsgrad des Elektromotors im Gegensatz zum Verbrennungsmotor erheblich höher ist [Sau10]. Neuere Forschungen zeigen aber auch, dass in Zukunft Fortschritte hinsichtlich der Energiedichte von Batterien möglich sein werden, wie zum Beispiel die Entwicklung von Zinn-Schwefel-Lithium-Batterien [HS10]. Sie erzielen eine zehnmal höhere Energiedichte als aktuell eingesetzte Lithium-Ionen-Batterien, sind aber bezüglich der Langlebigkeit noch nicht ausgereift und verhältnismäßig teuer.

Nicht nur die geringe Energiedichte bereitet den Herstellern Probleme, sondern auch die hohen Produktionskosten. Durch teure Werkstoffe, die zur Produktion benötigt wer- den, und die aufwendige Batterieherstellung ergeben sich hohe Kosten pro speicherbarer Leistung. So wird beispielsweise für eine Lithium-Ionen-Batterie mit einer Kapazität von 30 kWh, die für eine Reichweite von 200 km genügt, ein Einkaufspreis von mindestens 30 × 300 e veranschlagt. Dies entspricht alleine schon dem Verkaufspreis eines herkömmlichen Kleinwagens. Benutzer sind aber nicht bereit, einen solch hohen Aufpreis für diese Technologie zu zahlen.

Zusätzlich führt die über die Zeit kontinuierliche Verminderung der Batterieleistung und der Qualität zu einer begrenzten Lebensdauer. Blei-Batterien, die vor allem in batteriebetriebenen Motorrollern verbaut werden, müssen schon nach spätestens drei Jahren ersetzt werden, da durch die häufigen Ladezyklen oder auch durch die langen Standzeiten nicht-regenerative Kapazitätsverluste auftreten. Aber auch die Zuverläs- sigkeit kann nachlassen, falls beispielsweise die Außentemperatur niedrig ist. Dadurch werden die chemischen Reaktionsgeschwindigkeiten innerhalb der Batterie verlangsamt und der Innenwiderstand der Batterie nimmt zu, so dass die für den Antrieb benötigte Arbeitsspannung fällt [Kol86].

Aufgrund der beschriebenen Problematik hat die optimale Ausnutzung der Energie für die Elektromobilität eine größere Bedeutung als für herkömmliche Fahrzeuge. Aus diesem Grund wird die Entwicklung der Batterie dahin gehen, die Energiedichte und somit die Reichweite zu erhöhen und die Kosten zu minimieren.

2.2.2 Reichweitenbeschränkung der Elektrofahrzeuge

Elektrofahrzeuge stellen hinsichtlich der limitierten Reichweiten aktuell keine Alterna- tive zu Fahrzeugen mit Verbrennungsmotoren dar. Hauptgrund dieses Problems ist die speziell für Elektrofahrzeuge unausgereifte Batterietechnologie. Für potentielle Nutzer sind große Reichweiten allerdings ein wichtiger Grund für die Anschaffung eines Elek- trofahrzeugs. Diese Eigenschaft kann zumindest durch den Einsatz von Hochenergie- batterien, wie den Lithium-Ionen-Batterien, teuer erkauft werden¹¹ oder es wird durch die Verwendung der Plug-in Hybrid-Technik versucht, das Problem zu umgehen.

Aber auch andere Faktoren, die bereits in Kapitel 1.1 beispielhaft erwähnt wurden, führen dazu, dass die Angaben über die Reichweite zumindest stark variieren. Dadurch ergeben sich Optimierungsmöglichkeiten, die eine Vergrößerung der Reichweite zur Folge haben.

- Steigungen und Gefälle
- Stadt- und Autobahnfahrten
- Unterschiedliche Fahrgeschwindigkeiten
- Individuelle Fahrweise
- Zusätzliches Gewicht

Um die Reichweite zu maximieren, muss daher jeder der aufgeführten Faktoren für eine energieeffiziente Fahrt miteinbezogen werden. Zur Senkung des Energieverbrauchs sollten beispielsweise hohe Steigungen innerhalb einer Route vermieden werden. Die genaue Analyse einer Strecke hinsichtlich dieser Faktoren kann einem Anwender mitgeteilt werden, so dass eine energieeffiziente Fahrt durchgeführt werden kann.

2.2.3 Ladeinfrastruktur für Elektrofahrzeuge

Traktionsbatterien, die in Elektrofahrzeugen eingesetzt werden, besitzen eine beschränk- te Speicherkapazität und werden bei einer Fahrt entladen. Dadurch ergibt sich die Pro- blematik, wie diese Batterien danach wieder aufgeladen werden sollen. Hierzu existieren verschiedene Lösungsstrategien, um die Mobilität weiterhin zu gewährleisten.

Die übliche Ladevorgehensweise ist die Standardladung durch ein Stromnetz. Dabei wird das Fahrzeug über einen Stromstecker mit dem Netz verbunden und die Batterie 1-phasig und mit 3,7 kW geladen [Sau10], welches auch die batterieschonendste Vari- ante darstellt. In vielen Stadtprojekten werden Ladesäulen mit gängigen Haustroman- schlüssen eingesetzt, die entweder direkt an das örtliche Stromnetz angeschlossen sind oder über Photovoltaik autark Strom erzeugen. Letzteres hat den zusätzlichen Nutzen, dass die Stromgewinnung emissionsfrei ist. Der größte Vorteil ist, dass der Ladevorgang auch im privaten Umfeld, wie in einer Garage mit Stromanschluss, durchgeführt wer- den kann. Daher ist es nur noch nötig, ein weniger enges Netz von Ladestationen als Ergänzung aufzubauen und somit eine solche Infrastruktur günstig zu realisieren. Der Nachteil dieser Technik ist die relativ lange Ladezeit für Elektrofahrzeuge, die bis zu 8 Stunden betragen kann.

Um eine Verkürzung der Ladezeiten zu erreichen, kann eine Schnellladung der Bat- terien genutzt werden. Durch die leistungsorientierte Ladung mit einer Aufladezeit von 5 Minuten kann eine Reichweite von 30 km erzielt werden, was vor allem im Stadtver- kehr einen großen Vorteil darstellt. Dabei wird die Batterie über ein Gleichstromnetz von 30 bis 50 kWh nur teilweise aufgeladen¹². Auch längere Ladezeiten sind möglich, wodurch sich entsprechend die Reichweite erhöht. Nachteilig sind jedoch die hohen An- schaffungskosten dieser Ladesäulen und die erhöhten Kosten von ungefähr 30 bis 50% für das Batteriepackdesign [Sau10]. Dies resultiert aus einem zusätzlichen Kühlsystem für Batterien, das vor der hohen Wärmeentwicklung durch die Starkstromaufladung schützt, und der speziellen Auslegung der einzelnen Batteriezellen für die Schnellla- dung.

Ein anderer Ansatz ist der Aufbau eines Netzes von Batteriewechselstationen in Analogie zu Tankstellen heutiger Zeit. Dabei werden Batterien zu austauschbaren Modulen, die an den Stationen gewechselt werden können¹³. Dadurch entfallen lange Ladezeiten und Fahrzeuge sind sofort wieder betriebsbereit. Der Nachteil sind die immensen Kosten für den Aufbau einer solchen Infrastruktur, wodurch sich auch die benötigte Anzahl an Batterien erhöht, die deswegen in Reserve gehalten werden müssten. Kritisch wären auch saisonale Verkehrsstoßzeiten wie Ferienanfänge, wenn nicht genügend geladene Batterien vorhanden sind.

Allerdings sind Schnellladung und Wechselbatteriekonzepte Ansätze, um den Kunden zu suggerieren, dass ein Elektroauto sich nutzen lässt wie das heuti- ge Fahrzeug mit Verbrennungsmotor, was ö konomisch und ö kologisch nicht sinnvoll ist [Sau10].

Daher wird es in Zukunft wahrscheinlich bei der Variante der Standardladung blei- ben. Eine damit verbundene Umstellung für den Nutzer ist die Folge: Eine auf Elektro- mobilität abgestimmte Planung der Fahrt ist vonnöten. Deswegen ist eine ökonomische Fahrweise und eine energieeffiziente Routenwahl unvermeidlich, um größere Reichweiten realisieren zu können, ohne dabei auf noch teurere Batterien zurückgreifen zu müssen.

2.3 Anforderungen für das energiebasierte Routing

Wegen der Vorteile der Elektrofahrzeuge und des zukunftsträchtigen Markts, werden in der Folgezeit Optimierungen bezüglich dieser Fahrzeuge gefordert. Vor allem die in Kapitel 2.2 beschriebenen Probleme der Elektromobilität zeigen, dass die Planung einer Fahrt einen richtigen Ansatz darstellt. Insbesondere beinhaltet die Planung die Bestimmung jener Route, die für die Batterie am energieschonendsten ist. Wird diese Planung befolgt, kann die Reichweite, die mit der aktuellen Batterietechnologie möglich ist, erweitert werden.

3 Navigation

Heutzutage findet man in vielen Bereichen Verfahren zur Navigation, die die geleite- te Führung zu einem Ziel als Aufgabe hat. Diese Verfahren werden beispielsweise bei Navigationsgeräten für Automobile genutzt und bieten dem Nutzer automatische Rou- tenbeschreibungen und -führungen und somit eine erhebliche Steigerung des Komforts. Es ist zudem möglich, dass eine Route hinsichtlich verschiedener Aspekte optimiert wer- den 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 Ü ber wachung von Bewegungen auf einem vorbestimmten Weg von einem Aus gangspunkt 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ön- nen. 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 Verwen- dung des Global Positioning System (GPS), eines amerikanischen, satellitenge- stützten Ortungssystems [GPS06]. Ähnliche Systeme stellen das russische Projekt GLONASS oder das europäische System Galileo [DH10] 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 [HVC+08]. 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 wer- den, die den Weg zum Ziel beschreibt. Die Voraussetzungen für die Berechnung einer Route sind zum einen das Vorliegen einer Landkarte mit Streckenbeschrei- bungen, 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 die- se 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 kontinu- ierlichen 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 Tei- laufgaben bei der Navigation in der Schifffahrt ausreichend waren, erfüllen Navigati- onsgerä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 Na- vigation. Da man durch Satelliten- oder Funktechnik schon sehr präzise Positionsanga- ben 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 op- timalen Pfad von einem Startknoten (Quelle) zu einem Zielknoten (Senke) in einem Graphen, was somit eine mögliche Herangehensweise zur Lösung eines Routings dar- stellt. 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.

3.2.1 Routingstrategien für treibstoffbetriebene Kraftfahrzeuge

Für Kraftfahrzeuge mit Verbrennungsmotoren gibt es verschiedene Routingstrategien, die sich darin unterscheiden, welche Aspekte für die Berechnung einer Route relevant sind. Die üblichen, von Navigationsgeräten unterstützten Modi werden im Folgenden beschrieben. Die Verschiedenartigkeit drückt sich dann in der Implementierung der Kostenfunktion und der resultierenden Metrik aus.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.1: Straßenkarte mit Bewertung der Teilabschnitte

Kürzeste Route In diesem Modus wird ausschließlich die Wegdistanz als Metrik ver- wendet. Für eine Strecke n mit der Länge l (n) ergeben sich dann die Kosten

Abbildung in dieser Leseprobe nicht enthalten

Der einzige Vorteil ist, dass die kürzeste Route ausgegeben wird. Nur in den wenigsten Fällen ist die gewählte Route auch zu empfehlen. Dies liegt daran, dass beispielsweise weglängenbezogene Abkürzungen über Feldwege oder Wohngebiete priorisiert werden oder Landstraßen anstelle von Autobahnen vorgeschlagen werden, weil dadurch eine kleinere Weglänge garantiert wird. Folglich geht dies aber zu Lasten der Fahrzeit und des Reisekomforts.

Schnellste Route Ist die schnellste Route gewünscht, versucht man die Fahrzeit zu mi- nimieren. Dafür müssen zusätzlich zur Weglänge l (n) die zulässige oder empfoh- lene Höchstgeschwindigkeit v (n) in die Metrik aufgenommen werden. Die Kosten einer Strecke ergeben sich dann aus dem Quotienten

Abbildung in dieser Leseprobe nicht enthalten

Diese Option wird häufig in Navigationsgeräten und bei Routenplanern genutzt, da viele Nutzer von treibstoffbetriebenen Kraftfahrzeugen ihre Priorität auf eine geringe Fahrzeit legen. Kosten für den Treibstoff werden nicht miteinbezogen, da in dieser Nutzergruppe der Faktor noch nicht als kritisch erachtet wird. Es ist jedoch anzunehmen, dass in naher Zukunft der Energieverbrauch eine wichtige Komponente bilden wird (vgl. Kapitel 2.1).

„Schönste“ Route Eine solche Strategie beinhaltet das Ausschließen von Autobahnen. Die Folge für den Nutzer ist, dass unattraktive Autobahnstrecken für ruhige Land- straßen in der Route weichen müssen. Zudem kann diese Option einfach dazu genutzt werden, Strecken mit Mautgebühren zu umgehen. Eine Kostenfunktion könnte dabei wie folgt aussehen.

Abbildung in dieser Leseprobe nicht enthalten

Des Weiteren kann die Route so abgeändert werden, dass Sehenswürdigkeiten (Point of Interest) als Zwischenziele eingefügt werden, um die Attraktivität der Route zu erhöhen².

Ökonomischste Route Mit dieser Strategie wird versucht, eine sparsame Route zu fin- den, was der Minimierung des Verbrauchs entspricht. Die Metrik, die aufzustellen ist, ist nicht mehr trivial, da der Energieverbrauch von mehreren Faktoren abhän- gig ist. Zusammenfassend können die Kosten aus dem Produkt vom durchschnittli- chen Treibstoffverbrauch e und der Weglänge berechnet werden. Der durchschnitt- liche Verbrauch hängt hauptsächlich von der gefahrenen Geschwindigkeit ab. All- gemein sind 60-80 km/h die optimale Geschwindigkeit für einen geringen Treib- stoffverbrauch bei gewöhnlichen Kraftfahrzeugen mit Verbrennungsmotoren³ (vgl. Abbildung 3.2).

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.2: Streckenspezifischer Verbrauch in Abhängigkeit der Geschwindigkeit

Aber auch Stadt- oder Autobahnfahrten müssen unterschieden werden: In Städten

[...]

---

¹ http://www.smart.de/

² http://www.navigon.com/

³ http://www.tomtom.com/

⁴ http://wiki.openstreetmap.org/wiki/

¹ „E-mobility Berlin“ ist ein Kooperationsprojekt zwischen Daimler AG und RWE AG

² Die smartlab GmbH ist ein Gemeinschaftsunternehmen der Stadtwerke Aachen Aktiengesellschaft, der Duisburger Verkehrs- und Versorgungsgesellschaft und der Stadtwerke Osnabrück AG.

³ Opel wird das Plug-in Hybrid-Fahrzeug Ampera voraussichtlich im vierten Quartal 2011 ausliefern. Die integrierte Batterie besitzt eine Leistung von 16 kWh.

⁴ Angenommen wurde eine Strecke von 90 km.

⁵ http://www.deutschebahn.com/site/bahn/de/konzern/im__blickpunkt/call__a__bike.html

⁶ http://www.sixtblog.de/allgemein/sixt-bietet-fahrspass-auch-mit-zwei-gaspedalen/

⁷ http://www.e-max-roller.de/110.html

⁸ je nach Hersteller und Modell sind es 10 bis 70 Eurocent pro 100 km

⁹ http://www.ecofriend.org/entry/el-assist-recharging-concept-lets-electric-vehicles-recharge-on-the- move/

¹⁰ Dieser Wert ist noch nicht bekannt.

¹¹ Das Elektroauto Tesla Roadster von Tesla Motors erzielt eine Reichweite von unter 300 km bei einem Anschaffungspreis von 98.000 US-$.

¹² http://www.inka-emobility.de

¹³ http://www.betterplace.com/the-solution-switch-stations

¹ Bibliographisches Institut F.A. Brockhaus, Mannheim

² http://www.garminonline.de/extras/poi

³ http://www.verkehrswissenschaftler.de/berichte/bericht_2.htm