Routenplanung: Optimierte Reihenfolge für die Zielpunkte

max331 · 2020-02-07T10:10:30.000Z

Hallo,

ich bin ab und an in größeren mir unbekannten Wohngebieten unterwegs um fehlende Dinge zu taggen. Ich versuche dabei schon halbwegs wirtschaftlich die ganzen Straßen abzulaufen, aber es gibt einiges an Optimierungspotenzial um nicht mehrere Wege doppelt laufen zu müssen.
An anderer Stelle wurde mir für die Streckenorganisation Graphhopper empfohlen: https://graphhopper.com/api/1/examples/#optimization
Ich hab das mal versucht, leider muss man hier die Reihenfolge der Punkte angeben, die man abarbeiten möchte. Die ist mir jedoch egal. Ich habe einen Startpunkt und Zielpunkte die ich in einer optimierten Reihenfolge erreichen möchte.

Gibt es ein Tool welches mir sowas bietet?

Vielen Dank

Grüße

kreuzschnabel · 2020-02-07T10:14:00.000Z

max331:

Ich habe einen Startpunkt und Zielpunkte die ich in einer optimierten Reihenfolge erreichen möchte.

Gibt es ein Tool welches mir sowas bietet?

Das nennt sich Tür-zu-Tür-Sortierung – Start- und Zielpunkt bleiben, alle Zwischenziele werden auf kürzeste Gesamtstrecke optimiert. OsmAnd kann das, aber ich muss die Funktion auch jedes Mal erst suchen.

Die mathematische Aufgabenstellung an sich heißt Problem des Handlungsreisenden.

–ks

Nop · 2020-02-07T10:27:43.000Z

Graphhopper bietet das, allerdings meines Wissens nicht als fertige Anwendung, sondern entweder zum Selberbasteln mit dem open source Optimierungstool jsprit oder über eine kostenpflichtige API.

gormo · 2020-02-07T13:46:18.000Z

Hier https://help.openstreetmap.org/questions/55994/traveling-salesman-routing gibts einige Links

ikonor · 2020-02-07T14:16:37.000Z

max331:

Ich versuche dabei schon halbwegs wirtschaftlich die ganzen Straßen abzulaufen, aber es gibt einiges an Optimierungspotenzial um nicht mehrere Wege doppelt laufen zu müssen.

Diese Anforderung entspricht eher dem Briefträgerproblem / Chinese postman problem.

Das einzige was ich mal dazu gefunden hatte ist ein QGIS Plugin “Chinese Postman Solver”:
https://plugins.qgis.org/plugins/chinesepostman/

(ist bei mir in QGIS 3.4.15 nicht gelistet, hab deshalb Zip unter Versions heruntergeladen und installiert)

AB-inf-x-chg-AB · 2020-02-07T14:54:55.000Z

Auch eine interessante Fragestellung, ich hatte mal so etwas ähnliches geschrieben und stelle mal zwei Querverweise her:

OSM-forum Thread: “(kurze) Route zu mehreren Ziele erzeugen”

stephan75 · 2020-02-09T20:46:11.000Z

Nach meiner Erinnerung bietet der Webdienst https://www.routexl.de/

so eine Funktion auf OSM-Basis, oder?