ich bräuchte ein wenig Hilfe bei einer Aufgabenstellung die ich für eine Schätzung der realen Routenentfernung brauche.
Epilog
Bei mir auf arbeit müssen wir ständig Entfernungen zwischen mehreren Zielpunkten berechnen und den bestmöglichen Zielpunkt für eine Route berechnen.
Dafür benutzten wir zu anfangs die Luftlienenentfernung welche wir mit einem festen Faktor multipliziert hatten. Auf kurzen Distanzen funktionierte das noch ganz gut, bei längeren Entfernungen war das aber sehr ungenau. Daraufhin haben wir 100.000 Routen zwischen zufällig auf der Deutschlandkarte ausgewählter Orten berechnet und aus der differenz zwischen Luftlienenentfernung und Routenentfernung eine Funktion abgeleitet die die Schätzung deutlich verbessert hat. Leider ist dies bei sehr langen Entfernungen trotzdem noch recht ungenau wenn man nicht gerade von Berlin nach München fährt.
Mein Lösungsansatz wäre, die Deutschlandkarte in 50.000 - 100.000 Raster aufzuteilen, für jedes Raster den Mittelpunkt zu ermitteln, und den nächstgelegenen Punkt der per Straße erreichbar ist als Coordinate zu ermitteln. (Auf den Epilog bezogen: Dann könnte die Routen zwischen diesen Rasterpunkten vorberechnen und später dann für Start- und Ziel-punkt den nächstgelegenen Rasterpunkt ermitteln und damit die Schätzung der Entfernung und Fahrzeit deutlich verbessern).
Leider kenn ich mich damit nicht wirklich aus so das das Problem für mich ein wenig erschlagend wirkt.
Wie lange hat das Berechnen der 100000 Routen gedauert? Dir ist klar, dass ein Vorberechnen aller Verbindungen von 50000 Punkten ungefähr 12000 Mal so lange dauern würde?
Ich schätze, der Aufwand, den Routenplaner (den ihr ja schon irgendwo haben müsst) so performant hinzubekommen, dass man damit einfach arbeiten kann düfte geringer sein…
Die Berechnung von 100.000 Routen hat etwas über einen Tag gedauert. Mein Ziel ist es nicht alle 50.000 Rasterpunkte mit einander zu verbinden sondern nur die Routen zwischen Rasterpunkte über 100km Luftlienenentfernung zu berechnen. So zumindest war meine Idee. Aber dein einwand ist berechtigt. Eventuell muss ich die Anzahl der Rasterpunkte reduzieren.
Das Problem ist das ich eine Lösung brauche die innerhalb von Sekunden mir die geschätzte Entfernung zwischen einem Startpunkt und 100.000 möglichen Zielpunkten zurück gibt. Und dies rein mit MSSQL-Mitteln. Ich denke nicht das dies mit der realen Routenberechnung machbar ist.
Als Routenplaner für die Vorberechnung der Routen haben wir damals MapPoint benutzt. Wir gesagt, es geht darum aus tausende mögliche Zielpunkte innerhalb von Sekunden den oder die besten auszusuchen.
(1) du machst Raster mit z.B. 0.1 Grad Maschenweite (= ca 7km x 10 km).
(2) prüfst ob der Mittelpunkt (oder ein Stück) dieser Masche in Deutschland liegt.
(3) ermittelst jeden andere Maschenmittelpunkt mit >100km Entfernung (Luftlinie)
(4) wirfst jede Kombination mit >100km deinem Router vor
(5) nimmst den Start- und Endpunkt, den dir dein Router gibt (das ist die nächste Straße, evtl musst du auch den zweiten und vorletzten Punkt nehmen, den dir MapPoint im GPX auswirft)
(6) speicherst diese Start- und Endpunkte zusamen mit der Entfernung, die dir dein Router sagt.
So wie ich das sehe, kann dir OSM nur bei Punkt (2) helfen, (1) und (3) ist nur ein bisschen Mathe mit 2 Schleifen. Den nächsten Straßenpunkt muss dir ja dein Router geben, der möglicherweise andere Straßen als OSM verwendet.
Für (4) und (5) kannst Du OSM nur verwenden, falls Du auf MapPoint verzichten willst. Allerdings kannst Du ja damit schon umgehen, die Einarbeitungszeit in MapPoint wäre verloren. Dafür könntest danach mit Graphhopper oder Routino oder osrm arbeiten
Idee:
Du machst Dir eine Tabelle mit Postleitzahlen und GPS-Koordinaten.
Du machst Dir eine Tabelle mit Orten/Gemeinden und GPS-Koordinaten.
Jetzt machst Du eine Entfernungstabelle von jeder Postleitzahl zu jeder anderen Postleitzahl
Dazu machst Du eine Entfernungstabelle von jeder Postleitzahl zu jeder Gemeinde in dieser Postleitzahl
Wenn Du jetzt die Entfernung zwischen zwei Punkten brauchst rechnest bzw. holst Dir alle Einzelentfernungen:
GPS-Punkt zu Ortsmitte → Luftline
Ortsmitte-PLZ-Mitte → Datenbank
PLZ-PLZ → Datenbank
PLZ-Ortsmitte → Datenbank
Ortsmitte-GPS-Punkt → Luftlinie
Jetzt musste die kurzen Luftlinien-Wege noch mit einem Faktor versehen, den Du ja schon hast.
Dann musste noch über die Winkel von Ortsmitte/PLZ/PLZ ausrechnen, ob du die Werte aus der Datenbank addieren oder subtrahieren musst. Oder ggf. halbiert addieren wenn es ein 90° Winkel wird.
