Optaplanner/graphhopper: Wie löst man VRP Minimax Optimierung?

Question

Ich habe ein Problem bei der Routenplanung, das aus N Fahrzeugen und> 2N Wegpunkten besteht. Ich möchte ihre Route so optimieren, dass die maximale Zeit/Kosten aller Fahrzeuge minimiert wird.

Die einzigen Optionen in JVM sind entweder Optaplanner oder Graphhopper.

Dieses Problem wird jedoch in keinem ihrer Dokumente nachgewiesen. Sieht so aus, als wäre dies ein Randfall, der von den meisten Benutzern ignoriert wird. Ist es möglich, eine dieser Bibliotheken zu erweitern, um ein solches Problem zu lösen? Vielen Dank für einen Rat.

Answer 1

Siehe OptaPlanner's page on Vehicle Routing:

Hier ist ein Beispiel mit dem Belgien-Datensatz an 50 Standorte liefern (~ Ihre Wegpunkte) mit 10 Fahrzeugen (nicht alle von ihnen verwendet werden) in etwa 32 Stunden der realen Straßenfahrzeit (ohne Rück Verkehr berücksichtigt):

siehe optaplanner-webexamples Beispiel um zu sehen, diese in Aktion (einschließlich google Maps und OpenStreetMap Visualisierungen) und optaplanner-Beispiele Vehicle siehe Beispiel Routing mit größeren Datenmengen, Multi-Depot zu spielen Fälle und/oder Zeitfenster.

Der obige Fall minimiert die Gesamtdauer (32 Stunden), aber mit ein paar Änderungen im vehicleRoutingScoreRules.drl können Sie diese ändern, um die maximale Dauer pro Fahrzeug zu minimieren (addieren Sie einfach die Dauer pro Fahrzeug und bestrafen das Quadrat dieser Zahl, Siehe "Fairness/Load Balancing" in OptaPlanner Dokumenten.