Easy score calculation vs Drools score calculation for VRP problems

[Aleksandrs Saveljevs]

Dear OptaPlanner,

We have been using OptaPlanner to solve VRP problems for the last several years. Reading the manual regarding various methods for score calculation, we got the impression that easy score calculation is the one that does not scale, so Drools score calculation should be used (and, in modern times, constraint streams), which provides incremental score calculation without any effort on our part. There is also manual incremental score calculation, but that is hard to write and maintain. So in previous years we built our solutions with the aim to use Drools score calculation as the main method and easy score calculation for score assertions.

However, somewhere around last year, doing performance tests, we started to notice that easy score calculation actually performs better than Drools (about 1.5 to 2.5 times faster, depending on the use case). That was unexpected, because according to the manual, Drools is expected to be much faster and incremental score calculation (with Drools, constraint streams or manual) is the only thing that scales. At the time, however, we did not go deeper into that.

Finally, in recent days I got to do some performance tests with OptaPlanner examples. After all, if easy score calculation performs better than Drools in our VRP use cases, it may mean that we just did not write something correctly. However, if the same trend can be observed with OptaPlanner examples, then probably it is suspicious enough.

So I got to play with solver configuration in optaplanner-examples/src/main/resources/org/optaplanner/examples/vehiclerouting/solver/vehicleRoutingSolverConfig.xml as of OptaPlanner 8.5.0. I made the local search phase run for one minute on "cvrptw-400customers" data set, changing the way score calculation is done. The following list shows the average for score calculation speed and the number of steps over three one minute runs, most efficient score calculation methods first:

1. incremental: scores/sec=118,697, steps=33,229

2. easy: scores/sec=48,090, steps=14,265

3. Drools: scores/sec=24,500, steps=6,973

4. constraint streams: scores/sec=23,419, steps=6,613

It can be seen that manual incremental score calculation is by far the most efficient, then comes easy score calculation and then Drools and constraint streams about two times slower than easy score calculation, which is also consistent with our implementations of VRP (and we solve with hundreds and thousands of points).

For completeness, I also got to play with a non-VRP problem (cloud balancing) and its solver configuration in optaplanner-examples/src/main/resources/org/optaplanner/examples/cloudbalancing/solver/cloudBalancingSolverConfig.xml . I chose cloud balancing, because it is not a VRP problem and because the example provides various methods for score calculation. These tests were done on "200computers-600customers" data set:

1. incremental: scores/sec=1,169,587, steps=7,138,161

2. constraint streams: scores/sec=115,919, steps=893,085

3. Drools: scores/sec=105,252, steps=826,369

4. easy (map-based): scores/sec=24,880, steps=252,239

5. easy: scores/sec=9,929, steps=105,969

It can be seen here that in this non-VRP problem incremental types of score calculation indeed significantly outperform easy score calculation. Also, incremental Java significantly outperforms Drools and constraint streams.

That raises a question of why Drools and constraint streams do not perform well for VRP? Is that because, for instance, after every move a lot of objects are updated (like updating arrival time throughout the chain)?

Have you observed similar performance characteristics in your own VRP use cases and would it be correct to say that easy score calculation is the best practical choice for VRP?

Best wishes,

Aleksandrs

[Lukas Petrovicky]

Hello Aleksandrs,

On Wed, Jul 28, 2021 at 2:21 PM Aleksandrs Saveljevs <aleksandrs...@gmail.com> wrote:

That raises a question of why Drools and constraint streams do not perform well for VRP? Is that because, for instance, after every move a lot of objects are updated (like updating arrival time throughout the chain)?

Have you observed similar performance characteristics in your own VRP use cases and would it be correct to say that easy score calculation is the best practical choice for VRP?

Interesting analysis!

Our general guidance is that a well written incremental will always win. Followed from a distance by either Constraint Streams or DRL, since the two use the same underlying implementation - when choosing between the two, you are generally better off with CS, simply because it is pure Java, so you get all the IDE magic. Generally, easy score calculators would be at the end of the pack.

That said, this is only general guidance. We have seen cases where easy score calculators win over CS - typically, it is on small data sets, where the gains of incrementality do not account for the overhead. I also believe that we have never seen a case where a well-written incremental would fail to beat anything else.

Speaking specifically about VRP, our own micro benchmarks show that CS is roughly 50 % faster than Easy on belgium-tw-n2750-k55. So now we have to ask why would this data set behave differently from the one you tried. I have no answer at the moment, but it would certainly be an interesting experiment to run.

 

--

Lukáš Petrovický

He/Him/His

Principal Software Engineer, Business Automation

Red Hat Czech, s. r. o.

lukas.pe...@redhat.com    IM: triceo/lpetrovi