Routenplaner programmieren

B

bfsdasauge

Erfahrenes Mitglied
Hallo zusammen,

weiß jemand, nach welchem Verfahren herkömmliche Routenplaner arbeiten? Gibt es da irgendwelche mathematischen Tricks?

Bislang bin ich davon ausgegangen, das man das ganze geometrisch lösen kann. D.h. jeder Ort erhält eine eindeutige Koordinatenzuweisung. Zudem wird in einer Datenbank jede Ort-Ort Verbindung als Vektor hinterlegt.

Wenn man nun eine Routenanfrage stellt, errechnet das Programm zuerst den Vektor (A->B) und versucht dann anhand der Verbindungsinformationen über die Richtung der einzelnen Verbindungsvektoren verschiedene mögliche Strecken zu finden.
Konkret würde das heißen, er versucht sich von Ort zu Ort durchzuhangeln, und verwendet dabei die Verbindung, deren Vektor dem der gesuchten Strecke (A->B) am ähnlichsten ist (Winkel). Zudem wird der Vektor der gesuchten Strecke permanent neu berechnet. Quasi nach jedem Erreichen eines neuen Ortes.

Das ganze funktioniert aber nur stark eingeschränkt, weil bei langen Strecken eine totale Unschärfe reinkommt. Das liegt vorallem daran, daß bei jeder Entscheidung welche Verbindung nun die beste ist, immer nur das Detail betrachtet wird und nicht die gesamte Anfrage.
Da verennt sich das System z.B. in Sackgassen, oder es rechnet im Kreis.

Wie also lässt sich das Problem lösen?

Gruß
 
hmm,

das ist so eine Art Traveling Salesman Problem.

guck dir mal dieses Dokument an =>

http://www.informatik.uni-leipzig.de/~meiler/Schuelerseiten.dir/TBlaszkiewitz/TBlaszkiewitz.pdf

Ich denek so gehen auch die Routenplaner vor, sie haben immer die Strecken zwischen 2 Punkten gespeichert und verbinden diese 'unterstrecken' zu einer Gesamtstrecke. Dabei wird der Rechner so ähnlich vorgehen wie von dir schon beschrieben. Wir nehmen erstmal alle Punkte die auf der geraden strecke liegen und verbinden die via Unterpunkten bis die beste 'Strecke' gefunden ist.
 
Aufgrund der Komplexität der Routenplanung würde ich das Einsatzgebiet minimieren.

Also, du musst eigentlich damit rechnen, Graphen zu benutzen. Am besten fängst du mit ungerichteten Graphen an. Das sind Graphen, wo die Punkte einfach verbunden sind, ohne irgendwelche Richtung (das käme bei dir später).

Versuche erstmal, einen Graphen aufzubauen und dann kümmere dich darum, erstmal irgendeinen Algorithmus selber zu schreiben, der die Äste (wege) bist zu deinem Endpunkt findet. Dann kannst du daran gehen und einen populären Weg-such-alg. einzuprogrammieren.

Nimm 6 Punkte, die irgendwie verbunden sind und errechne den Weg.

BTW: ist das eine Idee von dir oder brauchst du das irgendwie irgendwo? Dann kann man dir spezifisch helfen.

Grüße
Christian Behrenberg
 
Zu diesem Thema kann ich allen Interessierten ein Buch empfehlen das wir in der Schule durchgenommen haben: Das Geheimnis des kürzesten Weges

Dort wird dieses Thema ausführlich diskutiert und in eine hübsche Geschichte verpackt (die vielleicht ein bisschen zu sehr auf ein junges Publikum zielt, aber daran darf man sich nicht stören). Die Erläuterungen sind äussert anschaulich und die Algorithmen werden plattformunabhängig erklärt, eine Implementierung muss man schon selbst vornehmen.
 
Hi,

will auch mal meine Senf dazugeben :)
Das ist schon ein ziemlich komplexes Thema mit der Routenplanung und den Algorithmen dazu. Beschäftigen uns im Studium schon seit längere Zeit damit.
Da gibt es ganze Diplomarbeiten drüber, aber wirklich neue Ansatzpunkte kommen da nicht bei raus.

Hab nun auch nochmal ne allgemeine Frage in die Runde:

Es soll das Straßennetz der USA zum öffentliche Download bereitstehen. Da ich gerade dabei bin in Delphi Straßennetze zunächst grafisch darzustellen, wären paar vernünftige Koordinaten ganz sinnvoll.

Kennt da jemand einen Link zu dem Straßennetz Download? Bei google finde ich so nix.

Gruß

Flens
 
Re: hmm,

hallo zusammen, ist meine Aufgabe auch gehoerte zu TSP ?

Thema: "Statistische Auswertung von Datensaetzen ueber personengebundene Routenplanung"

das touristische Assistensystem zielt darauf ab, die unabhaengige mobilitaet von touristen mit und ohne handicap in nicht vertrauten

umgebungen zu erhoehen, idem es nuetzliche informationen vor und waehrend einer wanderung zur verfuegung stellt. im vorfeld ist eine routenplanung vonnoeten, die auf die persoenlichen faehigkeiten des touriesten angestimmt ist. das beutet, dass wegstuecke die aufgrund ihrer beschaffenheit zur barriere werden, umgangen werden muessen. infolgedessen,werden moegliche ziele einer routenplanung eventuell schwerer oder sogar unerreichbar
ziel ist es, eine software zur verfuegung zu stellen, die auf grundlage gespeicherter daten ueber routenplanungen und deren ergebnisse, eine statistische auswertung vornimmt. interessante, abrufbare ergebnisse koennten z.B. folgende informationen sein:
---->wie oft und fuer wen ist ein bestimmter abschnitt zur Barriere geworden
---->welche Barreiren erschweren oder verhindern das erreichen eines interessanten punktes
---->welche Ziele werden bevorzugt angefragt
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück