Java-Bibliotheken für Routing gesucht

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?

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.

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

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.