[Talk-de] Routing Fehler A3-B58

Bernd Raichle bernd at dante.de
Mi Jun 24 14:03:38 UTC 2009


On Wednesday, 24 June 2009 14:44:23 +0200,
marcus.wolschon at googlemail.com <marcus.wolschon at googlemail.com> writes:
 > On Wed, 24 Jun 2009 12:50:37 +0200, Claudius <claudius.h at gmx.de> wrote:
 > > Am 24.06.2009 12:25, marcus.wolschon at googlemail.com:
 > > Du sagst also, dass wir die fuer die Router einfachere Taggingvariante 
 > > verwenden sollen? Ist die Unterstuetzung fuer Abbiegerelationen denn so 
 > > schwer?
 > 
 > Ja ist es. Denn das sind Einschraenkungen/Kosten-Funktionen an Knoten
 > statt Kanten was die meisten Routing-Algorithmen incl. den beliebten
 > Dijstra und A* nicht vorsehen.

Ist es das wirklich?  (Ich meine die _schwere_ Unterstuetzung
... wegen Knoten statt Kanten ...)

Wenn man Durchfahrtsbeschraenkungen (wie Einbahnstrasse etc.; fuer
eine Kante geltend) und Abbiegerelationen (wie Linksabbiegen verboten,
nur geradeaus etc.; fuer eine Kantenfolge mit 2 und mehr Kanten
geltend) als Kosten umsetzt, gebe ich dir recht.  Diese Dinge sind
aber _harte_ Ausschlusskriterien, d.h. im Dijkstra sorgen die
Durchfahrtsbeschraenkungen und Abbiegerelationen schon beim Erweitern
des Suchbaums, dass ich diese und jene Kante gar nicht erst als
Folgekante in Betracht ziehe (a la Gewicht=unendlich).  Damit bleibe
ich doch weiterhin kanten-orientiert und verwende die Knoten nur dazu
herauszufinden, welche Kante mit welche verbunden ist.

Bei Abbiegerelationen hat ein Router halt das Problem, dass sich diese
auf eine Kantenfolge beziehen, d.h. ich nicht einfach nur die
Eigenschaften einer einzelne Kante anschauen kann, um die Kante
auszuschliessen (bzw. zu bewerten).  Und das Nachschlagen/Mitfuehren
von erlaubten/verbotenen Kantenfolgen erhoeht den Aufwand schon
deutlich (ist aber nicht "schwer").

Daher sollten Mapper eine Kante mit "oneway=yes/1/-1" auf keinen Fall
durch die aequivalente Darstellung mit einer Menge von
Abbiegebeschraenkungen von anderen Kanten in diese Kante ersetzen.


 > > Mal abgesehen davon: Was wuerde es denn dem Router bringen, wenn ich den 
 > > gemeinsamen Abschnitt der Autobahnauf-/abfahrt mit oneway=no taggen 
 > > wuerde. Er koennte doch immer noch von der Abfahrt auf die Auffahrt
 > > routen.
 > 
 > Mein Beispiel war von der Autobahn in die Auffahrt, zurueck bis zur
 > Abfahrt und dort wieder auf die Autobahn. Das ist ein ganz anderer Fall.

... dann doch lieber ein paar zusaetzliche "oneway=yes" spendieren,
bevor man solch ein Routing-Ergebnis erhaelt ;-)

(Wobei man bei deinem beschriebenen Beispiel dieselbe Kante in
derselben Richtung mehrfach befaehrt, was fast immer unsinnig ist und
nur bei komplizierteren Abbiegebeschraenkungen vorkommen duerfte.)


Gruss,
  -bernd




Mehr Informationen über die Mailingliste Talk-de