Wie funktioniert eigentlich Routenberechnung
Guntram Ulrich
ich hab hier einen Ipaq mit dem Navman 3000. Wenn ich eine Route berechne
wird eine gewisse Zeit lang angezeigt das da irgendwelche Strassen
analysiert werden und das für die Restanalyse noch eine gewisse Anzahl
Kilometer verbleiben.
Mich würd jetzt mal als mit null Vorwissen interessieren was da eigentlich
grundsätzlich passiert.
Kann mir vielleicht jemand einen guten Einstieg oder Link dazu nennen, der
das mal Grundsätzlich abhandelt?
Schönen Dank im voraus.
Gruß
Guntram
Ralf Schoenfeld
Hallo Guntram,
diese ganze Routenberechnung bei den diversen Routenplanern/
Fzg-Navigationssystemen ist ziemlich komplex, und basiert auf
Vektorkarten (prinzipiell mal egal, ob jetzt 20 DM Routenplaner von
Billig-Lebensmittelkette, oder 4000 DM Navi von Edel-Limousine).
Diese Vektorkarten sind eigentlich "nur" Datenbanken, die aus vielen
einzelnen Punkten bestehen, denen zusätzlich Attribute und
Informationen zugewiesen sind (z.B. welche Art Straße (Feldweg,
Landstraße, Autobahn ?), welche Geschwindigkeitskategorie, Kreuzung,
Einbahnstraße, Straßenname, Hausnummer, u.v.m.). Die einzelnen Punkte
werden dann durch Linien miteinander verbunden.
Aus allen diesen Daten muß dann erst die Route berechnet werden, und
auch so Angaben wie Routenlänge, Fahrdauer, Kraftstoffverbrauch etc.
Basis ist auf jeden Fall diese Datenbank. Entscheidet ist dann, wie
aktuell diese Daten sind und wie umfassend (Anzahl der Punkte, der
Attribute, Zusatzinfos, etc.).
Die Güte des auswertenden Softwareprogramms spielt natürlich auch noch
ne Rolle.
Aber hier nochmal im Einzelnen (Auszug aus
http://home.arcor.de/canadier+gps-info/d-gpsundkanu3.htm):
Was steckt hinter Vektorkarten ? - Grundsätzliches
Vektorkarten sind nicht einfach nur gescannte Straßenkarten, sondern
um eine navigationstaugliche, für den Computer les- und
interpretierbare Karte zu erhalten, muß jede Strasse in Vektordaten
aufgeteilt und mit allerlei Zusatzinformationen versehen werden (z.B.
Straßennamen, Hausnummern und so genannten Attributen).
Aus diesem Grund werden Vektorkarten erst beim Betrachten gezeichnet,
und nicht schon bei der Erstellung. Sie sind also nicht starr, sondern
passen sich den Bedürfnissen des Anwenders an.
Es kann beispielsweise bestimmt werden, welche Informationen
gezeichnet werden sollen und wie viele. Die Anzahl der gezeigten
Informationen ist in der Regel zoom-abhängig. Je weiter in die Karte
hineingezoomt wird, umso mehr Details werden dargestellt.
Mit Hilfe von bestehenden Karten, Satellitenbildern, Luftaufnahmen und
direkt vor Ort, erstellen die Mitarbeiter der Kartenhersteller vom
Straßennetz ein Gebilde aus Punkten, die über Linien miteinander
verbunden werden, die Vektorkarte.
Jeder Punkt stellt dabei ein für die Navigation relevantes Ereignis
dar, wie eine Kreuzung, der Beginn einer Auf-/ Abfahrt usw.
Um diese Daten für die Kartendatenbank zu sammeln, gehen die
Mitarbeiter vor Ort in mühsamer Handarbeit Straße um Straße, Kreuzung
um Kreuzung durch.
Die beiden großen Hersteller solcher Vektorkarten sind Tele Atlas und
Nav-Tech.
Sie bedienen praktisch den gesamten europäischen Automobilmarkt für
deren Navigationssysteme, und auch die diversen Hersteller von
Routenplanern für den PC.
Neben der möglichst kompletten Abdeckung des Straßennetzes steht und
fällt eine Navigationskarten-Software mit den Attributen.
Sie sorgen dafür, daß die Fahrzeugnavigation ohne Verstöße gegen die
Straßenverkehrsordnung über den richtigen Weg ans Ziel führt.
Diese Attribute definieren zum Beispiel, ob eine Straße in beide
Richtungen befahrbar ist, welche Fahrtrichtung eine Einbahnstraße hat,
die Anzahl der Fahrspuren, ob die Richtungsspuren baulich oder über
Markierungen voneinander getrennt sind, ob über die andere Fahrspur in
eine Straße abgebogen werden darf, wer eine Straße befahren darf
(Anwohner, Zulieferer, zeitl. Beschränkungen, Fuß- oder Radweg usw.).
Weitere Attribute definieren die Wichtigkeit der Straße, was für die
Routenwahl (kürzeste/ schnellste Strecke) wesentlich ist.
Bei Nav-Tech geschieht dies beispielsweise in 5 Stufen (höchste Stufe
ist die Autobahn).
Weiterhin werden alle Straßen in Geschwindigkeitsbereiche eingeteilt,
was bei der Navigation dazu dient, eine voraussichtliche Ankunftszeit
am Ziel zu errechnen.
Nav-Tech hat beispielsweise dazu 8 Tempobereiche definiert. Der
kleinste steht für Geschwindigkeiten unter 11 km/h, also für Feldwege
oder engste Wohnstraßen, und der höchste definiert Geschwindigkeiten
über 130 km/h, wie z.B. auf der deutschen Autobahn.
Dazu kommen dann noch Maut-Zahlstellen an Autobahnen, Tunnels oder
Brücken, welche ebenfalls der Routenwahl dienen (Auswahl: mit/ ohne
Maut) und viele weiter Attribute mehr.
Die Hersteller der Kartensoftware liefern mit ihrer Datenbank
allerdings lediglich die Grundlagen.
Was letztendlich einem Autofahrer mit seinem Navigationsgerät oder dem
PC-Anwender mit seinem Routenplaner vorgesetzt wird, entscheidet der
Gerätehersteller bzw. die Softwarefirma des Routenplaners.
Diese definieren, nach welchen Algorithmen die Navigation erfolgen
soll.
So verlangen z.B. einige Geräte nach einem falschen Fahrmanöver "wenn
möglich bitte wenden", während andere annehmen, daß aus einem
bestimmten Grund nicht die vom Gerät vorgegebene Route gewählt wurde
(betrifft jetzt preiswerte Routenplaner natürlich nicht).
Sie führen deshalb in einer Schleife auf die ursprüngliche Route
zurück.
Weitere Algorithmen bestimmter Hersteller sind darauf ausgelegt,
möglichst wenig Manöver vorzugeben, die das Fahrzeug über den
Gegenverkehr führen (bzw. links abbiegen), da derartige Manöver ein
höheres Unfallpotential bergen.
Auch bei den immer zahlreicher werdenden Sonderzielen (POI’s; =
Points of Interest), wie Hotels, Attraktionen, Tankstellen, Bahnhöfen,
Flughäfen usw., bestimmt jeder Hersteller selbst, welche Daten er aus
dem immensen Datenpool zur Verfügung stellen möchte.
Gruß
Ralf
http://kanadier.gps-info.de/
Guntram Ulrich
Das hat mir schonmal sehr gut auf die Sprünge geholfen.
Was mich jetzt allerdings noch genauer interessiert ist, wie tatsächlich
eine gangbare Route über dieses Vektornetz gefunden wird. Es können ja nicht
alle möglichen Kombinationen in alle möglichen Richtungen abgegangen werden
um zu sehen ob man zufällig auf das Ziel stößt.
Aber trotzdem hat mir diese Einführung und deine Webseite schon sehr sehr
viel gebracht.
Schönen Gruß
Guntram
"Ralf Schoenfeld" <ralf.sc...@web.de> schrieb im Newsbeitrag
news:d937263f.02010...@posting.google.com...
Uwe Schneider
> Das hat mir schonmal sehr gut auf die Sprünge geholfen.
>
> Was mich jetzt allerdings noch genauer interessiert ist, wie tatsächlich
> eine gangbare Route über dieses Vektornetz gefunden wird. Es können ja
nicht
> alle möglichen Kombinationen in alle möglichen Richtungen abgegangen
werden
> um zu sehen ob man zufällig auf das Ziel stößt.
http://www.google.de/search?hl=de&q=traveling+salesman&meta=lr%3Dlang_de
Das ist das sogenannte Traveling-Salesman-Problem (TSP), auch als
Rundreiseproblem bezeichnet.
Es gibt wohl immer noch keine optimale mathemat. Lösung für dieses Problem.
Daher ist es immer sehr Herstellerabhängig.
Auch muss man die zu bevorzugenden Strassen angeben also Autobahnen vor
Bundesstrassen oder andersrum bzw. kürzeste oder schnelleste Strecke.
Das beste Programm was ich je hatte, war ein DOS-Programm, so um 1993 muss
das gewesen sein.
Das hies damals wo Autoroute !? Was es jemand genau und kann mir sagen werd
der Hersteller war und wo man es herbekommen kann ?
Heute hat MS ein Programm namens Autorout. Ich weiss aber nicht ob die was
miteinander zu tun haben.
ciao
Carsten Kurz
> Was mich jetzt allerdings noch genauer interessiert ist, wie tatsächlich
> eine gangbare Route über dieses Vektornetz gefunden wird. Es können ja nicht
> alle möglichen Kombinationen in alle möglichen Richtungen abgegangen werden
> um zu sehen ob man zufällig auf das Ziel stößt.
Dahinter stecken relativ komplizierte Verfahren, die aber in grundlegenden
mathematischen Lösungen münden, die in der Regel schon vor langer Zeit
erarbeitet wurden. Die Hersteller können da noch ein bißchen optimieren, je
nachdem, was an Ressourcen auf dem Rechner zu Verfügung steht. Ähnliche
Verfahren gibts z.B. für die automatische Entflechtung von elektronischen
Leiterplatten.
Ein simpler Ansatz wäre z.B. vom aktuellen Standort erstmal die Straße/den
Vektorzug zu nehmen, der am ehesten in die Zielrichtung weist. Das ist noch noch
ganz einfache Vektorgeometrie. Von jedem Kreuzungspunkt aus macht man das dann
wieder erneut. Das kann man so oft und für soviele Start-Straßen/Richtungen
wiederholen, bis es zu einer Abbruchbedingung kommt - Zeit, Weglänge, Wegzeit,
ungeeignete Straßen, etc. pp. Typischerweise ermittelt die Software mehrere
mögliche Wege zum Ziel, notiert dabei die damit verbundenen Routing-Kriterien,
und verwirft nach Abschluss des Durchlaufes die mit den ungünstigeren
Resultaten.
Das Ganze wird dann eben noch erweitert mit Zusatzinfos über mögliche
Geschwindigkeiten, Optimierung Weg/Zeit/Kosten, was weiß ich.
Daß das nicht in Sekundenbruchteilen geht, sieht man, wenn man so eine
Routenberechnung mal auf einem PDA startet. Das kann schonmal ein paar Minuten
dauern.
Ciao - Carsten
--
Audio Visual Systems fon: +49 (0)2238 967926
Carsten Kurz fax: +49 (0)2238 967925
Fasanenweg 38a email: audio...@t-online.de
50259 Pulheim / Germany WGS84:N50°58'44.7" E06°47'03.5"
Gilles Kohl [MVP]
On Wed, 2 Jan 2002 17:32:23 +0100, "Uwe Schneider"
<dieses_loe...@yahoo.de> wrote:
>Das beste Programm was ich je hatte, war ein DOS-Programm, so um 1993 muss
>das gewesen sein.
>
>Das hies damals wo Autoroute !? Was es jemand genau und kann mir sagen werd
>der Hersteller war und wo man es herbekommen kann ?
>
>Heute hat MS ein Programm namens Autorout. Ich weiss aber nicht ob die was
>miteinander zu tun haben.
MS hat soweit ich weiss damals (1995) die Firma NextBase gekauft - so
gesehen ist AutoRoute 2002 ist der Nachfolger des damaligen
DOS-Programms. Wieviel vom ursprünglichen DOS-Code noch übrig ist
vermag ich allerdings nicht zu sagen :-)
Viele Grüße,
Gilles.
Gunter A.
news:a0vclo$nfjsc$1...@ID-87149.news.dfncis.de...
[..]>
> Das ist das sogenannte Traveling-Salesman-Problem (TSP), auch als
> Rundreiseproblem bezeichnet.
>
> Es gibt wohl immer noch keine optimale mathemat. Lösung für dieses
Problem.
Stimmt. Wird erst mit Quanten-Computern allg. optimal zu lösen sein.
Im Prinzip geht es daher immer so:
- Jeder Kante wird eine Wertigkeit zugewiesen (Wegkosten)
- Es gibt einen Ursprungs-/ und Zielknoten.
- Mehr oder weniger intelligent wird nun vom Ursprungsknoten aus zum
Zielknoten gegangen.
- Die Wegkosten sind das wichtigste Kriterium
- Oft kommen noch sog. heuristische Verfahren zum Zuge (man versucht dem
Verfahren "Erfahrung"/"Vorwissen" mitzugeben, um so schnell und "optimal"
eine Lösung zu finden.
Gruß Gunter
P.S.: Die Verfahren sind nicht so schwierig wie es klingt, für das Prinzip
programmiert man 3-4 Zeilen Code.
Uwe Schneider
> P.S.: Die Verfahren sind nicht so schwierig wie es klingt, für das Prinzip
> programmiert man 3-4 Zeilen Code.
Mehr nicht ?
Bist du Mathematiker oder machst Du ganz und gar Routenberechnungssoftware ?
Ich kenne nämlich ein Firma, die damit Probleme hat.
ciao
HaDE-Germany
Du hast ganz recht alles fing mit CAD an und die Funktionen wurden für
Konturenverfolgung und Maschinenwege im CAM und für die
Leiterplatten-Entflechtung (Routing) benötigt. Das sind/waren alles
Vektor-Daten, (heute eher 3D-Modeling-daten).
So kompliziert und Schwierig ist es nicht, nur sehr viel zu rechnen (viele
Wege füren nach Rome, auch über China) Es ist Abhängig davon wie optimal ich
es haben will und wie genau die Attribute einer Polyline ( Polyline=
anneinander gereihte Vectoren zB. Autobahn, Landstr., Fluss, etc.)
zugeordnet sind z.B.:Strassentype; Geschwindigkeit, Verkehrsdichte ,
Einbahnstrasse, etc. und wie genau diese berücksichtigt werden bei der
Optimierung. Die Software macht es auch nicht anders ( vereinfacht
ausgedrückt)
wie wir mit dem Finger auf einer unbekannten Karte wo wir Durchmüssen)
HaDe
"Carsten Kurz" <audio...@t-online.de> schrieb im Newsbeitrag
news:3C333FA9...@t-online.de...