Ich frage mich gerade, ob es eine Software-Lösung auf OSM-Basis für folgendes Problem gibt:
n-Zwischenziele sollen angefahren werden
Startpunkt sowie Endpunkt bekannt
Route soll über ermittelte Reihenfolge erfolgen, die am kürzesten erscheint
Falls es das nicht gibt, wäre Folgendes meine naive Vorangehensweise:
Mit OSRM eine Matrix (ähnlich wie eine Routingtabelle im Netzwerk) für alle Knoten ermitteln (wie weit bin ich von Ziel a1 a2 usw entfernt) und alle speichern (ist vermutlich erst einmal rechenintensiv)
Danach mit einem Algorithmus wie Dijkstra die beste Strecke ermitteln
Für das TSP gibt es einige Heuristiken und sicherlich auch Programme, welche diese implementieren. Dafür müsstest du nur einen Graphen mit den vorberechneten Entfernungen aller Knoten zueinander erstellen (dein Schritt 1).
Mit Dijkstra kannst du den Schritt 2 natürlich machen, aber das dauert laaaaaange (abhängig von der Anzahl der Ziele), das ist nämlich der schwierigste Teil dieses Problems. Deswegen die Heuristiken verwenden. Wenn es nur wenige Ziele (ein paar Hundert?) sind und du das nur selten brauchst, kannst du es natürlich ganz naiv machen.
Es macht beides: schnelles OSM-Routing mit Contraction-Hirachies (also ähnlich wie OSRM), um die Routen-Matrix zu berechnen, und löst das Travelling-Salesman-Problem basierend auf dieser Matrix.
Wenn Du mit OSRM routen willst musst Du beachten, dass solche bulk-requests auf den existierenden Instanzen von OSRM nicht erlaubt sind, Du müsstest Dir also eine eigene einrichten. OSRM ist in C++ geschrieben, auch das muss man mögen, eine reine Java-Lösung geht vielleicht am ehesten auf Basis von Graphhopper.
