Routenplaner, Umkreissuche nach Fahrzeit

[joschilein]

Hat jemand eine Idee, wie man mit einer Routenplaner-API und einem gegebenen Startpunkt eine Fläche / einen Umkreis / viele Grenzpunkte erzeugen kann, mit dem ein Abstand von z.B. einer Stunde Fahrzeit angezeigen kann? Ausgabe dann z.B. in GoogleEarth.

Oder noch viel besser: Gibt es das schon irgendwo?

Ich habe mir schon öfters darüber Gedanken gemacht. Das größte Problem das ich sehe: Man kann einer API wohl schlecht sagen "Fahre die Straße mal 500m weiter und sage mir dann wie lange die Fahrzeit ist". Ich habe mal irgendwann angefangen das manuell zu machen und bin über mehrere Etappen auf bisher ca. 180° gekommen. Die zweite Hälfte fehlt also noch. Aber seitdem sind bestimmt schon irgendwo mal ein paar Umgehungsstraßen gebaut worden und das Ergebnis sähe schon wieder ganz anders aus.

Könnte man aber über das hinterlegte Koordinatengitter navigieren, wäre das aber doch recht gut möglich. Wenn ein Knoten z.B. 59 min entfernt ist geht man dessen 3 weitere Pfade bis zu deren Knoten und fragt dort wieder*. Hat man einen mit >60 min, liegt die Grenze zwischen diesen beiden Knoten.

*ggf. ist die Zeit über eine andere Route schon wieder kürzer.

Mir ist übrigens auch bewusst, dass es in der Grenzregion "Inseln" geben könnte, die eigentlich außerhalb des Zeitbereichs liegen, aber von der äußeren Grenze der zulässigen Fläche eingeschlossen wären, z.B. ein Waldgebiet mit langsamen Pfaden, während drumherum eine Schnellstraße führt. Die Inseln sind mir nicht so wichtig.

[theHacker]

Eine Idee von mir

Bekannt:
Bekannt ist eine Durchschnittgeschwindigkeits v, die du zu Grunde legst.
Außerdem gibst du dir eine Zeit t vor, die du maximal fahren willst.

Vorbereitung:
Ermittle Kreis um deinen Startpunkt S mit Radius v*t. Damit hast du eine ungefähre Näherung deiner Lösung, die aber viel zu ungenau ist. Jetzt mach aus dem Kreis einen Ring, indem du plusminus am Radius spielst.

Statistischer Ansatz:

Zitat von joschilein

Man kann einer API wohl schlecht sagen "Fahre die Straße mal 500m weiter und sage mir dann wie lange die Fahrzeit ist".

Richtig, das geht nicht. Mach es umgekehrt. Nimm dir aus dem o.g. Ring zufällig Punkte X aus frag die API, wie lang es von X nach S dauert. Ist die Fahrdauer kleiner als t, dann X als Lösung markieren; sonst X als Nicht-Lösung markieren.

Ziehe solange Punkte, bis eine ausreichende Genauigkeit erreicht wird, d.h. du keine neuen Erkenntnisse mehr von der API kriegst. Praktisch gibts ja nur ne sehr begrenzte Menge von Straßen, die du fahren kannst, egal wie viele Punkte du ziehst.

Deine Lösungsmenge ist ein Polygon, was von den als Lösung markierten Punkten aufgespannt wird (ich lass die Schwierigkeit außer Acht, dass du dir nur die "äußeren" Punkte für das Polygon raussuchen musst ).

[joschilein]

Also du würdest quasi rein geometrisch vorgehen und pro Winkelstellung so lange suchen, bis ein grüner (noch drin) und ein roter (schon draußen) Punkt gefunden ist? Wenn ich mir das bildlich vorstelle ist das also ein Mehroderweniger-Kreis, dessen rot-grün-Paare immer zum Zentrum zeigen. Und klar, die grünen könnte man dann z.B. zu einem Pfad verbinden.

Wenn ich mir jetzt aber mal mein bisheriges Praxisergebnis anschaue, könnte es schon Probleme geben. Die Grenze liegt momentan zwischen 28 und 64 km Luftlinie (in noch freien Winkeln könnte es wegen Autobahnen noch mehr werden). In der Winkelstellung mit den 28 km gibt es selbst ohne Inselproblem mehrere Grenzen. Die gültige Fläche befindet sich a) bis 28,1 b) 31,5-32,5 c) 40,6-43,5 und d) 46,8-51,9. Und es gibt natürlich auch noch einige andere Stellen, die wegen den nicht-radialen Straßenverläufen zu den von Ländergrenzen bekannten "Unregelmäßigkeiten" führen.

Weiteres Problem: Wenn ich einer Api eine Koordinate gebe ohne zu wissen was sich dort befindet, springt sie doch häufig zur nächstgelegenen Straße. Bekomme ich dann auch die Koordinate des "neuen" Punktes, über den ich die Information (Entfernung, Zeitangabe) erhalte? (Habe mich noch nicht in die verschiedenen Apis eingelesen).

Jetzt fällt mir eigentlich nur eine wirklich sinnvolle Vorgehensweise ein. Man schmeißt quasi ein Koordinatengitter um den Startpunkt, prüft für jeden Punkt dessen Werte und markiert ihn damit rot oder grün. Am Ende werden dann alle Punkte gelöscht, die von Punkten ihrer eigenen Farbe umschlossen sind und übrig bleiben alle Grenzpunkte inklusive der Inseln. Und um deren Koordinaten könnte man dann noch mal feinmaschigere Koordinaten werfen, damit die Grenze detaillierter wird.

[theHacker]

Zitat von joschilein

Also du würdest quasi rein geometrisch vorgehen und pro Winkelstellung so lange suchen, bis ein grüner (noch drin) und ein roter (schon draußen) Punkt gefunden ist?

Viel Optionen hast du ja nicht, wenn du eine API nutzen willst, die dein Problem so nicht unterstützt.

Optimalerweise baust du dir selber den Graph auf (z.B. OpenStreetMap), hast entsprechende Kanten mit Streckenlänge-/Zeitaufwand-Gewichten und implementierst einen entsprechenden Tiefen- oder Breitensuche-Algorithmus, der deine Lösung optimal bestimmt.

Zitat von joschilein

Die Grenze liegt momentan zwischen 28 und 64 km Luftlinie (in noch freien Winkeln könnte es wegen Autobahnen noch mehr werden).

Das hätt ich befürchtet. In diesem Fall also kein Ring, sondern eben Worst-Case der ganze Inkreis.

Zitat von joschilein

In der Winkelstellung mit den 28 km gibt es selbst ohne Inselproblem mehrere Grenzen.

Mehrere Grenzen sind aber auch praktisch drin. Stell dir zwei parallele Straßen vor (die im Abstand von 10 Meter sind), wo die eine Autobahn mit 130km/h und die andere ne Ackerstraße mit 50km/h is. Genau so entsteht das Problem. Hier würd ich halt n Maximum anwenden, weil du ja die Wahl hast, welche Straßen du benutzt.

Zitat von joschilein

Weiteres Problem: Wenn ich einer Api eine Koordinate gebe ohne zu wissen was sich dort befindet, springt sie doch häufig zur nächstgelegenen Straße. Bekomme ich dann auch die Koordinate des "neuen" Punktes, über den ich die Information (Entfernung, Zeitangabe) erhalte? (Habe mich noch nicht in die verschiedenen Apis eingelesen).

Das merkst du an der Webbeschreibung. Jede API muss dich ja irgendwie auf eine Straße lenken, wenn du n Punkt in der Prärie angibst. Hast du als nächsten Wegpunkt bei mehreren Routen denselben Punkt, weißt du, dass deine Zufallspunkte zu nah beieinander liegen.

Zitat von joschilein

Jetzt fällt mir eigentlich nur eine wirklich sinnvolle Vorgehensweise ein. Man schmeißt quasi ein Koordinatengitter um den Startpunkt, prüft für jeden Punkt dessen Werte und markiert ihn damit rot oder grün.

Is aber ja auch nix anderes als mein Vorschlag. Bedenke: Wenn du - wie von mir beschrieben - einen Zufallspunkt ziehst, so passt die Koordinate ja auch in ein bestimmtes Gitter. Wenn ich z.B.

PHP-Code:

1:

$lat = (int)(rand() * 180000) / 1000 - 90;  // rand() -> 0...1

mach, so hab ich n Gitter mit Abstand 0,001°.

Deine Variante gibt nur spezifischer vor, dass eben alle Punkte durchprobiert werden und nicht - wie bei mir - nur ne bestimmte Anzahl.

[thrown-out]

openrouteservice hat ein feature namens erreichbarkeitsanalyse, das sollte das sein, was du suchst, oder?

[ice-breaker]

Also ich würde es wie theHacker machen und die Straßenkarte als Graphen abbilden bei denen die Kanten aus den Eigenschaften (Fahrzeit, Strecke, Geschwindigkeit).
Die Fahrzeit ist dabei eine veränderliche Größe, diese gibt an mit welcher Fahrzeit man bisher am schnellsten dieses Streckenstück seit Beginn der Fahrzeit befahren konnte.

Als Algorithmus würde ich mir dann den Dijkstra vornehmen und modifizieren, so dass jeweils an den Knoten auf Kanten weitergefahren wird, die die geringste Fahrzeit haben, so löst sich auch das von theHacker in #4 beschriebene Problem von 2 parallelen Straßen mit verschiedener Geschwindigkeit (die langsame Strecke wird nach 1 Iteration nicht mehr benutzt werden).


Alles keine leichte Aufgabe und den Algorithmus zu entwickeln wird wahrscheinlich viel Feintuning benötigen (Fehler und Laufzeit).

Da wäre es möglicherweise einfacher das Modell zu vereinfachen und einfach eine Umkreissuche anhand einer definierten mittleren Geschwindigkeit v zu machen. Die Geschwindigkeit v könnte sich an das Startgebiet anpassen: Beginnt die Suche in einer Innenstadt mit nur 5 Minuten Fahrzeit, kann man von einem normalen mittleren Tempo für eine Innenstadt ausgehen. Starte ich jedoch auf einer Autobahn, ist die Geschwindigkeit höher. Startet man in der Nähe einer Landstraße oder Autobahn aber in einer Innenstadt so könnte man 2 Umkreissuchen nutzen: Eine normale Kreisförmige mit einem Radius für Stadtgeschwindigkeit und eine Umkreissuche mit einem Bogenmaß von 90° dessen Mitte in Richtung der Landstraße/Autobahn zeigt.

[joschilein]

Zitat von thrown-out

openrouteservice hat ein feature namens erreichbarkeitsanalyse, das sollte das sein, was du suchst, oder?

Ja, das ist schon mal ziemlich gut. Jetzt muss ich nur noch rausfinden, wie ich das exportiert bekomme.

[Aradiv]

Ich würde dafür auch einen A* (modifizierter Dijktra) verwenden.
http://de.wikipedia.org/wiki/A*

Die erforderlichen Daten kannst du dir von OpenStreetMaps laden.
So kannst du auch eigene Heuristiken für Autobahnen, Landstraßen usw usw vergeben und so die suche für deine Wünsche und Vorlieben genau anpassen.

(soetwas in der Art war bei uns übrigens Übung im 1. Semester Informatik )