Java-Bibliotheken für Routing gesucht

stephan75 · 2012-07-27 14:55:10

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

pimapper · 2012-08-06 19:24:37

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.

Last edited by pimapper (2012-08-06 19:26:26)

karussell · 2012-08-07 20:16:50

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.

Last edited by karussell (2012-08-07 20:17:36)

chris66 · 2012-08-07 20:48:50

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

Last edited by chris66 (2012-08-08 09:14:55)

kerosin · 2012-08-08 06:16:38

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

pimapper · 2012-08-08 10:02:26

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.

Last edited by pimapper (2012-08-08 10:14:41)

karussell · 2012-08-08 11:08:03

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

Last edited by karussell (2012-08-08 11:09:20)

karussell · 2012-08-08 11:29:23

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

pimapper · 2012-08-08 12:15:32

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.

karussell · 2012-08-08 13:57:28

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

pimapper · 2012-08-08 16:24:06

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.

SunCobalt · 2012-08-08 17:29:04

pimapper wrote:

Aber bevor ich jetzt andere Zuleser nerv

Tue Dir keinen Zwang an, zumindest ich lese gerne mit

chris66 · 2012-08-09 08:28:22

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

wambacher · 2012-08-09 08:48:01

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.

Last edited by wambacher (2012-08-09 08:51:52)

marek kleciak · 2012-08-09 08:49:52

Schon wieder die Polen

wambacher · 2012-08-09 08:53:33

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.

Last edited by wambacher (2012-08-09 08:55:06)

pimapper · 2012-08-09 11:55:06

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 ;-)

karussell · 2012-08-09 13:31:44

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

ikonor · 2012-08-10 12:44:16

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

karussell · 2012-08-10 14:24:46

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.

ikonor · 2012-08-10 16:48:00

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.

karussell · 2012-08-12 22:03:46

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

chris66 · 2012-08-12 22:54:17

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

ikonor · 2012-08-13 10:55:02

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

pimapper · 2012-08-17 20:16:58

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?

Announcement

#26 2012-07-27 14:55:10

Re: Java-Bibliotheken für Routing gesucht

#27 2012-08-06 19:24:37

Re: Java-Bibliotheken für Routing gesucht

#28 2012-08-07 20:16:50

Re: Java-Bibliotheken für Routing gesucht

#29 2012-08-07 20:48:50

Re: Java-Bibliotheken für Routing gesucht

#30 2012-08-08 06:16:38

Re: Java-Bibliotheken für Routing gesucht

#31 2012-08-08 10:02:26

Re: Java-Bibliotheken für Routing gesucht

#32 2012-08-08 11:08:03

Re: Java-Bibliotheken für Routing gesucht

#33 2012-08-08 11:29:23

Re: Java-Bibliotheken für Routing gesucht

#34 2012-08-08 12:15:32

Re: Java-Bibliotheken für Routing gesucht

#35 2012-08-08 13:57:28

Re: Java-Bibliotheken für Routing gesucht

#36 2012-08-08 16:24:06

Re: Java-Bibliotheken für Routing gesucht

#37 2012-08-08 17:29:04

Re: Java-Bibliotheken für Routing gesucht

#38 2012-08-09 08:28:22

Re: Java-Bibliotheken für Routing gesucht

#39 2012-08-09 08:48:01

Re: Java-Bibliotheken für Routing gesucht

#40 2012-08-09 08:49:52

Re: Java-Bibliotheken für Routing gesucht

#41 2012-08-09 08:53:33

Re: Java-Bibliotheken für Routing gesucht

#42 2012-08-09 11:55:06

Re: Java-Bibliotheken für Routing gesucht

#43 2012-08-09 13:31:44

Re: Java-Bibliotheken für Routing gesucht

#44 2012-08-10 12:44:16

Re: Java-Bibliotheken für Routing gesucht

#45 2012-08-10 14:24:46

Re: Java-Bibliotheken für Routing gesucht

#46 2012-08-10 16:48:00

Re: Java-Bibliotheken für Routing gesucht

#47 2012-08-12 22:03:46

Re: Java-Bibliotheken für Routing gesucht

#48 2012-08-12 22:54:17

Re: Java-Bibliotheken für Routing gesucht

#49 2012-08-13 10:55:02

Re: Java-Bibliotheken für Routing gesucht

#50 2012-08-17 20:16:58

Re: Java-Bibliotheken für Routing gesucht

Board footer