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
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.
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.
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.
ich weiß, man macht es nicht alte threads aufzuwecken, aber es fehlen doch einige nützliche Infos:
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++ …
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
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!)
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.
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?
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/GraphHopper/wiki/Performance
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?
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
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.
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.
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.
Danke, gerne mehr vorallem was die daten betrifft die ich weglassen kann. Ich hole momentan halt alles was “” ist und ein highway tag hat, da hast du schon recht dass da noch viel optimierungspotential verschenkt wird:
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.
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).
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.
