Messreihe an Roadls Routing-Engine · BRouter
Eine Radroute von Düsseldorf nach Rom, in zwei Teilstücken gerechnet, ist 13 km kürzer und hat 636 Höhenmeter weniger als die am Stück gerechnete . Sie ist trotzdem messbar schlechter. Die Frage, wo man die Strecke stattdessen teilen sollte, führt geradewegs zurück in die OSM-Daten.
Messung Teilung gegen ganz · Düsseldorf → Rom · Profil trekking
Lange Strecken zerlegt Roadl in Teilstücke, weil die Engine sie am Stück nicht schafft. Der Schnittpunkt liegt dabei auf der Luftlinie. Ein Punkt, durch den die Route anschließend zwingend hindurch muss. Was das kostet, ist beziffert.
Kürzer, weniger Anstieg. und trotzdem 7,54 % teurer nach BRouters eigener Zielfunktion. Die beiden Routen liegen dabei über weite Strecken gar nicht nebeneinander: die Querabweichung erreicht im 95. Perzentil 113 km.
Wer eine Fahrradroute nach Länge und Höhenmetern beurteilt, hätte die schlechtere gewählt.
Der Grund ist unspektakulär und genau deshalb lehrreich: Länge und Höhenmeter sind nicht die Zielfunktion. Ein Router minimiert Kosten, und Kosten enthalten Belag, Verkehr, Abbiegungen, Wegtyp. Die geteilte Route spart Kilometer und Anstieg, indem sie über Wege ausweicht, die das Profil teuer bewertet. Beide Kennzahlen, die ein Radfahrer zuerst anschaut, zeigen in die falsche Richtung.
Zum Maßstab: die Schwelle, unterhalb derer eine Routenänderung in dieser Messreihe als „unauffällig“ gilt, liegt bei 0,05 % Kosten. Die heutige Teilung liegt beim 150-fachen davon.
Ausgangslage warum überhaupt zerlegt wird
BRouter berechnet eine Route auf genau einem Kern. Es gibt keine Parallelisierung innerhalb einer Anfrage. Das ist eine Eigenschaft der Engine, keine Frage der Einstellung. Wie viele Routen gleichzeitig laufen können, ist damit schlicht die Zahl der Kerne, die man dafür abstellt.
Daraus folgt etwas, das man leicht übersieht: mehr Hardware macht eine einzelne Route nicht schneller. Sie macht nur mehr davon gleichzeitig möglich. Die sieben Minuten für Rom bleiben sieben Minuten, gleich wie groß die Maschine ist. Was sich ändert, ist allein, wie viele andere Nutzer währenddessen warten.
Damit ist die Rechenzeit kein Budgetproblem, sondern ein algorithmisches. Und die Zerlegung ist kein Eleganzproblem, sondern der Grund, warum überhaupt jemand planen kann, statt zu warten.
Die automatische Zerlegung greift nur zwischen zwei aufeinanderfolgenden Wegpunkten und nur oberhalb von 800 km Luftlinie. Wer selbst einen Zwischenpunkt setzt, ersetzt den automatischen Schnitt durch seinen eigenen. Solange beide Teilstücke unter dieser Schwelle bleiben, teilt Roadl nicht noch einmal nach.
Der Nutzer entscheidet damit, wo die Route hindurch muss. Das ist besser als jede Luftlinien-Interpolation, wenn er den Punkt gut wählt — und genau darum geht es weiter unten.
Messung Rechenzeit der Teilstücke · Profil trekking
Warum überhaupt geteilt wird, zeigt sich erst, wenn man beides misst. Wird derselbe Korridor in der Mitte geschnitten, brauchen die beiden Teilstücke zusammen weniger Rechenzeit als die ungeteilte Strecke. Nicht ungefähr gleich viel, wie man erwarten würde, wenn sich Arbeit einfach aufteilen ließe, deutlich weniger.
Bei Rom bleiben von 411,6 s zusammengerechnet 40 % übrig, bei Madrid 47 %. Wäre der Aufwand der Länge proportional, kämen zwei halb so lange Stücke wieder auf 100 %. Sie tun es nicht und daran lässt sich ablesen, wie stark der Aufwand mit der Länge wächst: bei Rom etwa mit der 2,3. Potenz, bei Madrid mit der 2,1., bei Warschau nur mit der 1,4. Grob quadratisch also, umso ausgeprägter, je schwieriger das Gelände ist.
Das ist der eigentliche Grund für die Zerlegung, und er hat zwei Seiten. Für den Nutzer verkürzt sich die Wartezeit bei Rom von 411,6 s auf 85,0 s, weil beide Teilstücke gleichzeitig laufen knapp das Fünffache. Für den Server sinkt gleichzeitig die gesamte Rechenzeit, obwohl zwei Anfragen statt einer bearbeitet werden. Dieselbe Maschine bedient damit mehr Leute, und jeder Einzelne wartet kürzer.
Für einen Teil der Strecken ist die Teilung überhaupt die Bedingung
dafür, dass eine Route herauskommt. Düsseldorf → Rom ungeteilt
läuft mit keinem der drei ausgelieferten Roadl-Profile
durch. Alle drei brechen nach 600 s ab. Geteilt rechnen sie 275
bis 370 s je Teilstück. Die 411,6 s oben stammen vom
genügsameren Lagerprofil trekking, das es als einziges am
Stück schafft.
Eine Einschränkung gehört dazu: jede Zelle ist ein einzelner Lauf, und zwei Läufe derselben Konfiguration streuen um bis zu ±17 %. Mehr dazu weiter unten. Die Größenordnung trägt, die zweite Stelle des Exponenten nicht.
Und ein Vorbehalt, der gleich wichtig wird: das gilt innerhalb eines Korridors. Zwischen verschiedenen Korridoren sagt die Länge fast nichts .Das ist die nächste Überraschung.
Messung Luftlinie gegen Rechenzeit
Die Zerlegungsschwelle stand bei 800 km Luftlinie. Unter der Annahme, dass längere Strecken länger rechnen. Die Annahme hält nicht:
| Korridor | Luftlinie | Höhenmeter | Rechenzeit |
|---|---|---|---|
| Düsseldorf → Kopenhagen | 626 km | 1524 | 73,6 s |
| Düsseldorf → Warschau | 984 km | 2429 | 75,8 s |
| Düsseldorf → Rom | 1123 km | 8872 | 411,6 s |
| Düsseldorf → Madrid | 1448 km | 9385 | 417,1 s |
Madrid liegt 325 km weiter als Rom und braucht dieselbe Zeit. Warschau ist nur 140 km näher als Rom und braucht ein Fünftel. Was hier durchschlägt, steht in der dritten Spalte: über diese vier Korridore korrelieren die Höhenmeter mit der Rechenzeit zu 0,996, die Luftlinie nur zu 0,821.
Der naheliegende Verdacht, die Alpen hätten ein besonders dichtes oder verzwicktes Wegenetz wurde eigens geprüft und fällt durch. Der Alpenkorridor expandiert 2,56× mehr Knoten je Luftlinien-km als der flache; allein aus Länge und Schätzfehler sagt das Modell 2,44× vorher. Der Überschuss beträgt 1,05× also nichts. Und der Umwegfaktor schwankt über die ganze Rom-Route nur zwischen 1,40 und 1,52, Gebirge 1,502 gegen Flachland 1,452. Keine Barrieren-Signatur.
Es sind auch gar nicht die Alpen. Madrid liegt nicht in den Alpen es quert Pyrenäen und Meseta, hat vergleichbar viele Höhenmeter und braucht dieselbe Zeit. Es ist nicht das Gebirge. Es ist das Steigen.
Mechanismus warum Höhe die Suche verbreitert
BRouter sucht mit A*. Es verwirft einen Knoten, wenn die bisherigen Kosten plus eine Schätzung der Restkosten die beste bekannte Gesamtroute übersteigen. Die Schätzung ist die Luftlinie in Metern sie weiß nichts von Höhe.
Jede Kosteneinheit, die aus dem Klettern kommt, ist damit unsichtbar: sie vergrößert die wahren Restkosten, ohne dass die Schätzung mitwächst. Auf der Rom-Route stammen 27 % der Gesamtkosten aus Höhenmetern, auf der Warschau-Route 11 %. Der Schätzfehler steigt entsprechend von 1,34 auf 1,73.
Was das anrichtet, lässt sich geometrisch sagen. Die Bedingung „bisherige Kosten plus Luftlinie ≤ Gesamtkosten“ beschreibt eine Ellipse mit Start und Ziel als Brennpunkten. Wächst der Schätzfehler, wächst die Ellipse überproportional, weil die Nebenachse mit der Wurzel geht. Aus einem schmalen Band entlang der Luftlinie wird eine Fläche, die in alle Richtungen ausgreift.
Ein Routenplaner rechnet nicht lange, weil die Strecke weit ist, sondern weil sie hoch ist und zwar weil seine eingebaute Abkürzung Höhe gar nicht kennt.
Dasselbe erklärt, warum ein Profil, das Umwege für Belag oder Verkehr belohnt, zusätzlich Rechenzeit kostet: jeder Aufschlag hebt die Kosten je Meter, während die Schätzung bei einem Meter pro Meter bleibt. Komfort kostet nicht nur Umweg, sondern auch Sekunden.
Zwei Messungen Güte der Route · Teilung auf Korridoren
Wenn geteilt werden muss und das muss es, dann ist die Frage nicht ob, sondern wo. Dazu gibt es zwei Messungen, und sie liegen an den entgegengesetzten Enden desselben Prinzips.
Ein Schnitt auf der Route, die ohnehin herausgekommen wäre, ist gratis. Gemessen über sechs Korridore: Δ Länge 0,000 %, Höhenmeter ≤ 0,4 %, größte Abweichung 16 m. Das gilt für beliebig viele Teilungen. Nur kennt man diese Route vorher nicht — sonst müsste man sie nicht ausrechnen.
Ein Schnitt daneben kostet, aber sehr unterschiedlich viel. Zwei Fälle aus derselben Messung, beide mit demselben Verfahren geteilt:
| Korridor | Δ Länge | Δ Höhenmeter | Querabweichung |
|---|---|---|---|
| Koblenz → Regensburg Rhein, Main, Donau |
0,000 % | 0,00 % | 4 mm |
| Düsseldorf → Nürnberg Sauerland, Rhön, Frankenhöhe |
−1,09 % | +62,7 % | 32,2 km |
Vier Millimeter gegen 32 Kilometer, bei identischem Verfahren. Der Unterschied ist nicht das Verfahren, sondern das Netz an der Schnittstelle.
Im Flusstal gibt es faktisch einen sinnvollen Weg. Ein Punkt, durch den die Route ohnehin muss, zwingt sie zu nichts, der Schnitt ist folgenlos. Im Mittelgebirge liegt der interpolierte Punkt 30 km daneben, und zwar im falschen Tal. Die Route muss dann über einen Kamm, den die optimale umfährt: die Länge stimmt fast, die Höhenmeter explodieren.
Ein Schnittpunkt kostet genau so viel, wie das Wegenetz an dieser Stelle an Alternativen hat.
Damit wird aus einer Routing-Frage eine Datenfrage und hier fängt es an, für OSM interessant zu werden. Die guten Schnittstellen sind genau die Stellen, an denen sich das Netz verengt, und die stehen in der Karte:
mountain_pass=yes markiert wörtlich
die Stelle, an der ein Kamm genau einen Durchlass hat.
Ein Nutzer kann das heute schon von Hand tun: Zwischenpunkt auf die Brücke oder auf den Pass setzen statt irgendwo in die Landschaft. Nach der Messung oben kostet das dann annähernd nichts und man behält die Kontrolle darüber, wo die Route langgeht.
Automatisiert ist davon nichts. Zwei Messpunkte an den Extremen stützen das Prinzip; wie es sich dazwischen verhält, ist offen. Und der naheliegende Weg zur Automatisierung ist bereits gescheitert: erst eine grobe Route rechnen und deren Mittelpunkt als Schnittstelle nehmen, bringt dieselben schlechten Punkte wie die Interpolation, die Grobform liegt im selben falschen Tal. Das Verfahren zu wiederholen konvergiert nicht, es bleibt in zwei von drei Korridoren nach der ersten Runde stehen.
Was fehlt, ist der umgekehrte Weg: die Engstellen aus der Karte zu bestimmen, unabhängig von jeder Route, und die Teilung dorthin zu legen. Das ist offline vorberechenbar und braucht keine Routing-Anfrage. Gebaut ist das noch nicht.
Methodik was das Messen selbst kostet
Der beständigste Teil dieser Messreihe sind nicht die Ergebnisse, sondern die Irrtümer auf dem Weg dahin. Jeder sah während der Messung nach einem Befund aus.
Zwei Läufe derselben Konfiguration unterscheiden sich um bis zu ±17 %. Die naheliegende Erklärung: „unterschiedliche Server“ ist falsch: die Identität der Instanz trägt 0 %. Was streut, ist die Zeit, rund 13 %/h innerhalb einer Sitzung. Damit ist auch die naheliegende Abhilfe falsch: Wiederholungen hintereinander tasten nur wenige Minuten ab. Was schützt, ist Verschränkung — A/B/A/B.
Sechs identische Anfragen, dieselbe Instanz, dieselben Parameter, zwei verschiedene Routen. Der abweichende war der erste nach einer Pause und zugleich der langsamste. Ursache ist die Aufräumroutine des Knotenspeichers: sie iteriert über eine Hashtabelle, und welche Knoten dabei verschwinden, hängt von der Reihenfolge ab die wiederum von der Vorgeschichte des Prozesses. Ohne Aufwärmlauf hätte dieser Effekt eine korrekte Änderung fälschlich verworfen.
Eine Methode stand mit 10,9 % Selbstzeit im Profil mehr als die beiden Aufräumroutinen zusammen. Die Optimierung war verhaltensgleich, sauber gebaut, im Bytecode verifiziert und brachte −0,4 %. Sie war der erste von drei Durchläufen über dieselbe Liste und zahlte die Cache-Misses, die die beiden folgenden dann nicht mehr zahlten. Selbstzeit ist nicht einsparbare Zeit.
Fazit drei Sätze zum Mitnehmen
Was der Beitrag nicht behauptet: dass die Zerlegung abgeschafft gehört. Sie bleibt nötig. Rom läuft mit keinem ausgelieferten Profil am Stück durch, auch nicht mit einer besser eingestellten Schätzfunktion der erste von zwei Suchdurchgängen verwirft nämlich gar nichts und trägt trotzdem etwa die Hälfte der Rechenzeit.
Wer eine Strecke über 800 km Luftlinie plant, setzt den Zwischenpunkt am besten selbst. Der automatische Schnitt landet auf der Mitte der Luftlinie und weiß nichts über das Gelände du weißt es. Meistens gibt es ohnehin feste Zwischenziele: die Übernachtung, der Pass, der Bahnhof, an dem die Tour beginnt. Sie als Wegpunkt einzutragen kostet nichts und ersetzt den geratenen Schnitt durch einen gewollten.
Ein Freibrief für uns ist das nicht. An der Frage, wo ein Schnitt hingehört, arbeiten wir weiter die Karte weiß, wo die Brücken sind, und ein Router sollte das lesen können, statt auf halber Luftlinie zu raten.