Java-Bibliotheken für Routing gesucht

TrafficJam · 2012-03-23 11:50:03

Ich suche eine Java-API/Bibliothek, mit der ich eine Route berechnen kann.

Genauer gesagt:
Unser Programm ermittelt die OSM-Ids eines Start- und Endpunktes (sogar immer auf einer Straße) und wir suchen die Menge aller way-Ids, die dazwischen liegen. Leider haben sich unsere eigenen Versuche (über relations zu gehen) als nicht zuverlässig erweisen, weil viele Straßen nur als ungeordnete Menge von ways im Datenmodell hinterlegt sind.

Wir haben auch schon auf http://wiki.openstreetmap.org/wiki/Routing und http://wiki.openstreetmap.org/wiki/Develop/Frameworks nachgesehen, aber die meisten Tools sind entweder eigenständige Anwendung (keine Lib, die man einfach in den Java-Code integrieren kann) oder benötigen spezielle Datenbankstrukturen.
Wir nutzen die Standard-PostGIS-DB-Struktur und mapnik als Renderer.

Habt Ihr irgendwelche Tipps?

Last edited by TrafficJam (2012-03-23 11:50:30)

kerosin · 2012-03-23 12:18:30

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

!i! · 2012-03-23 13:41:33

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?

TrafficJam · 2012-03-23 15:37:23

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

errt · 2012-03-23 15:48:49

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.

TrafficJam · 2012-03-23 16:10:20

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.

!i! · 2012-03-23 16:43:46

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.

errt · 2012-03-23 16:44:40

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.

pimapper · 2012-03-24 11:19:12

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.

Last edited by pimapper (2012-03-24 12:03:23)

ikonor · 2012-03-24 11:48:04

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

pimapper · 2012-03-24 12:19:09

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.

ikonor · 2012-03-24 12:33:20

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

pimapper · 2012-03-24 12:38:12

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.

TrafficJam · 2012-03-27 15:19:18

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.

viw · 2012-03-27 16:33:19

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.

Last edited by viw (2012-03-27 16:33:45)

TrafficJam · 2012-03-28 14:53:31

>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...

!i! · 2012-03-28 15:16:55

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.

viw · 2012-03-28 15:30:01

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)

Last edited by viw (2012-03-28 15:30:31)

!i! · 2012-03-28 18:36:59

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?

viw · 2012-03-28 21:58:03

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.

pitscheplatsch · 2012-03-29 09:55:37

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

TrafficJam · 2012-03-29 14:58:25

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.

viw · 2012-03-29 16:31:50

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.

pitscheplatsch · 2012-03-29 16:48:08

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

karussell · 2012-07-26 22:03:42

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.

Last edited by karussell (2012-08-08 11:12:59)

Announcement

#1 2012-03-23 11:50:03

Java-Bibliotheken für Routing gesucht

#2 2012-03-23 12:18:30

Re: Java-Bibliotheken für Routing gesucht

#3 2012-03-23 13:41:33

Re: Java-Bibliotheken für Routing gesucht

#4 2012-03-23 15:37:23

Re: Java-Bibliotheken für Routing gesucht

#5 2012-03-23 15:48:49

Re: Java-Bibliotheken für Routing gesucht

#6 2012-03-23 16:10:20

Re: Java-Bibliotheken für Routing gesucht

#7 2012-03-23 16:43:46

Re: Java-Bibliotheken für Routing gesucht

#8 2012-03-23 16:44:40

Re: Java-Bibliotheken für Routing gesucht

#9 2012-03-24 11:19:12

Re: Java-Bibliotheken für Routing gesucht

#10 2012-03-24 11:48:04

Re: Java-Bibliotheken für Routing gesucht

#11 2012-03-24 12:19:09

Re: Java-Bibliotheken für Routing gesucht

#12 2012-03-24 12:33:20

Re: Java-Bibliotheken für Routing gesucht

#13 2012-03-24 12:38:12

Re: Java-Bibliotheken für Routing gesucht

#14 2012-03-27 15:19:18

Re: Java-Bibliotheken für Routing gesucht

#15 2012-03-27 16:33:19

Re: Java-Bibliotheken für Routing gesucht

#16 2012-03-28 14:53:31

Re: Java-Bibliotheken für Routing gesucht

#17 2012-03-28 15:16:55

Re: Java-Bibliotheken für Routing gesucht

#18 2012-03-28 15:30:01

Re: Java-Bibliotheken für Routing gesucht

#19 2012-03-28 18:36:59

Re: Java-Bibliotheken für Routing gesucht

#20 2012-03-28 21:58:03

Re: Java-Bibliotheken für Routing gesucht

#21 2012-03-29 09:55:37

Re: Java-Bibliotheken für Routing gesucht

#22 2012-03-29 14:58:25

Re: Java-Bibliotheken für Routing gesucht

#23 2012-03-29 16:31:50

Re: Java-Bibliotheken für Routing gesucht

#24 2012-03-29 16:48:08

Re: Java-Bibliotheken für Routing gesucht

#25 2012-07-26 22:03:42

Re: Java-Bibliotheken für Routing gesucht

Board footer