[Mapserver-DE] Routing mit Mapserver

[Michael Schulz]

Hallo zusammen,

habe jetzt nach ein bisschen Nachdenken über Flavios letzte Mail noch
ein paar Fragen oder Kommentare:

> > Das ist Richtig. Der Algorithmus ist ein Shortest Path Algorithmus.
> > Aber ist das nicht bereits Routing?
>
> frage ist, was ist "routing" ??? "shortest path" ist relativ simpel, da
> gibt es "kanten" (nennen wir die abschnitte mal so), eine einfache
> topologie (verbunden / nicht verbunden) und dazu die kanten-kosten. ich
> kann aber von jeder kante nach jeder kante (ausser bei "nicht
> verbunden", z.b. brücke oder tunnel). strassen-routing (und nur das ist
> meiner meinung nach "routing") ist da ein bisschen komplexer, z.b. eben:

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. Die von Flavio hier angeführte einfache Topologie
(Knoten sind über Kanten verbunden und können in allen Richtungen
begangen werden = ungerichteter Graph) wird ja schon etwas
komplizierter, wenn man beim Routing von einem gerichteten Graphen
ausgeht (knoten sind über kanten verbunden, aber die kante enthält die
Information, dass sie nur von A->B nicht aber von B->A begangen werden
kann).

>
> abbiegeverbote:
> sind meist unabhängig vom strassentyp (reine verkehrsregeln). also muss
> ich eine zusätzliche information mitgeben, von welcher kante ich zu
> welcher kante "springen" kann. beispiel kreuzung: ich kann von kante A
> auf kante B links nicht abbiegen, dafür auf kante A rechts (aus C) oder
> geradeaus (aus D) sehr wohl. also AB verboten, alle anderen verbindungen
> erlaubt.

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?

> zustände:
> beispiel: über verkehrsmeldesysteme kann ich online abfragen, ob ein
> alpenpass offen ist oder nicht ("real time", alle 8 minuten oder so
> nachgeführt). also muss ich zu gewissen knoten ein zustandstabelle
> mitführen können, die "real-time" berücksichtigt wird.

Ok, d.h. man ändert in dem Fall immer das Netzwerk? Ungefähr so: "Habe
die Info, dass der Alpenpass der an meinem Knoten A anfängt gesperrt
ist, also entfällt die Kante hinter A aus dem Netzwerk."?  Könnten
diese Zustände, nicht auch über die Kostenberechnung mit in das
Routing eingehen? Die Kosten für die Kante die einen gesperrten
Alpenpass darstellt, muss halt in dem 8-min. Rythmus aktualisiert und
im gesperrten Fall auf einen exorbitanten Wert gesetzt werden, damit
sie sicher beim Routing umgangen wird.

@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?

Finde dieses Thema und die Diskussion recht spannend, da sinnvolles
Routing doch bis vor PgDijkstra Zeiten eigentlich eher proprietären
Systemen vorbehalten schien. Aber sofort taucht dann wieder das
Problem der miserablen oder eben sündhaft teuren, guten Daten auf,
ohne die Routing auch mit dem besten Algorithmus zäh ist.

Viele Grüße, Michael
-- 
-----------------------------------------------------------
Michael Schulz
mschulz at webgis.de

in medias res
Gesellschaft für Informationstechnologie mbH

In den Weihermatten 66
79108 Freiburg

Tel  +49 (0)761 556959-5
Fax +49 (0)761 556959-6

http://www.webgis.de / http://www.zopecms.de
-----------------------------------------------------------