Ich kann das Problem als "Mehrere Reisen Verkäufer Problem mit gegenseitigen Knoten" nennen. Ich habe eine Gruppe von Leuten aus verschiedenen Orten in einer Stadt. Sie möchten eine Tour planen, um bestimmte Geschäfte zu sehen. Wie kann ich dieses Problem lösen? Wie kann ich das Problem modellieren, um meta-heuristische Algorithmen wie GA oder ACO zu verwenden?planen Sie eine Reise für Mitglieder einer Gruppe von Verkäufern mit unterschiedlichen Ursprüngen
Ich gehe davon aus, dass das Problem wie folgt ist;
Jede Person möchte eine Reihe von Städten aus der großen Karte gehen.
Zwei oder mehr Personen in derselben Stadt zugleich sein können
Zwei oder mehr Menschen die gleiche Kante zur gleichen Zeit verwenden können.
Für den genetischen Algorithmus wird jedes Chromosom so aussehen;
Route für Person 1 | Route für Person 2 | Route für Person 3 ..
Eine Beispielgeneration kann sein;
Chromosom 1 = 2,6,7,1 | 4,7,2 | 3,5,6
Chromosom 2 = 6,7,2,1 | 2,4,7 | 3,5,6
Sie müssen Crossover- und Mutationsoperationen für jede Route separat anwenden. Sie können Crossover-Methoden wie PMX (Partial-mapped Crossover) für Permutationsdarstellungen verwenden. Sie können Operationen wie Random Swap, Insert, Scramble für Mutation verwenden.
Für Ant Colony Optimierung muss jede Ameise Lösungen für jede Person in jeder Iteration erstellen. Außerdem sollten unterschiedliche Pheromonwerte für die Route jeder Person gespeichert werden. Denn, selbst wenn sie gemeinsame Orte haben (zum Beispiel beide Städte 2 und 3), heißt das nicht, dass die Grenze zwischen diesen Städten die gleiche Erwünschtheit haben sollte (die Grenze zwischen 2 und 3 mag für Person 1 geeignet sein, aber sie kann es für die Person nicht wünschenswert sein2).
Also, ich denke, es wird am besten sein, Routen für jede Person separat zu finden. Weil es keinen Informationsaustausch zwischen Lösungen für die Routen jeder Person geben kann.
Ihre Antwort war sehr hilfreich, aber ich denke, es ist besser, alle Touren zusammen zu betrachten, da die Summe aller Tourenlängen minimiert werden muss und nebenbei die Reihenfolge der zu besuchenden POIs verwaltet werden sollte. – Ebola
Was hast du probiert? Sie müssen ein minimales Arbeitsbeispiel einbeziehen. –
@ThomasW Das Problem ist, ich habe kein Papier oder Forschung oder ähnliches Projekt gefunden, um diese Aufgabe zu erledigen. Normalerweise werden metaheuristische Ansätze verwendet, um solche Probleme zu lösen. Aber es gibt ein Problem bei der Verwendung dieser Ansätze. Die geplante Tour, die aus verschiedenen Routen für verschiedene Benutzer besteht, ist eine einzige Lösung für das Problem (in GA ist es ein Chromosom). Wie können wir diese eine einzige Lösung bilden und wie können wir die Evolution-Operatoren anwenden, um die Lösungen zu besseren Antworten zu entwickeln? Das Gleiche passiert mit ACO. Wie können wir die Lösungen bilden? – Ebola