Java-Bibliotheken für Routing gesucht

Ich habe mal gegoogelt

http://osm2po.de/ habe ich gefunden. ist die frage wie ausgereift deren angepasster a*-algorithmus ist. kann ich nicht beurteilen, da ich auch kein entwickler bin.
Ansonsten hat Cloudmade eine Java-API: http://developers.cloudmade.com/projects/show/java-lib

Ich denke das Routing ganz andere Anforderungen an die Datenstrukturen im Hintergrund stellt als Rendering, von daher bin ich nicht sicher, ob ihr da wirklich drum rum kommen werdet. Als fallback gäbe es ja auch noch pgrouting.

Wer genau seid ihr denn?

@kerosin:
http://osm2po.de/ scheint mir nicht geeignet, das es nicht auf der Datenbankschicht arbeitet, sondern mit den XML-Dateien. Das erscheint mir nicht performant genug, da wir hunderte von Routings durchgrechnen müssen und ein gesamter Druchlauf für Bayern (inkl. Rendering) nicht länger als 5-10 min dauern darf...

http://developers.cloudmade.com/projects/show/java-lib ist vermutlich auch problematisch, weil uns da abhängig von einem externen Webservice machen, von dem ich nicht weiß wie zuverlässig und performant er ist und ich nicht riskieren will, dass wir diesen Dienst mit Anfragen fluten und externe Kosten in unbekannter Höhe erzeugen...

@!i!:
Da hast Du recht, wobei wir ja eine extrem primitive Variante von Routing benötigen. Wir brauchen das als Basis für die Einfärbung von Straßenzügen mit Verkehrsflussdaten. Da dies sehr viele Straßen sind, müssen wir diese als Tiles rendern und können nicht einfach mit OpenLayers clientseitig arbeiten.

Wir sind ein Projekt, das auf Basis eines TMC-Netzes Verkehrsinformationen für Bayern auf einer OpenStreetMap-Karte darstellen will...

Wenn ihr keine Bibliothek dafür findet: In einem eigenen Ansatz wüsste ich nicht, was genau ihr mit Relationen vorhattet. Im Endeffekt müsste es darauf hinauslaufen, einen Routing-Algorithmus (A* beispielsweise) auf Knoten anzuwenden, wobei zwei Knoten genau dann als verbunden gelten, wenn sie Nachbarn in einem Weg sind, dessen Eigenschaften für eure Zwecke geeignet sind.

Richtig, die Schwierigkeit liegt nur darin, wie man möglichst wenig Umwege bei der Suche einschlägt.
Wir hofften, den Algorithmus dadurch effizient zu bekommen, dass wir wissen, dass die beiden Endpunkte auf ein und derselben Straße liegen. Und falls diese Straße als Relation abgespeichert ist, reduziert das die Anzahl der im Algo. zu durchlaufenden potentiellen ways dramatisch.
Dies nutzen wir auch, aber dadurch fallen viele Straßen durchs Raster. Zudem wird der Code immer komplexer und undurchsichtiger, je mehr (Optimierungs-)Varianten man einbaut. Und der ist angesichts von Zyklen (Kreisverkehr) etc. schon schlimm genug. Daher suchen wir eine fertige Lösung, d.h. jemanden, der so etwas schon mal gelöst hat. Und das Thema Routing ist zwar für unser Team neu, aber nicht gerade exotisch.

Also wenn ihr euch echt um die Performance sorgt, würde ich MoNav empfehlen. Den Dienst könnt ihr selber hosten und der ist leicht einzubinden. Schau dir mal die Performance an: http://map.project-osrm.org Nutzt allerdings auch nicht die HauptDB, sondern glaube ich eine Datei.

P.S. Unter TrafficJam habe ich leider nichts gefunden, gibt es da einen Link? Wenn ihr die TMC Informationen mit OSM verknüpft (oder die bei uns eingepflegten nutzt), müsst ihr allerdings das Ergebnis (oder neu laut ODbL die ursprünglichen DBs) unter derselben Lizenz zugänglich machen.

Wenn ihr immer auf der gleichen Straße bleibt: Vorauswahl über ref (bei größeren Straßen) oder name (innerorts), aber auf unterschiedliche Schreibweisen achten. Außerdem dürfte es dann ausreichen, außer bei Kreisverkehren, aber die sind ja recht leicht zu filtern (zumindest theoretisch sollten die alle junction=roundabout haben) nur Anfangs- und Endknoten zu betrachten.

Hallo Leute!

Hier ein wenig Licht in der Dunkelheit:

1) Ein Routing wird niemals auf den OSM-Way-IDs arbeiten, da dies schlichtweg nicht funktioniert.

2) Die Daten müssen vorher konvertiert werden und wenn das gesuchte Programm gut ist, dann liefert es vielleicht zusätzlich die ursprüngliche OSM-ID zurück.

3) Es gibt nun grundsätzlich zwei Zielgruppen. Die einen suchen ein schnelles Routing (z.B. als C++-API), andere eher für geografische Fragestellungen. Bei letzteren liegt der Fokus auf Datenmanipulations-Möglichkeiten. z.B. um externe Sachen hineinzumischen, Visualisierung in GIS-Programmen, etc.
Die ursprüngliche Frage in diesem Thread bezog sich jedoch auf Geschwindigkeit und Handhabung.

4) Den ersten Platz belegt da ein Programm, geschrieben in purem C, was die Konvertierung und das Routing übernimmt und zusätzlich kompatibel in alle Richtungen ist. Ein solches Programm kenne ich nicht.

5) Die alternative ist pgRouting (reines Datenbankrouting) - eher für Analysezwecke geeignet, wo die Laufzeit keine Rolle spielt. Dann hätten wir den MoNav von OSM. Entweder als fremden Dienst anzusteuern (=Abhängigkeit) oder lokal zu installieren. Allerdings braucht man für letzteres eine etwas anspruchsvollere Rechner-Landschaft. MoNav ist aber sauschnell.

6) osm2po arbeitet entgegen der obigen Behauptung weder auf XML noch auf der Datenbank.
Richtig ist: Es liest osm.xml, osm.bz2, osm.pbf und konvertiert dies in ein eigenes Format.
Als Nebenprodukt fällt dabei auch noch SQL für PostGIS/pgRouting ab.
osm2po kann über HTTP-GET oder SOAP angesprochen werden.
osm2po kann auch als Java-Library eingebunden werden.

7) Ein A* Algo ist kein Hexenwerk. Es ist und bleibt ein Dijkstra mit'm bisschen Heuristik drin. Was die Routing-Algos betrifft, kochen eigentlich alle nur mit Wasser. Wenn ein A* behauptet, er sei schneller als ein anderer, dann wird an der Heutistik gedreht und geschummelt. Es gibt für A* eine ganz eindeutige Heuristik-Vorschrift (Formel), die ihn sogar "optimal" werden lassen kann.

8) Ach ja... und es kann sogar passieren, dass ein Dijkstra performanter läuft als ein A*. Das hängt von geografischen Besonderheiten ab oder davon, ob man sich vom Rand des Kartenausschnitts in die Mitte bewegt oder eben anders herum.

9) Schneller kriegt man diese Kisten meistens dadurch, dass man von beiden Seiten gleichzeitig losroutet und wenn man sich dann in der Mitte trifft, dann hat man den Weg gefunden. Eine weitere Opti-Maßnahme ist die Vorausberechnung von Transitstrecken. Oder eben contraction hierarchies (MoNav). Diese Dopplungen, Überlagerungen und Relaxionen benötigen allerdings meistens wesentlich mehr Arbeitsspeicher.

Eine Möglichkeit wäre evtl. noch GeoTools. Das wird vom OpenRouteService verwendet (leider nicht Open Source). Der ORS zeigt in Bayern auch TMC Verkehrsinfos an. Ihr könnt ja einfach mal Pascal kontaktieren.

Im Java Magazin 04+05/2010 gab es ein Tutorial "Laufen im Kreis" mit einem kleinen Beispiel für Routing mit GeoTools und einer osm2pgsql DB. Der Source dazu liegt auf sourceforge.

Gruß,
Norbert

Hi ikonor,

hast du mal ein paar Eckwerte von dem Teil?
Sehe da eine Menge Java-Modell-Gehühner.
Da ich selbst Java-Entwickler bin, kann ich mir nicht vorstellen, dass da Deutschland oder Europa in den Speicher passt.
Die Laufzeit würde mich ja auch mal interessieren. Java-Objekte sind nicht grad die schnellsten.

pimapper wrote:

hast du mal ein paar Eckwerte von dem Teil?
Sehe da eine Menge Java-Modell-Gehühner.
Da ich selbst Java-Entwickler bin, kann ich mir nicht vorstellen, dass da Deutschland oder Europa in den Speicher passt.
Die Laufzeit würde mich ja auch mal interessieren. Java-Objekte sind nicht grad die schnellsten.

Ich kann leider nichts genaueres dazu sagen, hab das selbst noch nicht ausprobiert, das wartet noch geduldig auf meiner ToDo Liste 😉

ikonor wrote:

pimapper wrote:

hast du mal ein paar Eckwerte von dem Teil?
Sehe da eine Menge Java-Modell-Gehühner.
Da ich selbst Java-Entwickler bin, kann ich mir nicht vorstellen, dass da Deutschland oder Europa in den Speicher passt.
Die Laufzeit würde mich ja auch mal interessieren. Java-Objekte sind nicht grad die schnellsten.

Ich kann leider nichts genaueres dazu sagen, hab das selbst noch nicht ausprobiert, das wartet noch geduldig auf meiner ToDo Liste 😉

Schade. Wäre ja mal interessant gewesen.

Das hört sich doch schon mal ganz spannend an.
Wir sehen uns GeoTools, osm2po und MoNav mal an.

Leider werfen die meisten Rooting-Tools nur Tracks aus, weil sie die EINE berechnete Route einfärben. Da wir aber hunderte (und später wahrscheinlich tausende) von Straßen/Strecken einfärben wollen, muss das in einen gerenderten Layer als Kacheln passieren, wenn der Dienst eine erträgliche Performance bieten soll.
Daher setzen wir derzeit ein Farbattribut in die planet_rels, das dann der Mapnik nutzt. Und dies passiert bisher auf Basis der errechneten way-Ids.

Was die Lizenz angeht, wir nutzen nur die TMC-Angaben in OSM (und pflegen dort auch fleißig neue TMC-Referenzen ein...). Insofern sehe ich da DB-Lizenzproblem. Das Ergebnis, also die Karte (inkl. Quellreferenz) wird auch für jedermann kostenlos zur Verfügung stehen, sobald das Ganze stabil und performant läuft. Muss/soll man den gesamten Quellcode auch zur Verfügung stellen? So allg. kann man damit ja gar nichts anfangen, weil die Eingangsverkehrsdaten und die notwendige Infrastruktur ja höchst speziell ist.

Ihr müsst den Quellcode nicht zur Verfügung stellen. Aber sicher habt ihr Euch Gedanken gemacht, die ihr dem ein oder anderen Projekt ersparen könntet.

Du sprichst sehr von Performance. Glaubst du es ist wirklich weniger anstrengend alle 10 Minuten die Kacheln neu rendern als nach Regionen gefilterte Tracks für die Farben auszuliefern?
Im Prinzip würdet ihr ja die Kacheln auch rendern, wenn sie gar keiner sehen möchte. Das würde schon mal von sich aus eine große Last darstellen.

Ihr müsst den Quellcode nicht zur Verfügung stellen. Aber sicher habt ihr Euch Gedanken gemacht, die ihr dem ein oder anderen Projekt ersparen könntet.

Sehr gerne, wir sind da völlig offen.

Du sprichst sehr von Performance. Glaubst du es ist wirklich weniger anstrengend alle 10 Minuten die Kacheln neu rendern als nach Regionen gefilterte Tracks für die Farben auszuliefern?
Im Prinzip würdet ihr ja die Kacheln auch rendern, wenn sie gar keiner sehen möchte. Das würde schon mal von sich aus eine große Last darstellen.

Was heißt anstrengend? Wir haben eine performante Hardwareinfrastruktur, die möglichst häufig die aktuelle Lage visualiseren soll. Ob die einzelnen Kacheln in allen Zoomstufen auch tatsächlich abgerufen werden, das ist natürlich nicht in unserer Hand.
Wenn wir hingegen sämtliche Tracks als GPX o.ä. ausliefern, dann sind das in den großen Zoomstufen Hunderte oder gar Tausende Linien, die der Client rendern muss (im Gegensatz zu einer Hand voll Kacheln). Unsere Tests haben ergeben, dass viele einfache Clients (z.B. Netbooks) damit völlig überfordert sind.

Jetzt sind wir etwas vom eigentlichen Thema der Rotenfindung abgekommen...

Hmm könntest du uns bitte noch mal etwas präziser den Einsatzzweck umreißen. Bisher wurde von dir/euch nur nach Routing gefragt und immer darauf hingeweisen, dass aber gleichzeitig hunderte Strecken gemessen werden müssen. Also was ist denn das Anwendungsszenario, dann könnten andere sicherlich auch malüber die Probleme mit der Darstellung nachdenken.

Wenn ich das bei Frederiks Vortrag richtig mitgenommen habe, müsst ihr bei der ODbL dann zwar nicht das Endprodukt frei zugänglich machen, aber die Datenbank bzw. einen Algorithmus beschreiben, wie diese erstellt wurde. Ansonsten müsst ihr die Sourcen aber natürlich nicht zugänglich machen.

Es geht darum die TMC Verkehrslage zunächst für Bayern darzustellen. Der Anspruch liegt bei gegen Echtzeit und mindestens alle 10 Minuten. So verstehe ich die Informationen aus dem Beitrag 4.
Aber er hat natürlich Recht, wenn er auf das Thema verweist, dass es hier ums Routing geht und nicht um seine Hardware.
Wie liegen eigentlich die Daten vor? Kann man nicht in einem Präprozess alle möglichen Strecken schon den TMC Strecken zuordnen und wie beim osm2pgsql-shema Schon als fertige Wege in der Datenbank liegen haben. Mapnik ist es im Prinzip egal ob er 1 oder 3 Wege übereinander zeichnet. Wichtig ist nur das der wichtigste zu letzt oben drauf liegt. Aber das erreicht man auch dadurch das man die kritischsten einfach (Stau oder so) dann zu letzt zeichnet. (Falls sich die einzelnen Strekcne überhaupt überschneiden können)

Sorry hatte ich glattweg übersehen. Aber wenn es nur um eine Färbung geht, reicht es doch die TMC Segmente zu isolieren und diese dann als Overlay einzufärben (ansatzweise so hatte das ja die Maxspeed oder Parkinglanes Karten gemacht). Der OpenRouteService nutzt dann die Echtzeitinfos in Bayern doch sowieso schon und das Routing wäre erstmal draußen?

Das Problem scheint zu sein, dass Start- und Endpunkt bekannt sind. Jetzt braucht man die Weg dazwischen, um diese färben zu können. Da diese Aufgabe in der Datenbank nicht trivial ist, war die Idee einen Router einzusetzen, welcher diese IDs ermittelt.
Aber eigentlich müssen die Strecken doch schon in TMC Relationen stecken, oder? Vielleicht kann jemand mit Ahnung vom TMC Tagging sich dazu ja mal näher äußern.

Hi,
habe letztes Jahr auf der FOSSGIS und auf der AGIT jeweils einen Vortrag zu Theme OSM & TMC gehalten. Von der FOSSGIS gibt es ein Video hier zu finden:
"Untersuchung der Nutzung von OpenStreetMap Daten zur Darstellung von TMC Verkehrsmeldeinformationen"
http://wiki.openstreetmap.org/wiki/FOSSGIS_2011

Die Folien von der AGIT sind hier online:
http://www.slideshare.net/pascalneis/zu … nstreetmap

Weiterhin gibt es wie bereits erwähnt auf http://openrouteservice.org/ ein prototypisches Layer mit Icons und einem Overlay von Straßen der TMC Meldungen für ganz Deutschland.

viele gruesse
pascal

Hey Pascal, Deinen Vortrag kenne ich natürlich!

Es ist halt die Frage, ob das Verfahren skaliert. Wenn ich nur von max. 300 TMC-Meldungen pro Regiobereich (z.B. Bayern + Umland) ausgehe, dann ist das auch gut als Overlay machbar. Bei uns geht es aber um eine großfläche Abdeckung aller Autobahnen und Bundesstraßen ähnlich der Verkehrslage in Google oder ADAC Maps.
Unsere Eingangsdaten sind also nicht TMC-Meldungen, sondern basieren nur auf TMC als Ortsreferenzierung. Es ist aber nicht unwahrscheinlich, dass es in einer künftigen Ausbaustufe noch feiner wird (z.B. Nutzung von Offsets, also ein 1km Stau geht nicht von der Anschlussstelle/Ortschaft X = TMC Location zur nächsten und hat 1 km Länge, sondern beginnt z.B. 2,5 km nach der Anschlusstelle/Ortschaft).

Für das Mapping TMC Locations/OSM-Ids erstellen wir bereits (vorab) eine Mapping-Tabelle, daher sind Start-/Endpunkte bekannt und es geht (pro Kartengenerierungslauf) nur um die Errechnung der Way-Ids dazwischen.

TrafficJam wrote:

Für das Mapping TMC Locations/OSM-Ids erstellen wir bereits (vorab) eine Mapping-Tabelle, daher sind Start-/Endpunkte bekannt und es geht (pro Kartengenerierungslauf) nur um die Errechnung der Way-Ids dazwischen.

Wenn ihr die Tabelle schon habt, was spricht dagegen in der Tabelle auch noch eine Waygeometrie anzulegen de über alle Punkte der beteiligten Wege geht. Das muss man ja nur einmalig machen und dann vielleicht jeden Monat erneut. Das halte ich für performanter als wenn ihr das zu jeder Meldung rechnet. Bei Offsets wird es dann aber schon schwieriger. Aber da kommt ihr auch nicht mehr mit "ganzen" Wegids hin.

Hi,

viw wrote:

TrafficJam wrote:

Für das Mapping TMC Locations/OSM-Ids erstellen wir bereits (vorab) eine Mapping-Tabelle, daher sind Start-/Endpunkte bekannt und es geht (pro Kartengenerierungslauf) nur um die Errechnung der Way-Ids dazwischen.

Wenn ihr die Tabelle schon habt, was spricht dagegen in der Tabelle auch noch eine Waygeometrie anzulegen de über alle Punkte der beteiligten Wege geht. Das muss man ja nur einmalig machen und dann vielleicht jeden Monat erneut. Das halte ich für performanter als wenn ihr das zu jeder Meldung rechnet.

+1, genau das wollte ich jetzt auch gerade schreiben. Also so habe ich es eigentlich auch in meinen Vorträgen gemeint, bzw. so mache ich es auch.

Ansonsten gerade über die Tagging-Liste gegangen:
"Feature Proposal - TMC - New tagging scheme for TMC"
http://lists.openstreetmap.org/pipermai … 09639.html

Und hier der Vorschlag im Wiki:
http://wiki.openstreetmap.org/wiki/DE:P … TMC_scheme

Habe es mir aber noch nicht näher angschaut ...

viele gruesse
pascal

Hi,

ich weiß, man macht es nicht alte threads aufzuwecken, aber es fehlen doch einige nützliche Infos:

1. Das stimmt nicht: "Den ersten Platz belegt da ein Programm, geschrieben in purem C ... Ein solches Programm kenne ich nicht." Es gibt doch aber OSRM!? ok das ist C++ ...
2. da muss muss man aufpassen "dass da Deutschland oder Europa in den Speicher passt." Ein Java Projekt von mir, dass allerdings erstmal nur Dijkstra und A* kann, löst das Problem und nutzt für Deutschland ca 1.5GB: https://github.com/karussell/GraphHopper
3. Bzgl. A*: wenn die Abschätzung ne bestimmte Eigenschaft hat ("gut ist") liefert A* genau die gleichen Ergebnisse wie Dijkstra. Besser ist es sich Dijkstra als A* ohne Entfernungseinschätzung vorzustellen. Und in meinen Tests ist A* ca. 4 mal so schnell (fast doppelt so schnell wie mein bidirektionaler Dijkstra!)

Grüße,
Peter.

Hallo Peter,

Habe gesehen, dass du im Wiki auch schon unter "Routing" einen Eintrag für Graphhopper gemacht hast.

Wenn jemand hier auf der OSM-Mailingliste für Routing (und vielleicht auch für development) mitliest und schreibt, so könnte da eine Meldung dir auch noch Feedback bringen.

Vielleicht kommt auch noch eine Meldung in der Wochennotitz unter blog.openstreetmap.de wenn du willst.

Gruß, Stephan

Interessant.
Welche Straßentypen sind denn in den 1,5 Meg für Deutschland enthalten?
Sind diese auch segmentiert?
Welche Attribute werden aus OSM übernommen?
Sind die Straßennamen und Geometrien enthalten?
Wie sieht's mit Abbiegevorschriften und Einbahnstraßen aus?
Wie mit ShuttleTrains (Autozügen) z.B. Hindenburgdamm Sylt?

karussell wrote:

Hi,

ich weiß, man macht es nicht alte threads aufzuwecken, aber es fehlen doch einige nützliche Infos:

1. Das stimmt nicht: "Den ersten Platz belegt da ein Programm, geschrieben in purem C ... Ein solches Programm kenne ich nicht." Es gibt doch aber OSRM!? ok das ist C++ ...
2. da muss muss man aufpassen "dass da Deutschland oder Europa in den Speicher passt." Ein Java Projekt von mir, dass allerdings erstmal nur Dijkstra und A* kann, löst das Problem und nutzt für Deutschland ca 1.5GB: https://github.com/karussell/GraphHopper
3. Bzgl. A*: wenn die Abschätzung gut ist liefert A* genau die gleichen Ergebnisse wie Dijkstra. Besser ist es sich Dijkstra als A* ohne Entfernungseinschätzung vorzustellen. Und in meinen Tests ist A* ca. 4 mal so schnell (fast doppelt so schnell wie mein bidirektionaler Dijkstra!)

Grüße,
Peter.

Hi,

danke für euer feedback. Habe die Wochennotiz schon vernommen 🙂

aber für größere publicity in der OSM community ists noch nicht geeignet, da es viele Dinge noch nicht gibt (s.u.)

Welche Straßentypen sind denn in den 1,5 Meg für Deutschland enthalten?

momentan noch alle fürs auto. wichtig: 1.5GB 🙂 !

und da ist noch einiges an optimierung möglich. demnächst werde ich da aber weniger investieren, eher in speed und correctness

Sind diese auch segmentiert?

ja, leider existiert noch nicht einmal ein shortcut für eine längere straße ohne abzweigungen. als nächstes kommt aber dann tatsächlich diese shortcuts was den algorithmus viel schneller machen sollte. aber ist momentan doch schon schneller als gedacht (<0.1s für ~150km Anfragen):
https://github.com/karussell/GraphHoppe … erformance

Welche Attribute werden aus OSM übernommen?

nur auto und art des highways (für geschwindigkeit) und richtung. noch keine turnrestrictions.

Sind die Straßennamen und Geometrien enthalten?

nein, nur routing relevante dinge. später wird evtl. da noch ein suchindex in einem separaten projekt via elasticsearch entstehen. mal schauen ... das kostet dann aber nochmal 1-2GB

Wie sieht's mit Abbiegevorschriften und Einbahnstraßen aus?

einbahnstraßen ja, abbiegevorschriften nein.

Wie mit ShuttleTrains (Autozügen) z.B. Hindenburgdamm Sylt?

was meinst du damit?

Grüße,
Peter.

karussell wrote:

was meinst du damit?

Nach Sylt kommt man per Auto nur mit dem Autozug.
http://wiki.openstreetmap.org/wiki/Prop … ttle_train
Soll der Router nach Sylt routen können muss er also dieses Tag auswerten.

Edit: Der Shuttle hat den Bot wie zu erwarten nicht unbeschadet überstanden.
Während die Deutschen Polen reparieren werde ich heute dann mal Sylt reparieren 😉

Ach da gibts bei uns im Norden noch mehr ... z.B. Fähren über den Nordostseekanal

Ich will mich dann mal kurz outen, ohne dabei auf irgend welche Schlipse zu treten:
Ich bin der Irre, der osm2po programmiert hat.
Daher auch meine gezielten Fragen.
Hab mir gerade mal ein paar Eckdaten für Deutschland ausgeben lassen.

• Größe der Daten in Binärdatei (=Speicherimage): ca. 500MB
  

inklusive Strassen-Namen, -Typen, Geometrien und Abbiegevorschriften, u.a.
zudem können die Namen und Geometrien alternativ auch nachgelagert gelookupt werden, was den RAM-Bedarf nochmals auf ungefähr die Hälfte reduziert

• Rechengeschwindigkeit (@i3/4G) Hamburg-Hannover (Ohne highway=service) bei A* ca. 0,05s.
  

Einbahnstraßen, Abbiegevorschriften werden dabei allerdings bereits berücksichtig

Es gibt aber noch weitere Knackpunkte.
So z.B. eben die der Autozüge und Fähren. Will man die mit einbinden, so kommt man normalerweise nicht um die blöden Service-Strassen drumrum, was den Graphen unnötig aufpustet.
Zudem sind immer wieder einige OSM-Tagger der Meinung, dass ein Bahnübergang eine Verbindung zwischen Strasse und Schiene darstellt. Aus einer gewissen Sicht ist das ja auch so - für's Routing ist das natürlich tödlich. Während der Datenkonvertierung sorgt osm2po daher dafür, dass die Kombi Autozug-Bahnübergang-Strasse entsprechend entkoppelt wird.

Ich bin der Irre, der osm2po programmiert hat.

Aha 🙂 Hallo!

Größe der Daten in Binärdatei (=Speicherimage): ca. 500MB

respekt!

Also ich denke einfach dass ich noch viel zu viel unnötige Daten drin haben (z.B. eine straße hat ja extrem viele knoten was ja fürs routing nur für die ausgabe notwendig wird).

Weiterhin muss ich mich selbst korrigieren: auch fahrrad etc ist bei den daten drin (also nicht nur auto!). der algorithmus ist aber nur für auto optimiert - vorerst.

Rechengeschwindigkeit (@i3/4G) Hamburg-Hannover (Ohne highway=service) bei A* ca. 0,05s.

na dann ist GraphHopper doch schon ganz gut 🙂 !

Es gibt aber noch weitere Knackpunkte.

Danke für die Tipps!

Macht natürlich wenig sinn die geschwindigkeit zu vergleichen ohne die hardware zu nennen ... ich hab Intel Core 2 Duo CPU P8600 @ 2.40GHz ... und z.B. "john --test" liefert bei Traditional DES

Many␣salts:	1044K␣c/s␣real,␣1050K␣c/s␣virtual
Only␣one␣salt:	960486␣c/s␣real,␣960486␣c/s␣virtual

Also wenn da auch Fahrradwege drin sind und womöglich noch Fußwege usw. dann würde sich mein Graph auch aufblähen.
Wichtig bei der ganzen Nummer ist natürlich, die reinen Geometrie-Punkte von den echten Links (Vertices) zu trennen. Die Geometrien, Namen usw. benötigt man ja nur für die visuelle Rekonstruktion der Strecke nach erfolgter Berechnung.
Und diese Daten können dann auch gerne von Platte oder besser SSD gezogen werden.
Ok, die Geometrien braucht man auch, um z.B. nicht nur Vertices als Source und Target zu verwenden, sondern auch irgendwo auf 'ner Linie zu starten und ins Ziel zu kommen. Das kann osm2po derzeit (noch) nicht. Ist aber auch kein großes Hexenwerk. Noch'n Tipp: Habe auch mit dem bidirektionalen Dijkstra/A* rumgespielt und bin abschließend davon abgekommen. Das Problem besteht nämlich in der Möglichkeit, dass ausgerechnet der Treffpunkt eine Abbiegevorschrift haben kann, und das wieder rückwärts zu korrigieren war mir zu aktig.

Noch'n Tipp

Danke, gerne mehr 🙂 vorallem was die daten betrifft die ich weglassen kann. Ich hole momentan halt alles was "<way>" ist und ein highway tag hat, da hast du schon recht dass da noch viel optimierungspotential verschenkt wird:

https://github.com/karussell/GraphHoppe … .java#L325

Habe auch mit dem bidirektionalen Dijkstra/A* rumgespielt

habe bisher nur bi-dijkstra ... und der ist langsamer als der single a* ... aber bi-a* werde ich auf jeden fall reinbringen.

dass ausgerechnet der Treffpunkt eine Abbiegevorschrift haben kann

naja, wenn man turn restriction in den graphen reinmodelliert anstatt den algo anzupassen hat man da keine probleme... aber das reinmodellieren ist natürlich nicht das RAM schonenste .... mal schauen ... weiterhin kann ich mir da auch andere lösungen vorstellen, die mir momentan nicht so kompliziert erscheinen.

Ich würde da gar nicht so viel Energie in das Thema Optimierung hineinstecken - Hauptsache, das Teil konvertiert und routet richtig. Wichtig ist vor allem der Ansatz und die Erweiterbarkeit. Der Flaschenhals ist letztendlich Java selbst und da würde ich gar nicht erst versuchen wollen, gegen OSRM anzustinken. Da steckt 'ne komplett badisch-universitäre Abteilung hinter, die sich den lieben langen Tag mit nix anderem beschäftigt. Und den CH-Algo braucht man nur, wenn man halt viele Routen für viele User gleichzeitig rechnen will oder eben ganz abgefahrene Dinge macht. Für Deutschland ist ein simpler unidirektionaler A* völlig ausreichend - für alles andere gibt's ja Google und eben OSRM.
Die meisten Anwendungsfälle rechnen aber nur einmal und verarbeiten dann diese Ergebnisse weiter. Da spielt es keine Hupe, ob das Teil 'ne Minute oder einen Tag benötigt. Hauptsache, die Ergebnisse können mit anderen Daten aus OSM vermischt werden. Das heißt, die ursprünglichen IDs sollten bei der ganzen Routing-Arie nicht verloren gehen. Hier sehe ich eine gewisse Gefahr bei zu viel Optimierung, da eine Menge Rückwärts-Referenzen aufrecht erhalten werden müssen.
Man muss halt überlegen, wo ein "einfaches" Java-Tool seine Berechtigung hat. Und da gibt es eine ganze Menge Argumente. Ich weiß z.B. von einem Projekt, wo osm2po auf Android als Offline-Router eingesetzt wird, um damit Skigebiete und eben auch Pisten abzufahren - abgefahren, gell? Ein anderer lässt damit einen Roboter selbstständig durch die Wälder fahren und wiederum andere berechnen irgend welche Einzugsgebiete für irgend welche Einkaufszentren.

Aber bevor ich jetzt andere Zuleser nerve:
Du (und auch alle anderen) darfst mich auch gerne unter info@osm2po.de kontaktieren.

Gruß, Carsten.

pimapper wrote:

Aber bevor ich jetzt andere Zuleser nerv

Tue Dir keinen Zwang an, zumindest ich lese gerne mit

chris66 wrote:

Der Shuttle hat den Bot wie zu erwarten nicht unbeschadet überstanden.

Korrektur: Die shuttle_train Verbindung war noch in Ordnung, es waren nur zusätzlich einige Schienen
(railway=rail) mit motorcar=yes markiert, was OSRM dann für's Routing nutzt (Ist natürlich Blödsinn
denn wer fährt mit dem Auto direkt auf den Schienen).

chris66 wrote:

(Ist natürlich Blödsinn denn wer fährt mit dem Auto direkt auf den Schienen).

naja, das sehen einige ganz anders:

mach mal in google ne Bildersuche auf "Schienenauto" und du wirst dich wundern 😉

Gruss
walter

p.s. ich wäre froh, wenn ich so ein Teil hätte. Gerade um die Ecke ist eine ca 30 km lange Museumsbahn bis nach Wiesbaden rein. Damit Einkaufen fahren. Kann kein Cabrio mithalten.

Schon wieder die Polen 🤣

marek kleciak wrote:

Schon wieder die Polen 🤣

jauu, garnicht gesehen. aber es gibt massenhaft andere. Das war für mich nur das Schönste.

http://www.google.com/search?q=schienen … 15&bih=909
keine ahnung, ob der link geht.

chris66 wrote:

chris66 wrote:

Der Shuttle hat den Bot wie zu erwarten nicht unbeschadet überstanden.

Korrektur: Die shuttle_train Verbindung war noch in Ordnung, es waren nur zusätzlich einige Schienen
(railway=rail) mit motorcar=yes markiert, was OSRM dann für's Routing nutzt (Ist natürlich Blödsinn
denn wer fährt mit dem Auto direkt auf den Schienen).

Lass das lieber drin, da es früher so gehandhabt wurde und du nicht wissen kannst, welche Tools darauf noch beruhen.
Immerhin ist shuttle_train ja relativ neu.

Ein ähnliches Problem ist auch bei den Ferries zu sehen.
Eine Ferry muss laut OSM nicht zwangsläufig Autos transportieren. Hier hilft nur motorcar=yes.
Und eine "shuttle_ferry" gibt's ja nicht ;-)

mach mal in google ne Bildersuche auf "Schienenauto" und du wirst dich wundern wink

yeah 🙂 !!

Ich würde da gar nicht so viel Energie in das Thema Optimierung hineinstecken
Hauptsache, das Teil konvertiert und routet richtig. Wichtig ist vor allem der Ansatz und die Erweiterbarkeit.

Also Erweiterbarkeit ist jetzt nicht mein Hauptziel, aber ich denke durch die massigen unit tests etc ist GraphHopper ganz gut verstehbar, leicht modifizierbar, ...

Der Flaschenhals ist letztendlich Java selbst und da würde ich gar nicht erst versuchen wollen, gegen OSRM anzustinken.
Da steckt 'ne komplett badisch-universitäre Abteilung hinter, die sich den lieben langen Tag mit nix anderem beschäftigt.

also anstinken/konkurrieren o.ä. will ich überhaupt nicht. klar weiß ich das OSRM wg. C++ und dem Theorievorsprung mir meilenweit vorraus sein wird. Aber der Hauptgrund von GraphHopper ist dass es mir seltsamerweise Spaß macht an solchen Dingen/Algos zu arbeiten. Und da will ich auf jedenfall CH etc auch mal ausprobieren, tunen, fluchen, freuen 😉

Und ein paar Vorteile wie Lizenz, TDD und auch Java (android, portierbarkeit) hat GraphHopper ja auch.

Die konkrete Anwendung suche ich noch, also momentan ists wie gesagt für autos optimiert. aber evtl. wirds in zukunft eher für bahn oder bike genutzt, mal abwarten.

pimapper wrote:

Der Flaschenhals ist letztendlich Java selbst

Nur aus Interesse: kennst Du da konkrete Vergleiche/Benchmarks mit Routing in Java vs. C/C++?

karussell wrote:

Die konkrete Anwendung suche ich noch, also momentan ists wie gesagt für autos optimiert. aber evtl. wirds in zukunft eher für bahn oder bike genutzt, mal abwarten.

Also, ich suche immer noch einen wirklich guten Rad-Routenplaner, der flexibel konfigurierbar und anpassbar ist 😉

So in die Richtung:
http://openrouteservice.org/ - mehrere Rad-Profile + Rad-Routen bevorzugen
http://www.routino.org/uk/router.html - konfigurierbar
http://igf-project.igf.uos.de/fahrradies/ - mehrere Rad-Profile + Profileditor
http://www.komoot.de/ - berechnet Rundtour (im Idealfall) mit POIs

Nur halt eine Mischung aus allen, Open Source und bevorzugt in Java.

Mit Berücksichtigung (bevorzugen/vermeiden) von:
- neben highway weitere Tags wie tracktype, surface,...
- Steigung
- Wanderwege und Radrouten (route Relationen)
- Umgebung/POIs, z.B. "im Wald", "am Wasser entlang", Aussichtspunkte
- ...

Gruß,
Norbert

opentripplaner ist so ein multiple attribute routing engine. evtl. geht das ja schon für dich? (BTW: opentripplaner braucht relativ viel RAM)

Nur aus Interesse: kennst Du da konkrete Vergleiche/Benchmarks mit Routing in Java vs. C/C++?

generell kann man sagen dass C/C++ ca. 2-3 mal schneller ist und weniger RAM braucht. wieviel weniger es braucht hängt davon ab (grob gesagt) wie viel man von den object oriented features in java nutzt.

karussell wrote:

opentripplaner ist so ein multiple attribute routing engine. evtl. geht das ja schon für dich?

Danke. Den hatte ich mir auch schon vorgemerkt, falls ich tatsächlich selbst mal selbst zu basteln anfange. Das reine Radrouting auf trimet.org hat mich aber noch nicht so überzeugt.

also reines radrouting sollte mit graphhopper schon jetzt (mit minimalen aufwand) möglich sein, jedoch gibts von deiner seite her ja viel mehr anforderungen 🙂

Also, ich suche immer noch einen wirklich guten Rad-Routenplaner, der flexibel konfigurierbar und anpassbar ist wink
So in die Richtung:
http://openrouteservice.org/ - mehrere Rad-Profile + Rad-Routen bevorzugen

was sind rad profile? und wie sind rad routen in OSM gespeichert?

http://www.komoot.de/ - berechnet Rundtour (im Idealfall) mit POIs

aha, aber das ist ja dann eher traveling salesman als shortest path 🙂

karussell wrote:

was sind rad profile? und wie sind rad routen in OSM gespeichert?

(a) z.B. Profil MTB-Rad oder Rennrad
(b) als Relation mit type=route, route=bicycle

karussell wrote:

jedoch gibts von deiner seite her ja viel mehr anforderungen 🙂

Ich hatte einfach mal laut geträumt, in der Hoffnung, dass sich evtl. jemand für die Umsetzung begeistern kann 😉

chris66 wrote:

karussell wrote:

was sind rad profile? und wie sind rad routen in OSM gespeichert?

(a) z.B. Profil MTB-Rad oder Rennrad

Also im Prinzip Fahrzeug/Nutzer-Typen, für die es bestimmte Präferenzen gibt. D.h. für die jeweils eine spezielle Gewichtung z.B. je highway Tag hinterlegt ist. Im Wiki hat sich zum Beispiel mal jemand Gedanken zu Routing profiles gemacht.

chris66 wrote:

(b) als Relation mit type=route, route=bicycle

Zu sehen z.B. bei http://opencyclemap.org/ oder http://cycling.waymarkedtrails.org/de

ikonor wrote:

karussell wrote:

jedoch gibts von deiner seite her ja viel mehr anforderungen 🙂

Ich hatte einfach mal laut geträumt, in der Hoffnung, dass sich evtl. jemand für die Umsetzung begeistern kann 😉

chris66 wrote:

karussell wrote:

was sind rad profile? und wie sind rad routen in OSM gespeichert?

(a) z.B. Profil MTB-Rad oder Rennrad

Also im Prinzip Fahrzeug/Nutzer-Typen, für die es bestimmte Präferenzen gibt. D.h. für die jeweils eine spezielle Gewichtung z.B. je highway Tag hinterlegt ist. Im Wiki hat sich zum Beispiel mal jemand Gedanken zu Routing profiles gemacht.

chris66 wrote:

(b) als Relation mit type=route, route=bicycle

Zu sehen z.B. bei http://opencyclemap.org/ oder http://cycling.waymarkedtrails.org/de

Aber würde mich doch jetzt glatt mal interessieren, was ein sinnvolles Rad-Routing überhaupt ist.
Annahme: Man ignoriert, motorways und trunks. Nimmt an, dass man secondaries und tertiaries befahren kann. Residentials sowieso. Geht davon aus, dass Fahrradfahrer für gewöhnlich notfalls auch Einbahnstraßen ignorieren, von Abbiegevorschriften ganz zu schweigen... evtl. notfalls auch den Fußweg nehmen oder auf Schotterpisten fahren, jedoch Matschwege (Grade5) doch lieber Wanderern mit Gummistiefeln überlassen .... hmmm.... ????
Was ist also Radrouting?

pimapper wrote:

Was ist also Radrouting?

Kommt drauf an ob legal oder, wie Du schreibst, Einbahnstraßen ignoriert werden. Der Rest ist eine Frage des Malus/Bonus Systems. Wobei da nicht nur Wege (u.A. Primary und Steps hast Du in Deiner Aufzählung vergessen) oder Eigenschaften von Ways (bspw cobblestone) sondern auch Nodes (bspw cycle barrier) berücksichtigt werden müssen.
aighes ist hier einer der Experten dafür. Falls er nicht mitliest, schreib ihn mal an

pimapper wrote:

Aber würde mich doch jetzt glatt mal interessieren, was ein sinnvolles Rad-Routing überhaupt ist.
Annahme: Man ignoriert, motorways und trunks. Nimmt an, dass man secondaries und tertiaries befahren kann. Residentials sowieso. Geht davon aus, dass Fahrradfahrer für gewöhnlich notfalls auch Einbahnstraßen ignorieren, von Abbiegevorschriften ganz zu schweigen... evtl. notfalls auch den Fußweg nehmen oder auf Schotterpisten fahren, jedoch Matschwege (Grade5) doch lieber Wanderern mit Gummistiefeln überlassen .... hmmm.... ????
Was ist also Radrouting?

Es gibt nicht ein Radrouting sondern viele, je nach den Bedürfnissen der unterschiedlichen Radfahrergruppen.

Beim Garmin Oregon z.B. gibt es Cycling, Tour_Cycling und Mountain_Biking.
Beim Mio Cyclo 300 gibt es Stadtrad, RennRad und Mountainbike.

Nach meiner Meinung gibt es mindestens vier Nutzertypen.
- Stadtrad: Liebt es gemütlich und sicher, kein sportlicher Ehrgeiz.
Bevorzugt Radwege und Seitenstraßen.
- Rennrad: Liebt es schnell zu fahren, oft auch mit sportlichen Ehrgeiz.
Bevorzugt glatte Straßen und Wege.
- Mountainbike: Nimmt auch mal gerne kleine schwierige Wege.
Wirtschafts- und Waldwege sind kein Problem.
- Tourenfahrer: Fährt gerne Strecken abseits der großen Straßen.
Feld- und Waldwege (grade=1/2, zum Teil grade=3) sind kein Problem.
Ein Mittelding zwischen Rennrad (Strecke) und MTB (muss nicht alles glatt sein).

Es gibt natürlich nicht "den" MTBler, da gibt es viele Abstufungen, vom Tourenfahrer, der auch mal schwierige Wege fahren will, bis zum Downhill-Freak.

Edbert (EvanE)

Kernfrage: Macht es da eigentlich noch Sinn über "Routing" zu diskutieren?
Ich meine, ein Routing soll mir ja helfen, den schnellsten oder kürzesten Weg von A nach B zu finden.
Ob es geeignet ist, möglichst viele Umwege zu fahren, damit bestimmte Matschpisten möglichst dreimal umrundet werden und danach zur nächstgelegenen Dusche zu routen...
Ich denke, dass es sinnvoll ist, ein Fahrrad als Verkehrsmittel zu betrachten. Nicht unbedingt als Sportgerät.

.

mmd wrote:

Wie sieht's mit Höhenmetern aus? Bisher habe ich noch keinen guten Router gefunden, bei dem ich Start-/Endpunkt sowie einen gewünschten Bereich an Höhenmetern (min/max) definieren kann und dann automatisch passende Routen vorgeschlagen werden. OSRM bspw.

Der einzige Router, den ich kenne, der Rundkurse vorschlägt, ist http://www.komoot.de/

Beim MTB-Profil gibt es eine "Alpin"-Einstellung, weiß aber nicht, ob das jetzt Höhenmeter meint oder nur Pfade bevorzugt. Ich komme mit Komoot allerdings nicht so klar, liefert mir zu viele Vorschläge mit Rückweg auf gleicher Strecke und ist mir zu sehr auf abklappern von POIs fixiert.

Eine Alternative ist die Suche bei einem Tourenportal, z.B. http://www.gpsies.com/trackList.do mit u.a. Länge von/bis und Gesamtanstieg von/bis.

Gruß,
Norbert

pimapper wrote:

Kernfrage: Macht es da eigentlich noch Sinn über "Routing" zu diskutieren?

Ja, zumindest ein Teil der Anforderungen ist bestimmt auch mit einem normalen Routing-Algo zu lösen. Wir können es von mir aus aber auch "softwaregestützte Freizeit-Tourenplanung" nennen. 😉

pimapper wrote:

Ich meine, ein Routing soll mir ja helfen, den schnellsten oder kürzesten Weg von A nach B zu finden.

Mir nicht. Mir soll es helfen, den ruhigsten und schönsten Weg von A über B, C und D wieder zurück nach A zu finden. Umwege nehme ich in Kauf. Die Zwischenpunkte setze ich im einfachen Fall so lange selbst, bis das Ergebnis passt. Zwischen den Punkten ist es jeweils wieder A nach B Routing mit Gewichtung zusätzlich zur Länge/Geschwindigkeit. Und je passender das Routing, desto weniger Zwischenpunkte muss ich setzen, um die Route zu korrigieren.

pimapper wrote:

Ich denke, dass es sinnvoll ist, ein Fahrrad als Verkehrsmittel zu betrachten. Nicht unbedingt als Sportgerät.

Da machst Du es Dir als Entwickler halt einfach, blendest damit aber die Zielgruppe der Outdoor-Navis aus.

Ich gebe zu, es ist nicht einfach zu definieren, was z.B. "ruhig" und "schön" ist und jeder hat da andere Vorstellungen. Deshalb wäre für mich ein guter Rad/Freizeit-Router vor allem eines: konfigurierbar. Zum Beispiel wie bei Routino oder den verschiedenen Garmin-Karten.

Gruß,
Norbert

pimapper wrote:

Kernfrage: Macht es da eigentlich noch Sinn über "Routing" zu diskutieren?
Ich meine, ein Routing soll mir ja helfen, den schnellsten oder kürzesten Weg von A nach B zu finden.
Ob es geeignet ist, möglichst viele Umwege zu fahren, damit bestimmte Matschpisten möglichst dreimal umrundet werden und danach zur nächstgelegenen Dusche zu routen...
Ich denke, dass es sinnvoll ist, ein Fahrrad als Verkehrsmittel zu betrachten. Nicht unbedingt als Sportgerät.

Ja es macht Sinn, auch Routing für den Freizeit-Bereich vorzusehen.
Schließlich ist das beim Radfahren und Wandern oft der Hauptzweck. Beim Auto mag das anders sein, aber schon die Motorradfahrer wünschen sich auch die Berücksichtigung/Bevorzugung von 'schönen' Strecken.

Beim Radfahren sind die Wünsche je nach Ausprägung (Stadt, Tour, MTB, Rennrad) sehr unterschiedlich. Und in der Freizeit sind Rundtouren durchaus gewünscht. Schließlich will man oft am Ende seiner Tour wieder zurück nach Hause. Und was die Höhenmeter und die Steilheit angeht sind die Wünsche durchaus verschieden. Der Eine will möglichst wenige und wenn dann sanfte Anstiege (z.B. Familien-Ausflug), während das für den Anderen gerade die sportliche Herausforderung ist (z.B. Rennrad, MTB).

Edbert (EvanE)

Weichen wir jetzt nicht ein wenig vom eigentlichen Thema Java-Bibliothek für Routing gesucht ab?

Natürlich kann ein normaler Router die Kosten aufgrund von Straßenbeschaffenheiten bewerten und entsprechend die "schönsten" Strecken wählen, wenn diese z.B. nicht länger als z.B. Faktor 1.5 der kürzesten Strecke sind. Das sollte eigentlich jeder Router können.
Ist nur eine Frage der Bewertung der Weg-Typen.

Die meisten der obigen Fragestellungen sind Sonderlocken.
z.B. Aneinanderkettungen von Teil-Routen, manuelle Eingriffsmöglichkeiten oder eben Rundreiseprobleme (TSP).

pimapper wrote:

Die meisten der obigen Fragestellungen sind Sonderlocken.
z.B. Aneinanderkettungen von Teil-Routen, manuelle Eingriffsmöglichkeiten oder eben Rundreiseprobleme (TSP).

Nun ja, es gibt einfach die Frage ein Ausgangs-/Endpunkt und eine Rundstrecke mit xx km oder yy Stunden usw. Das Mio-Cyclo hat so eine Funktion (SurpriseMe Modus) implementiert. Das hat nun wenig mit dem Traveling Salesman Problem (Optimierung der Reihenfolge vorgegebener Anlaufpunkte) zu tun. Hier ist nur ein Punkt festgelegt.

Edbert (EvanE)

pimapper wrote:

Weichen wir jetzt nicht ein wenig vom eigentlichen Thema Java-Bibliothek für Routing gesucht ab?

Ich will das jetzt auch nicht weiter vertiefen. Ich wollte nur die Gelegenheit nutzen - wenn schon mal zwei Autoren da sind - und Werbung für ein Anwendungsgebiet machen, das im Gegensatz zur Autonavigation noch nicht so gut abgedeckt ist.

Und um zurück zum Thema zu kommen:

@TrafficJam: seit ihr mit GeoTools noch klargekommen oder habt ihr was anderes verwendet?

Gruß,
Norbert

Weichen wir jetzt nicht ein wenig vom eigentlichen Thema Java-Bibliothek für Routing gesucht ab?

Nö, oder 🙂 ? Was heißt denn Routing? Nur kürzesten/schnell Wege?

Ich denke, es sind eher "beste" Wege und da ist multi-attribute halt das allgemeinste und (noch) kompliziertere ... allerdings sobald mehr als 2 (oder 3) punkte involviert sind tritt der traveling salesman auf, was dann für mich ne andere problemstellung als routing wäre...

aber danke allen für den input 🙂 !

so ne fahrradgeschichte, am besten kombiniert mit DB, wäre cool und ist durch nen trick auch praktisch möglich. mal schauen was die nächsten monate so bringen.

karussell wrote:

...
Ich denke, es sind eher "beste" Wege und da ist multi-attribute halt das allgemeinste und (noch) kompliziertere ... allerdings sobald mehr als 2 (oder 3) punkte involviert sind tritt der traveling salesman auf, was dann für mich ne andere problemstellung als routing wäre...
...

Ich glaube du verwechselt da zwei Dinge:
- Traveling Salesman (T-S) hat als Aufgabenstellung:
Ich will x Punkte anfahren, suche mir die günstigste Reihenfolge
mit der insgesamt optimalen (nach den vorgegebenen Kritereien)
Route heraus. (Oft auch mit Rückkehr zum Startpunkt)
- 'Normales' Routing hat als Aufgabenstellung:
Ich will von A nach E mit den Zwischenpunkten B, C und D.

Der Unterschied ist bei T-S ist die Reihenfolge der Punkte variabel (und zu optimieren), während beim normalen Routing die Reihenfolge der Zwischenpunkte vorgegeben ist. Sofern der Abstand (Luftlinie) zwischen zwei aufeinanderfolgenden Punkten geringer ist als der Abstand zwischen den Endpunkten, dürfte dies das Routing sogar erleichtern, da kürzere Teilstrecken zu berechnen sind.

Selbst bei Rundstrecken dürfte sich die Berechnung vereinfachen, da die Unterteilug in mehrere Teilstrecken die Komplexität reduziert.

Edbert (EvanE)

Ich glaube du verwechselt da zwei Dinge:

nee, meinte ich so. nur hatte ich es so verstanden dass man bei bestimmten POI vorbei will und die reihenfolge eben nicht fest steht. egal ...

karussell wrote:

Ich glaube du verwechselt da zwei Dinge:

nee, meinte ich so. nur hatte ich es so verstanden dass man bei bestimmten POI vorbei will und die reihenfolge eben nicht fest steht. egal ...

Aus meiner Erfahrung mit Outdoor-Navis kenne ich nur die Variante mit der festgelegten Reihenfolge. Ob es PKW-Navis gibt, die auch die Reihenfolge optimieren können (dann wirklich das Travelling Salesman Problem), entzieht sich meiner Kenntnis.

Edit: Wir meinte beide schon das Richtige. Nur in der Frage der Reihenfolge hatten wir unterschiedliche Voraussetzungen und kamen daher zu anderen Schlußfolgerungen.

Edbert (EvanE)