Ich bastle gerade an meinem Fahrradouting von Osmand und Brouter herum. Dabei ist mir aufgefallen, je mehr ich versuche Hauptstraßen zu vermeiden, desto langsamer wird das Routing. Noch extremer wird es, wenn ich auch die Straßen von Wohngebieten abwerte. Sobald ich aber den Hauptstraßen die höchste Priorität einräume, wird das Routing wieder schnell.
Da alle relevanten Straßen zwischen 15 und 18 km/h bei meinen Berechnungen schwanken, würde mich interessieren, warum das so ist? In bestimmten Gegenden würde ich das Phänomen verstehen, aber nicht hier in der südhessischen Rhein-Main-Ebene, in der es ein dichtes Wegnetz von guten Forstwirtschaftswegen gibt. Es ist ja nicht so, dass es keine Alternativen zu den Hauptstraßen gäbe.
Dann ist das völlig normal. Die Routenberechnung ist sehr teuer. Je größer die Distanz ist, desto mehr Wege müssen berücksichtigt werden (selbst bei einem A*-Algorithmus mit guter Heuristik). Der Trick: Je nach Entfernung routet man erstmal von kleinen auf größere Wege, dann wieder größere und in der Nähe des Ziels genau anders herum. Wenn du von Hamburg nach München fährst, ist es also sehr wahrscheinlich, dass du die meiste Zeit über eine Autobahn fährst, obwohl es über Landstraßen und Feldwege direkter wäre.
Erstmal Danke. Ganz sicher bin ich mir aber nicht, ob ich es verstehe.
Also es läuft in einem Routingalgorithmus alles auf die Autobahn zu, mit der fräst man sich schnell durch die Landschaft, um dann sich wieder in den Gassen des Ziels zu verlieren. So weit logisch.
Es wird bei diesen Berechnungen die gängige Hierarchie von Straßen zugrunde gelegt.
Jetzt kommt das Aber, was mich zweifeln lässt, ob ich das richtig verstanden habe.
Dem Router und damit dem Algorithmus kann ich aber angeben, was für Straßen ich besonders gerne mag. Also bei meinen Fahrradroutings sage ich dem Router, ich mag Feldwege deutlich lieber als eine Bundesstraße. Der Geschwindigkeitsunterschied ist auch nicht so hoch und trotzdem wird erst zur Bundesstraße hin gerechnet, um dann doch herauszufinden, dass der Weg neben der Bundesstraße nach meinen Vorgaben der bessere ist. Dann wäre es doch vernünftiger, entsprechend der Priorisierung auch die Straßen zu ändern, auf die als erstes hin gerechnet wird. Also bei einem personalisierten Routing wäre es dann unter Umständen der Feldweg.
Das bedeutet doch, je mehr meine Priorisierung der Straßen der gängigen Straßenhierarchie widerspricht, desto mehr bremse ich den Algorithmus aus und er wird sehr träge, weil der Algorithmus in igendeiner seiner Ecken eine seiner Hierarchien nicht meiner Priorisierung anpasst?
Also wenn Feldweg Priorität=1, Bundesstraße=0,6, dann hat in irgendeinem Teil des Algorithmuses die Bundesstraße weiterhin eine Priorität von 1 und der Feldweg 0,4?
- The profile should be able to find a route with an average costfactor
not very much larger than one, because otherwise the routing algorithm
will not find a reasonable cost-cutoff, leading to a very large
search area and thus to long processing times.
Entscheidend ist die “Spreizung” der Kostenfunktion, also das Verhältnis aus Kosten/Luftlinie. Bei gleicher Spreizung solltest Du auch gleich grosse Suchgebiete und damit gleiche Berechnungszeiten haben.
Die Spieizung kann auch “aus Versehen” gross werden, wenn Du einfach alle Kosten verdoppelt hast und es den Kostenfaktor 1 garnicht mehr gibt. Es sollte immer so sein, dass das, was Du suchst (und auch finden kannst) den Kostenfaktor 1 hat.
Das Problem ist die große Anzahl von Wegen. Ich habe hier eine anschauliche Grafik, die ich aus urheberrechtlichen Gründen nicht veröffentlichen darf, aber ich schreibe dir mal eine PN.
Spreizung ist nicht so einfach zu fassen wie es der Laie gerne hätte? Größter Kostenfaktor - kleinster Kostenfaktor?
Wegen deiner Erklärungen habe ich ein kleines Experiment gemacht. Ich habe Südhessen mit Overpass-API die highway verglichen.
200MB type:way and highway=*
30MB type:way and (tracktype=grade4 or tracktype=grade5 or highway=path)
20MB type:way and (highway=primary|secondary|tertiary|primary_link|secondary_link|tertiary_link)
Alle Wege in Brouter auf 1 gesetzt. Frankfurt Bensheim 27 Sekunden.
highway=primary|secondary|tertiary|primary_link|secondary_link|tertiary_link auf 5 gesetzt. 36 Sekunden
Die Erwartung wegen deiner Aussagen war, wenn ich highway=primary|secondary|tertiary|primary_link|secondary_link|tertiary_link** zurück auf 1** setzte und tracktype=grade4 or tracktype=grade5 or highway=path auf 5 setzte müsste die Berechnung länger dauern, weil ich dem System mehr Wege klaue. Aber zu meiner Überraschung die Berechnung dauert nur 29 Sekunden.
Die Breite dieser Ellipse und die Ausdehnung nach hinten steigt mit der Spreizung der Kostenfunktion. Und nur diese Fläche zählt für die Rechenzeit, weil Du musst davon ausgehen, dass innerhalb dieser Fläche ohnehin jeder Weg gerechnet wird, auch die mit Kostenfaktor=5
Wenn die Spreizung gross wird heisst das, die A-Stern Heuristik funktioniert nicht mehr und das Suchgebiet nähert sich dem grossen Kreis.
Das ist eigentlich keine schlechte Syntax, um ver-oderte Lookup-Matches in die Profile zu schreiben. Ich hab’s in den Parser eingebaut.
Danke. Ich habe mir mal den Wikipediaartikel zum A*-Algorithmus und eine dort verlinkte Demonstration angesehen. Irgendwie fehlt mir immer noch die Antwort darauf, warum das Verteuern von Hauptstraßen so eine vehemente Wirkung hat verglichen zum Verteuern der schlechten Feldwege, die datenmäßig mehr sind.
Bloß wen ich mir die Grafiken der Demonstrationen so ansehe, könnte es daran liegen, dass die Kanten der Hauptstraßen tendenziell länger sind als die der Feldwege?
Wenn es dir um Nutzbarkeit geht, hätte ich da einen Vorschlag für dich. Ich habe mal vor mehr als 30 Jahren an irgendwelchen Commodorerechnern ein wenig Basic gelernt. Seitdem bin ich bei jeder Programmiersprache auf if und else gestoßen. Du arbeitest mit switch. Das war eigentlich das erste Mal, dass ich fragen musste, was bedeutet diese Syntax. Langer Rede kurzer Sinn, vielleicht wird die Personalisierung für mehr zugänglich, wenn Du auf if und else umstellen würdest. Oder überlege dir, wie selbsterschließend deine Syntax für jemanden ist, der geringe Kenntnisse bis gar keine von Programmiersprachen hat, aber einigermaßen logisch denken kann.
und speziell das Kapitel 5.6 über A-Stern bi-direktional und mir dann sagen, ob dessen Behauptung stimmt, dass man mit A-Stern bi-direktional das Suchgebiet nicht halbieren kann gegenüber dem uni-direktionalen Ansatz.
Hab ich. Ich denke immer noch, dass das Bild so nicht stimmt. Beim ersten gefundenen Pfad von Start zum Ziel kann man das Gebiet eingrenzen. Punkte mit einer Summe der Luftlinienlängen zu Start und Ziel, die größer als die Länge des gefundenen Weges ist, können keine Rolle mehr spielen. Diese Bedingung gibt aber genau eine Ellipse mit den Brennpunkten Start und Ziel an.
Puh! Kann ich nicht sagen:
Die Halbierung beim Dijkstra-Algorithmus ergibt sich ja daraus, dass die beiden Kreise um Start und Ziel gleichmäßig wachsen und man bei der Begegnung der beiden nur noch eine kleine Komplettierung berechnen muss. Die Fläche (also der Aufwand) ist halb so groß, als wenn man den Kreis um Start wachsen lassen würde bis er auf das Ziel trifft. Am Punkt der Begegnung kann man deshalb (im Prinzip) aufhören, weil ja zu jedem Zeitpunkt alle kürzesten bisherigen Wege einkalkuliert wurden.
Beim A* werden aber erfolgversprechende Wege gegenüber kurzen Wegen bevorzugt. Deshalb kann es bei der Begegnung auf beiden Seiten noch nicht berechnete Abkürzungen geben und man ist nicht mal im Prinzip fertig. Andererseits ist es bei A* viel wahrscheinlicher als bei Dijkstra, dass man die vorher ermittelten Ergebnisse brauchen kann…
Wobei ich gerade eine Entdeckung mache. Osmand ist bei der bidirektionalen Suche mal schneller mal deutlich langsamer als die Suche in nur eine Richtung. Das Autorouting ist bidirektional schneller, aber mein Fahrradrouting ist mit unidirektional schneller.
Wenn die Kanten alle gleich gewichtet werden, dann ist die Seite hinter dem Ziel sehr eng. Je höher die Differenz in der Gewichtung der einzelnen Kanten, desto dicker wird der Bereich hinter dem Ziel.
Ich habe mir die Sache mal im OsmandMapCreator angesehen. Die Spreizung erzeugt teilweise Suchgebiete, von deren ich bei einer langen Strecke mich frage: Ist das sinnvoll dort überhaupt zu suchen? Wie hoch ist die Wahrscheinlichkeit, dass sich ein Weg der über dieses Gebiet führt, überhaupt rauskommt?
Also vielleicht wäre es sinnvoll, die Suchräume zu begrenzen. Entweder durch den Nutzer oder dass je nach Spreizung, Entfernung von der Luftlinie der Wegpunkte die Knoten/Kanten eine entsprechende Wertung erhalten.
Bei meinen Experimenten war ich überrascht, wie weit man den Suchraum ausdehnen muss. Wenn man für 100 Meter Luftlinie nur im 1km-Umkreis sucht, scheitert man z.B. an Flüssen, die nur alle 5km eine Brücke haben. Oder wenn man von einem Talende zum Nachbartal möchte…
Wenn die verwendete Heuristikfunktion falsch ist (also deutlich kleinere Kosten liefert als realistisch erreicht werden können), dann muss man nicht zu basteln anfangen, sondern die Heuristik-Funktion in Ordnung bringen.
Wenn Du Dir die BRouter-Profile anschaust, dann haben die alle eine “Soll-Lösung” mit exakt Kostenfaktor 1. Bei “trekking” sind das Fernradwege, bei “fastbike” sind das tertiary Highways und bei “car-test” sind das Autobahnen. Und natürlich gibt es die und kann man die finden. Und wenn Du an einem Fluss erst mal 3km zurückfahren musst zur Brücke, die Dich auf den Fernradweg auf der anderen Seite bringt, dann ist das genau dieser scheinbar sinnlose Grenzfall. Ist aber nicht sinnlos, sondern gehört notwendig zum Suchgebiet.
Was Du da an Heuristiken und anderen Taschenspielertricks in den Ring wirfst ist exakt das, was sie bei OsmAnd seit Jahren unter “heurstic coefficient” und so weiter diskutieren, mit den bekannten Ergebnissen.
Das Du die Leute von Osmand nicht schätzt ist auch so bekannt. Ich verwende den Mapcreator, damit ich überhaupt sehen kann, was da passiert, nicht weil ich osmand toll finde. (Persönlich habe ich den Verdacht, wenn ich mir deren Routingfile ansehe, dass die ihre eigene Routingmaschine nicht verstehen.)
Bei deiner App gibt es auch eine Art Visualisierung. Dort ist auch zu beobachten, dass je stärker die Hauptstrassen abgewertet werden, desto größer wird das Suchgebiet.
Wenn man jetzt einen Weg abseits der Hauptstrassen sucht, dann oszilliert das Ergebnis meist um den Weg herum, den ein Hauptstrassen priorisierendes Routing ausgibt. Vergleiche ich jetzt die Abweichung des Nebenstraßenweges zum Hauptstraßenweg, mit der Abweichung des Suchgebietes des Nebenstrassensuche zur Hauptstraßensuche dann wundere ich mich.
Warum muss ich plötzlich 10 Kilometer weiter links suchen, obwohl das Ergebnis nur einen Kilometer weiter links ist. Zwei bis drei Kilometer würden mir einleuchten. Lege mich bitte nicht auf die Zahlen fest, sondern es soll mein Problem verdeutlichen.
Durch einen dummen Zufall habe ich verstanden, wie dieser “heurstic coefficient” arbeitet. Wir veringern die Rechenzeit, indem wir billige Wege teuerer machen und damit drängen wir die Leute auf ungeliebte Straßen. Wenn man maxdefaultspeed entsprechend im routing.xml ändert, kann man sogar bewirken, dass es keine Beschleunigung, sondern nur eine Ergebnisänderung zum Schlechteren gibt.
Die für mich resultierende Frage ist, kann man irgendwie berechnen, wie sich die Rechenzeit durch einen Telephonwechsel ändert.
