optaplannerdrools-planner

OptaPlanner deploy multiple vehicles to same location


I have taken OptaPlanner VRP web example and customized it to my needs. It is working fine except in the below scenario:

Number of vehicles available : 2.
Each vehicle capacity is 6.
And customer demand is 7.

In the above scenario, OptaPlanner is not able to solve the problem. I think it should deploy 2 vehicles to the same customer location, but it is not working as expected.

I am not able to figure out how to configure OptaPlanner rules to make it work.


Solution

  • One way to fix is it to split up the customer with demand 7:

    You 'll see that whenever possible, the same vehicle visits all customers at the same location. For a nicer design, you might even want to refactor Customer into Customer (only 1 per location) and CustomerPart (1 per separate demand of a customer).

    Notice that in the original requirements, a demand cannot be split up over 2 vehicles (not because of the constraint rules, but because of the domain design). So using the original implementation to solve your requirements, naturally excludes a number of feasible and potentially more optimal solutions.

    The more your split up, the more you open new feasible and potentially new optimal solutions. Of course, the more you split up the demand per customer, the more the search space increases. And it increases heavily. Replacing that customer with 7 customers of demand 1 (and doing that for all customers) is going to be perfect but suffer from major scalability issues.

    To be practical, I 'd split up every demand that is higher than half the smallest vehicle's capacity (or even a third of that capacity), but no more. Use the OptaPlanner Benchmarker to measure (instead of geussing) what the result quality and dataset scalability when the split up limit parameter changes, so you can tweak it. (oh and if you end up doing those benchmarks, do share your best parameter value here.)