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

[Wolfgang W. Wasserburger]

Also ich habe in den letzten Monaten pgRouting mit allerhand Daten gefüllt
und einiges an Erfahrungen rausgeholt. Die (offensichtlich) japanischen
Entwickler hören eher nicht auf Zuruf. Rein von der Performance ist das
Problem ganz wo anders: zum Rechnen einer Route muß man schnell mal ein paar
Hunderttausend Datensätze in den Speicher holen. Da spielt es schon eine
entscheidende Rolle, ob die Tabelle, die man abfrägt eher aus varchars oder
text-Feldern mit fester Länge besteht und ähnliches.
D.h. letztlich, daß man die Daten beim Import (besser vielleicht
Transformieren) fürs Routing kräftig umarbeiten muß. Darüber denke ich
gerade intensiv nach, wie man das wirklich gut hinbringen kann.

Der Arbeitsvorgang ist in etwa folgender (unter Postgres/PostGIS):
Man nehme jeden Way, überlege sich anhand der Tags
highway,cycleway,oneway,foot,footway,... welche Geschwindigkeit ein
bestimmtes Fahrzeug dort fahren könnte.
Dann geht es richtig los: das Programm geht von Node zu Node und schreibt
diese als Edge (Bezeichnung für eine Kante unter pgRouting) in eine neue
Tabelle. Soferne nun ein Node kommt, der mit Querstraßen geteilt wird, muß
man abbrechen und ein zweites neues Edge beginnen. Ebenso, wenn da irgend
ein Hindernis die Durchfahr gänzlich behindert.
Als nächsten Schritt nehmen wir das gerade geschaffene Postgis
Polylinien-Objekt um dessen Länge zu berechnen; zusammen mit obiger
Überlegung der Reisegeschwindigkeit läßt sich dann ein Kantengewicht
bestimmen, daß für das Routing benötigt wird, soferne man die schnellste
Route haben will.
Parallel kommen natürlich noch die Abbiege-Restriktionen: hier kann man
üblicherweise auch ein Gewicht für den Übergang von Kante A nach Kante B
mitgeben, wenn man's gar nicht darf, setzt man die benötigte Fahrzeit halt
einfach auf Jahrhunderte.

Das ganze ist einigermaßen komplex, dauert daher für jede Kante viele
Schleifendurchläufe und viele Selects lang. Wenn man hier die
Abbiege-Restriktionen und andere Punkt-Ereignisse wegläßt. Wird das ganze um
sehr vieles leichter. Daher steht auch an diesem Arbeitsende die Tendenz zu
einfacheren Algorithmen.

Für meine Anwendungen brauche ich im übrigen nur die FAhrzeiten/Kilometer
von A nach B; die Abweichung der exakten Strecke ist mir nicht groß genug um
die länger Rechenzeit in Kauf zu nehmen. Wenn dann jemand die endgültige
Route aufzeichnen läßt rechne ichs exakt und gerade das macht mir OSM nicht
wirklich leicht.

Das Überführen in eine sinnvolle Datenstruktur für Routing ist da wirklich
eine Challenge.

Jetzt hoffe ich aber auf gute Ideen aus der Community

lg Wolfgang

> -----Original Message-----
> From: talk-at-bounces at openstreetmap.org
> [mailto:talk-at-bounces at openstreetmap.org]On Behalf Of Andreas M.
> Sent: Saturday, November 29, 2008 10:14 AM
> To: talk-at at openstreetmap.org
> Subject: Re: [Talk-at] Double carriageways im Stadtgebiet
> (Alserbachstraße, Wien)
>
>
> Hi,
>
> Wolfgang W. Wasserburger wrote:
>
> [...]
>
> Danke für die Aufklärung zu den Routing-Algorithmen, das trägt für mich
> als GIS-Laien sehr zum Verständnis bei.
>
> > Unter dem Strich ist es sicher leichter auf den richtigen Algorithmus
> > umzustellen, als Renderern hübschere Sachen beizubringen.
>
> Genau darum ging es mir, im Grunde ist das also die Erweiterung von "wir
> mappen nicht für den Renderer" auf Router.
>
> Für das Mappen wäre es natürlich eine erhebliche Erleichterung und nicht
> zuletzt eine Reduzierung potenzieller Fehlerquellen, wenn man sich auf
> das zum korrekten Abbilden der Gegebenheiten notwendige Minimum an
> Datenelementen beschränken könnte.
>
> Die Frage ist, ob es realistisch wäre, mittelfristig mit einer Anpassung
> auf Router-Seite zu rechnen. Zumindest in der Open Source-Ecke sollte
> das durchaus machbar sein.
>
> Gruß
> Andreas
>
>
> _______________________________________________
> Talk-at mailing list
> Talk-at at openstreetmap.org
> http://lists.openstreetmap.org/listinfo/talk-at
>