optaplannervehicle-routing

Is there an example of an optaplanner vrp model that minimizes cost per unit?


I have a vrp variant that minimizes cost for a set of liquid deliveries. I have been asked to minimize cost per unit instead.

The costs are: hourly vehicle costs from standstill, back to depot (just the time to previous standstill and time to depot from the VRP example, multiplied by the vehicle hourly rate), plus the cost of product.

The amount delivered varies depending on the solution, but can be calculated by doing a sum of the deliveries of each vehicle.

So I have three streams for costs and one for unit count. Is there a way to join them and divide the two sums? Or is a shadow variable the only way to do it?

For a shadow variable method, I would add "cost"to each customer and then have a single constraint that replaces all the soft constraints that looks like:

protected Constraint costPerUnit(ConstraintFactory factory) {
                return factory.forEach(Customer.class)
                .groupBy( c->sumLong(c.getCost()), sumLong(c.getLitres))
                .penalizeLong(
                                                HardSoftLongScore.ONE_SOFT,
                                                (cost, amount) -> cost / amount)
                                .asConstraint("costOfProduct");
}

It seems like it would be very slow though.

edit: thinking about this some more, is there a performance reason for using constraint streams instead of just calculating the score in listerners and then using one simple constraint stream rule for all soft constraints?


Solution

  • Even though, with a lot of care and attention, you could probably implement a very fast listener to tackle this sort of problem, I doubt it would be as fast as a properly incremental solution.

    Now does that solution need to be implemented using Constraint Streams? No. For small problems, EasyScoreCalculator will be, well, easy - but for small problems, you wouldn't need OptaPlanner. For problems large in size but easy in how the score is calculated, you may want to look into IncrementalScoreCalculator - those are tricky to implement, but once you get it right, there is no way you could be any faster. Well-designed incremental calculators routinely beat Constraint Streams in terms of performance.

    The main benefit of Constraint Streams is good performance without the need for complex code. And you get constraint justifications, and therefore score explanations. The downside is you have to learn to think in the API, and there is some overhead. It's up to you to weigh these factors against each other and make the choice that is best for your particular problem.