Wir haben einen Algorithmus entwickelt, der abhängig von der Check-in-Zeit einiger Mitarbeiter und ihrem Wohnort die Art und Weise berechnet, wie sie in einige Fahrzeuge eingeteilt werden, und die Route, die die Fahrzeuge einhalten müssen, um sie zum Arbeitsplatz zu bringen. Dies wurde mithilfe des TSP-Algorithmus (Travelling Salesman Problem) und einiger anderer Anpassungen erreicht.
Wir wollen darüber hinausgehen und es verbessern. Die Sitzplatzkapazität der Fahrzeuge ist vorerst auf 4 festgelegt (5 Plätze, aber einer vom Fahrer belegt), und wir möchten diesen Betrag "variabel" machen. Mit anderen Worten, wir möchten vor der Ausführung des Hauptalgorithmus die Kombinationen von Fahrzeugen (und deren freien Sitzen) bestimmen, die möglicherweise benötigt werden. Es ist wichtig zu wissen, dass ich, wenn ich von Fahrzeugen spreche, über Fahrzeugtypen spreche, z. B. Fahrzeug A hat 4 Sitze, Fahrzeug B hat 7 Sitze und so weiter. Ich spreche also nicht von einem Audi A8 mit 5 Sitzen, einem Sitz Ibiza mit 5 Sitzen und einem Bus mit 20 Sitzen.
Bisher habe ich mir Folgendes ausgedacht:
- Bestimmen Sie die Arbeitnehmergruppen.
- Bestimmen Sie, wie viele Fahrzeuge benötigt werden und welche (freien) Plätze sie haben. Das stelle ich in dieser Frage [a].
- Der Benutzer wählt die bevorzugte Kombination aus und fährt fort.
- Wenden Sie den Algorithmus an, der bereits unter Verwendung der Fahrzeugkombination entwickelt wurde, und prüfen Sie, ob eine realisierbare Lösung gefunden wird.
Meine Frage ist, wie man den [a] -Algorithmus entwickelt. Das folgende Beispiel zeigt Ihnen das Ergebnis der Ausführung von [a]:
Stellen Sie sich vor, wir haben die folgenden Personen, die in Fahrzeuge mit 4, 7, 10 freien Plätzen zusammengefasst werden können.
Nach der Ausführung von [a] haben wir als Ergebnis:
- G3 (2 Arbeiter): Ein Fahrzeug mit 4 freien Plätzen (Fahrzeuge mit mehr freien Plätzen werden weggeworfen).
- G2 (2 Arbeiter): Ein Fahrzeug mit 4 freien Plätzen (Fahrzeuge mit mehr freien Plätzen werden weggeworfen).
G1 (9 Arbeiter):
- Option A: 3 Fahrzeuge mit 4 Sitzen.
- Option B: 1 Fahrzeug mit 4 Sitzen und ein weiteres mit 7 Sitzen.
- Option C: 2 Fahrzeuge mit 7 Sitzplätzen.
- Option D: ein Fahrzeug mit 10 Sitzplätzen.
Ich habe an eine Annäherung gedacht:
- Erstellen Sie die Fahrzeugtypen und fügen Sie sie einer sortierten Liste hinzu (Sortierkriterium müssen die Sitze sein).
- Führen Sie für jede Gruppe von Arbeitnehmern Folgendes aus:
- Berechnen Sie Kombinationen [b].
- Druckergebnisse auf dem Bildschirm.
Das Hauptproblem ist also, wie man sich entwickelt [b].
Irgendwelche Vorschläge? Entschuldigung, wenn ich mich schlecht erklärt habe.
quelle
Antworten:
Ich habe eine mögliche Lösung gefunden: Verwenden Sie das Constraint Satisfaction Problem, um es zu lösen.
Es gibt eine Einschränkung pro Gruppe wie folgt:
Arbeitermenge der Gruppe <= Summe pro Fahrzeug (Fahrzeugmenge X Fahrzeugsitze)
Die einzige Variable dort ist die Fahrzeugmenge, der Rest sind Konstanten. In meinem Beispiel gibt es also die folgenden Einschränkungen:
9 <= 4x + 7y + 10z
2 <= 4a + 7b + 10c
2 <= 4j + 7k + 10i
Ich habe mehrere Bibliotheken gefunden (JaCoP, Drools und OptaPlanner) und verwende derzeit die erste. Aber ich weiß nicht, wie ich diese Einschränkungen richtig definieren soll ...
quelle