[Talk-at] Routing (war: Double carriageways im Stadtgebiet (Alserbachstraße, Wien))

[Wolfgang W. Wasserburger]

... das hat wohl mit meiner Historie zu tun. Meine Modelle sind älter als
meine Bekanntschaft mit OSM; ich arbeite mit mathematischen Modellen, die in
einem Zug gleich mal mehrere Tausend Routen hintereinander rechnen. Das geht
wohl nur mit eigener Optimierung auf eigenen Geräten.
Bei rund 3x soviel Daten, wie OSM derzeit hat, rechne ich eine Strecke von
Wien nach Bregenz in unter einer Sekunde und das obwohl ich da die Daten
erst aus der Datenbank in den Speicher einer virtuellen Maschine hole -
dürfte wohl kein ganz schlechter Wert sein ;-)

Alles in den Speicher zu laden halte ich allerdings auch nicht für die
optimale Lösung, das setzt nämlich statische Geschwindigkeitsschätzungen
voraus, die ich gerne überwinden möchte.

Pascal Neis nach Wien zu bringen wäre sicher dennoch wirklich interessant.

Meine Ziele sind halt nicht im PKW/Fahrrad-Routing, sondern in der
Logistik - da sind die Anforderungen etwas höher.

BTW: meine erste Routing-Applikation habe ich 2002 für Österreich ins Netz
gebracht (existiert in dieser Form nicht mehr, soll aber (in Absprache mit
den Domain-Eigentümern) auf OSM-Grundlage wiederauferstehen :-). Da haben
wir auch mit einer Engine gearbeitet, welche die Daten vorlädt, hat sich
aber aus verschiedenen Gründen nicht sonderlich bewährt.

pgRouting ist eigentlich nur deswegen so schnell, weil die Library direkt im
PostgreSQL-Server läuft und eine Route sozusagen nur ein SQL-Request ist.
Das eigentliche Datenladen und so weiter fällt da fast weg.

Letztlich ist das auch keine neues Rad, sondern das Projekt läuft zumindest
seit 2005 ;-)

Ich arbeite seit 1988 mit GIS-Daten. Da hatte ich meine erste Übung auf
einem Großrechner mit ArcInfo, als einer der 3 ersten Studenten Österreichs.
Aus dieser Perspektive erscheint es mir manchmal auch so als wollten OSMler
Räder neu erfinden. Auf talk-de läuft zB gerade eine wirklich sinnlose
Diskussion über Projektionen, die halt daher kommt, daß die meisten
Mitdiskutanten keinen blaßen Tau haben, nicht einmal auf Wikipedia-Niveau
sind. Anfang der 90er-Jahre war das noch eine echte Challenge, zu den
passenden Formeln zu kommen und es gab nur ätzende Iterationsverfahren mit
höheren Wurzeln, die noch nicht alle Programmiersprachen implementier hatten
;-) Und an die Formeln zu kommen war ein echtes Abenteuer. Heute gibt es die
Proj4, die kann das ohne daß man allzu viel wissen muß.

Ähnlich ist es halt auch bei den Routing-Sachen: meine ersten Experimente
gehen auch hier auf 1988 zurück und waren noch in Fortran 77 gehalten. Das
war auf unserem Uni-Rechner gerade sinnvoll zu haben. Mit
Lochkarten-Emulatoren ging es damals ans Werk und wir haben auch schon
Ergebnisse erzielt.

Dazwischen habe ich mich mal in meiner Diplomarbeit mit diversen Algorithmen
auf mathematischer Basis befaßt und weiß ziemlich genau, welche
Laufzeitverhalten welche Algorithmen haben. Bei gleicher/ähnlicher Speicher-
und Programmimplementation gibt es da halt immer noch erhebliche
Abweichungen.

Manches liegt aber auch an der Geographie. pgRouting kennt neben dem
Dijkstra ('Klassiker') und dem Shooting-Star (mit Abbiege-Restriktionen)
auch noch den A* (schlecht zu googlen, aber unter Dijkstra gibts im
Wikipedia einen Link auf einen guten Artikel), der rein von der Mathematik
her schneller ist als der Dijkstra. Eine Testimplementation des A* für
Österreich hat mir aber gezeigt, daß dieser Algorithmus aufgrund der
Topographie eher Nachteile bringt. Wien und Umgebung sind gerade noch nicht
groß genug, damit seine Überlegenheit zum Tragen kommt und dann fangen die
großen Umwege durch die Gebirgsketten extrem zu wirken an. Für Holland würde
das Ding wahrscheinlich extrem pfeifen :-)

Verzeiht die Fossiliengeschichte - vielleicht hilft es dem einen oder
anderen weiter, spezielles Wissen abzuzapfen. Fragen sind jederzeit
willkommen.

lG Wolfgang

> -----Original Message-----
> From: talk-at-bounces at openstreetmap.org
> [mailto:talk-at-bounces at openstreetmap.org]On Behalf Of Andreas Labres
> Sent: Sunday, November 30, 2008 2:37 AM
> To: OpenStreetMap AT
> Subject: Re: [Talk-at] Routing (war: Double carriageways im Stadtgebiet
> (Alserbachstraße, Wien))
>
>
> Hallo Wolfgang!
>
> Warum fragst Du nicht den Pascal Neis, der hat sowas fertig
> implementiert...
> Wozu muß da jeder das Rad neu erfinden?
>
> Ja, erlädt alles in den Speicher. Seine Kiste hat etliche Gigabyte RAM.
>
> Und ja, das wichtigste ist ein Aufbereitungsschritt, der IIRC
> täglich läuft und
> die Daten in ein sinnvolles Modell umrechnet.
>
> Wenn das Thema Routing wirklich mehrere Leute so interessiert,
> könnte man ihn ja
> vielleicht auch mal nach Wien einladen... ;)
>
> Servus, Andreas
>
> _______________________________________________
> Talk-at mailing list
> Talk-at at openstreetmap.org
> http://lists.openstreetmap.org/listinfo/talk-at
>