[Mapserver-DE] Routing mit Mapserver

[Daniel Kastl]

Hallo Michael,

Das Thema ist wirklich spannend, sobald man sich damit beschäftigt.
> Ich würde meinen, jeder Routing-Algorithmus ist ein shortest-path
> algorithmus, wobei es in unseren Anwendungsfällen doch immer eher um
> lowest cost geht. 
So sehe ich das eigentlich auch. In pgRouting (sowohl Dijkstra als auch
A*) gibt deshalb als zentralen Wert den "cost" Parameter. Er stellt
einen Widerstand dar, und macht die jeweilige Kante mehr oder weniger
attraktiv. Es hängt also ganz davon ab, wie man diese "Kosten"
berechnet, welche Kanteneigenschaft man wie bewertet. Wir haben darüber
diskutiert, wie man am Besten eine Kante aus dem Netz nimmt: indem man
ein Attribut "on/off" hinzufügt, oder indem man die Kosten (unendlich)
hoch setzt. Letztlich haben wir ert einmal den selben Weg gewählt wie
bei pgDijkstra.

> Der gerichtete Graph würde den Fall Abbiegeverbote doch bereits
> einschliessen, oder? Im gerichteten Graph, wäre es vom Graphen
> vorgegeben welche Knoten mit bestimmter Richtung mit den nächsten
> Knoten verbunden sind und damit auch, ob beim Routing, wenn ich an
> der/dem Kreuzung/Knoten angelangt bin, überhaupt auf eine bestimmte
> Kante abgebogen werden kann. Dann ist die Frage (und die geht jetzt
> vorallem an Daniel): kann der A*-Algorithmus dies berücksichtigen?
Ebenso wie bei pgDijkstra gibt es zwei "cost" Parameter, je einen pro
Richtung. Damit kann man z.B. Einbahnstrassen beschreiben. Mit
Abbiegeverboten ist das jedoch etwas anders. Da wird es kompliziert.
Gute Ideen sind jederzeit willkommen ;-) Die Daten, die wir besitzen,
geben keinen Aufschluss über Abbiegeverbote, so dass diese nicht
berücksichtigt werden (können). Da es Open Source ist, kann natürlich
jeder den Routingalgorithmus erweitern und eigenen Bedürfnissen anpassen.

> @Till: Du hast in deiner Mail auch geschrieben, dass z.b. bestimmte
> Streckentypen vorher aus dem Netz rausgenommen werden. Habe ich das
> richtig verstanden? Wie stellt ihr dann sicher, dass man immer noch
> mit einem zusammenhängenden Netzwerk rechnet/routet?
Ich denke, wenn man z.B. eine Route für Radfahrer berechnet, dann muss
man die Autobahnen rausnehmen. Und wenn es im Netzwerk keine Alternative
zur Autbahn gebt, dann ist es eben nicht zusammenhängend und es gibt
keinen Weg von A nach B.

Michael, vielleicht habe ich es ja überlesen. Aber mich würde
interessieren, um was für ein Routingprojekt es sich bei Dir handelt. Es
gibt so viele spannende Anwendungen, in denen man Routing verwenden kann.

Viele Grüße

Daniel

*********************************************************
Orkney, Inc. Headquarters
6F JA-Kyosai Yokohama Building,
1-2 Kaigandori, Naka, Yokohama 231-0002 JAPAN 

TEL: +81 (0)45 - 228 - 3320 (Office)
TEL: +49 (0)89 - 420 959 519 (VoIP)
FAX: +81 (0)45 - 228 - 3321 

kastl at orkney.co.jp <mailto:kastl at orkney.co.jp>
www.orkney.co.jp <http://www.orkney.co.jp>
*********************************************************