vroom icon indicating copy to clipboard operation
vroom copied to clipboard

Use Eval struct over plain Cost/Gain types

Open jcoupey opened this issue 3 years ago • 1 comments

Issue

Fixes #738

Tasks

  • [x] Create data structure to replace Cost and Gain values
  • [x] Adjust helper functions
  • [x] Adjust heuristics client code
  • [x] Adjust operators client code
  • [x] Adjust local search code
  • [x] Benchmark timing impact
  • [ ] Update CHANGELOG.md
  • [ ] review

jcoupey avatar Aug 01 '22 13:08 jcoupey

I've run this PR against the usual benchmarks across various exploration levels.

Solution obtained

All solutions are strictly identical with current master and this PR so it looks like I did not break anything with all the adjustments to switch from Cost/Gain to the new Eval struct.

Timing

Computing time increase is in the +15 to 20% ballpark for CVRP and VRPTW instances and around +5 to +10% for PDPTW instances. So this will somehow eat a bit of the performance boost that was introduced in the latest release, but there is not really any other way around that I'm afraid.

Possible improvement

The new Eval struct holds both cost and duration metrics and all the math operations are overloaded to operate on both members. So the computing overhead is due to switching from doing cost/gain math with basic types (uint32_t and int64_t) and a single value to doing it with this struct. I've implemented the various operators in a straightforward way but maybe it's possible to do a bit of compile-time magic to improve the efficiency here. Any input on that is welcome!

jcoupey avatar Aug 02 '22 13:08 jcoupey