Wie teilt man n Ziele in zwei Gruppen und minimiert die Summe der TSP-Distanz von zwei Gruppen?

Question

Ich habe ein sehr praktisches Problem in der Robotertechnik getroffen. Da ich EE-Hintergrund bin und mit Algorithmen nicht vertraut bin, suche ich hier Hilfe.

Es gibt n Ziele, und die Ziele sind in zwei Gruppen (Gruppe A und Gruppe B) zu unterteilen. Es gibt auch zwei Roboter, Roboter A und Roboter B. Jedes Ziel der Gruppe A muss von Roboter A mindestens einmal besucht werden. Jedes Ziel der Gruppe B muss von Roboter B mindestens einmal besucht werden. Alle Informationen werden gegeben, Gewichte, Richtungen und etc.

Fragen:

Wie die Teilung, S. T. berechnen die beiden roboter reisen die summe zusammen? Wie berechnet man die Division, s.t. Die Zeit, in der zwei Roboter alle Zielorte zu erreichen, ist am kürzesten?

Answer 1

Meine Empfehlung ist es, auktionsbasierte Techniken zur Aufgabenverteilung für Roboter zu betrachten. Die Idee ist, dass Agenten auf einem Markt bieten, um Ziele zu ihrem Plan hinzuzufügen. Agenten, die zu niedrigeren Kosten neue Ziele zu ihren Plänen hinzufügen können (kürzere zurückgelegte Entfernung), erhalten die Aufgabe. Schneller zu berechnen Lösungen (mit minimalen Spanning-Tree-Heuristik, zum Beispiel, anstatt das schwierigere TSP-Problem zu lösen) neigen dazu, höhere Kosten Lösungen zu finden, sondern wird für eine große Anzahl von Robotern und eine große Anzahl von Destinationen ziemlich gute Lösungen finden.

Ein guter Ausgangspunkt ist die Referenz: Dias, M. Bernardine, et al. "Marktbasierte Multirobot-Koordination: Eine Umfrage und Analyse." Proceedings der IEEE 94.7 (2006): 1257-1270.