CODEWITHSUNDEEP
mathematical-optimizationoptaplannertraveling-salesmangraphhopper
tribbloid
tribbloid

Reputation: 3838

Optaplanner/graphhopper: how to solve VRP minimax optimization?

I have a route planning problem that consists of N vehicles and > 2N waypoints. I want to optimize their route such that the maximum time/cost of all vehicles is minimized.

The only options in JVM are either optaplanner or graphhopper.

This problem is however not demonstrated in any of their documents. Looks like this is an edge case ignored by most users. Is it possible to extend either of these libraries to solve such problem? Thanks a lot for any advice.

Upvotes: 0

Views: 519

Answers (1)

Geoffrey De Smet
Geoffrey De Smet

Reputation: 27312

See OptaPlanner's page on Vehicle Routing:

Here's an example with the Belgium dataset deliver to 50 locations (~ your waypoints) with 10 vehicles (not all of them are used) in about 32 hours of real road driving time (without taking traffic into account):

enter image description here

See the optaplanner-webexamples example to see this in action (including google maps and openstreetmap visualization) and see optaplanner-examples's Vehicle routing example to play with bigger datasets, multi-depot cases and/or time windows.

The case above minimizes the total duration (32 hours), but with a few changes in the vehicleRoutingScoreRules.drl you can change it to minimize the maximum duration per vehicle (just sum the duration per vehicle and penalize the square of that number, see "fairness/load balancing" in OptaPlanner docs).

Upvotes: 1

Related Questions