Traveling Salesmen für's Zeitung austragen

Radius2324132 · 2020-02-10T22:26:48.000Z

Hallo,

ich trage seit Kurzem nachts Zeitung aus. 148 Adressen maximal momentan. Natürlich interessiert mich die kürzeste Route. Google Maps hat mich die erste Nacht ziemlich im Stich gelassen weil es in der Gegend viele Hausnummern gibt die abseits der Straße an Gehwegen aufgereiht sind. Sie wurden einfach irgendwo positioniert wo gar nichts ist.
Die Zeitungsfirmen und Postdienst nutzen wohl einen Service namens sabris, mit dem sie die Laufzeiten, Zeiten fürs einwerfen in Briefkästen usw berechnen. Deren Daten waren schon etwas besser, aber der Ausdruck den ich hatte hatte trotzdem etwa 15 falsch positionierte Adressen. Alle auf einem Haufen, kein Wunder dass sie meinen das wäre schneller zu schaffen.

Das war die eine Sache, die andere ist, dass ich die kürzeste Route kennen will.

Als erstes hatte ich Google Maps versucht aber die Adressen unterzubringen ist kaum machbar.

Dann alle möglichen Android-Apps, die aber leider wenig nützlich sind, zumindest diejenigen die ich getestet habe.

Ich habe dann BatchGeo gefunden und eine Excelliste erstellt mit allen Adressen bei denen ich dann in einer Spalte einzelne Adressen für eine Tour abschalten kann. In einem anderen Sheet kopiere ich dann die Daten und erstelle in BatchGeo eine Liste. Die Liste kann ich dann auf dem Smartphone anschauen.

Das Problem ist, das sind google Maps-Daten und eine Adresse wurde sogar einen km weiter entfernt positioniert. Die kürzeste Strecke ist auch nicht machbar.

Bing maps habe ich dann gefunden und die waren schon deutlich besser mit den Hausnummern. Dann habe ich auch schon gleich OSM gefunden und alles passt bis auf eine Hausnummer die etwas seltsam ist.

Für das Traveline Salesman Problem habe ich graphhopper.com gefunden. Nachdem ich 68 Adressen eingegeben hatte wurde meine IP gesperrt. Ich vermute weil die Seite permanent, nach jedem Rechtsklick → Zwischenstop zufügen, eine komplette Berechnung macht. Sie nutzen OSM, das wäre also schon recht gut gewesen. Aber mich erst in die API einzuarbeiten wäre sicher schwierig.

Heute habe ich dann über Maps.me gelesen. Die haben wohl auch so etwas aber wie ich gerade eben sehe scheint es nach 3 Zwischenstops aufzugeben. Vorher habe ich versucht über BatchGeo eine .kml-Datei zu importieren. Das hat auch geklappt, allerdings enthält kml wohl Geodaten und das sind die falschen Koordinaten von google Maps.
Ich konnte die Daten auch in Maps.me importieren aber es gibt keinen Wege daraus direkt eine Strecke zu machen und ich denke der Grund ist auch weil es nur ein paar Zwischenstops geben kann.

Wie kann ich das lösen? Geht es überhaupt, so dass ich mit meinem Handy die kürzeste Strecke ablaufen kann? Ist halt leicht unterschiedlich pro Tag aber dafür habe ich ja die Exceldatei in der ich nicht nötige Adressen abwählen kann. Theoretisch kann ich dort auch Code für eine Datei erstellen und exportieren.

Besten Dank!
Radius

Skinfaxi · 2020-02-11T06:27:10.000Z

Die Komplexität von solchen Betechnungen steigt leider exponentiell mit jeder Adresse und verbraucht entsprechende Rechenleistung.

Ein möglicher Ansatz ist, Kleincluster zu bilden und nur die Wege zwischen den Clustern zu berechnen. ich meine dass die Daten um den optimalen Weg von Eingang zu Eingang bei nebeneinanderliegenden Häusern zu berechnen, eh keinen wirklichen Vorteil versprechen.

so reduzierst Du auf jedenfall die Komplexität deutlich

pebogufi · 2020-02-11T09:30:14.000Z

Osmand kann das. Bei den Zwischenzielen wählt man Sortieren, Tür-Zu-Tür sortieren.
Natürlich müssen alle 148 Zwischenziele eingegeben sein, am besten mit einer Gpx-Datei. Allerdings ist die Anzahl der Punkte eine echte Herausforderung, da gibt es SEHR viele Varianten. Keine Ahnung wie lange ein Programm für die Berechnung braucht.
Bitte berichte deine Erfahrungen, das Thema ist höchst spannend.
Zum Testen würde ich mit nicht mehr als 10 anfangen.

blauloke · 2020-02-11T12:12:24.000Z

pebogufi:

Osmand kann das. Bei den Zwischenzielen wählt man Sortieren, Tür-Zu-Tür sortieren.
Natürlich müssen alle 148 Zwischenziele eingegeben sein, am besten mit einer Gpx-Datei. Allerdings ist die Anzahl der Punkte eine echte Herausforderung, da gibt es SEHR viele Varianten. Keine Ahnung wie lange ein Programm für die Berechnung braucht.
Bitte berichte deine Erfahrungen, das Thema ist höchst spannend.
Zum Testen würde ich mit nicht mehr als 10 anfangen.

Danke für den Tipp mit dem Sortieren bei den Zwischenzielen. Diese Tür-zu-Tür Funktion habe ich die letzte Zeit gesucht und nicht gefunden.
Ich habe jetzt mit 12 Zwischenzielen getestet und die Berechnung dauert keine Minute.

gormo · 2020-02-11T12:39:26.000Z

blauloke:

Ich habe jetzt mit 12 Zwischenzielen getestet und die Berechnung dauert keine Minute.

Die Komplexität steigt exponenziell, nehme ich an. Keine Ahnung wie das Laufzeitverhalten der Heuristik ist, die OsmAND verwendet.

Ich finde das auch sehr interessant. Finde im OsmAnd-Sourcecode aber die Stelle nicht, um nachzugucken was der genau macht und wie das skalieren könnte.

…übrigens ist das Ausgangsproblem doch eine ziemliche Erfolgsstory für OSM - wir haben die besten Adressen!

_i · 2020-02-14T06:55:40.000Z

https://media.ccc.de/v/bucharest-40-shortest-path-in-the-database-and-more-with-pgrouting
Aber die Ergebnisse sollen ja auch sinnvoll sein (Anfahrt per PKW, unnötiges Wenden, …), Gab ja einen der ersten Router für OSM, welcher genau dieses TSP adressierte: https://wiki.openstreetmap.org/wiki/Traveling_salesman
Du musst mal schauen, ob es da aktuell noch einen gibt, welcher TSP durch Näherung lösen kann: https://wiki.openstreetmap.org/wiki/Routing

gormo · 2020-02-14T17:06:24.000Z

gormo:

Ich finde das auch sehr interessant. Finde im OsmAnd-Sourcecode aber die Stelle nicht, um nachzugucken was der genau macht und wie das skalieren könnte.

Gefunden: die machen das entweder mit Ant Colony Optimisation:

https://github.com/osmandapp/Osmand/blob/master/OsmAnd-java/src/main/java/net/osmand/TspAnt.java

Oder mit Held-Karp, https://github.com/osmandapp/Osmand/blob/master/OsmAnd-java/src/main/java/net/osmand/TspHeldKarp.java .

Ich hab keine Entwicklungsversion von OsmAnd laufen, kann also nicht weiter testen.