Abgesehen von Witzen hatte ich ein Routing-Problem, das beinahe ein Problem für Verkäufer auf Reisen (TSP) ist:
- Der Ausgangspunkt ist festgelegt
- der Endpunkt fällt mit dem Startpunkt zusammen
- Jeder Knoten muss besucht werden
- Die Gesamtkosten sollten minimiert werden
Vor zwei Jahren dachte ich, dass TSP perfekt zusammenpassen würde, also habe ich einige Beispieldaten tsp_solveund Concorde durchgespielt . Zum Glück war schnell klar, dass der kürzeste Weg des TSP nicht der kürzeste Weg ist , da das Problem dadurch erleichtert wird, dass die Knoten in unrealistischer Weise genau einmal besucht werden müssen . Dieses Bild ist nur ein manueller Ein-Schritt-Versuch zur Optimierung der berechneten Lösung und spart bereits ungefähr den Abstand der am längsten genutzten Kante.
Das Problem trat erneut auf, da ich versuche, optimale Routen zu Teilmengen von Kartierungs- / Überwachungsstandorten zu finden. Standort- und Straßennetzdaten sind ziemlich genau und präzise, daher ist eine solche Übung sinnvoll.
Ich habe mir Verallgemeinerungen des TSP angesehen, aber keinen geeigneten Algorithmus gefunden. Minimale Spannweiten berücksichtigen nicht die Rückkehr von Zweigen (die erste Lösung hier kostet 3 mehr). Soweit ich weiß, kümmert sich das Problem mit dem kürzesten Pfad letztendlich nur um zwei Knoten, und diejenigen, die nicht auf dem optimalen Pfad liegen, würden weggelassen. Ein spezieller Fall des Fahrzeugrouting-Problems scheint am besten zu passen, obwohl ich nicht weiß, ob es nicht direkte Pfade berücksichtigt.
Meine Frage: Gibt es einen festen Namen, eine Definition für diese Art von Problem (Familie)? Welchen Algorithmus und welches Tool würden Sie zur Lösung verwenden?
Ich bin sicher, dass es rechenintensiv wäre, aber ich interessiere mich sowohl für allgemeine (unendliche Ressourcen) als auch für praktische Antworten.
quelle
Antworten:
Das ist TSP . Sie haben nur keine gültige Entfernungsmetrik definiert, weil sie die Dreieck-Ungleichung nicht erfüllt: Wenn es eine Route von A nach C bis B gibt, die kürzer ist als die angegebene Entfernung von A nach C, dann die angegebene Entfernung von A nach C ist ganz einfach falsch. Die Lösung besteht darin, die Entfernungsmatrix zu aktualisieren, indem die Länge von A nach C auf die kürzeste Länge aller Routen von A nach C eingestellt wird.
quelle