Skip to content
New issue

Have a question about this project? # for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “#”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? # to your account

Improve local search aborts based on incompatibilities #281

Closed
jcoupey opened this issue Dec 16, 2019 · 2 comments · Fixed by #299
Closed

Improve local search aborts based on incompatibilities #281

jcoupey opened this issue Dec 16, 2019 · 2 comments · Fixed by #299

Comments

@jcoupey
Copy link
Collaborator

jcoupey commented Dec 16, 2019

We store various incompatibilities between vehicles and jobs (based on skills and other constraints) for constant-time lookup through Input::vehicle_ok_with_job. This used to allow early aborts for many operators during local search as compatibility is typically checked first place in cvrp::OperatorName::is_valid.

Now since #266 has been implemented, most validity checks happen after gain computations. So for a local search move with an obvious incompatibility between job and vehicle we still create the operator and call compute_gain while the following is_valid call is bound to fail.

We should ensure LS operators expect compatibility to be checked before-hand (maybe assert it for debugging), while moving all such checks to LocalSearch::run_ls_step, resulting in earlier aborts for obvious incompatibilities.

@jcoupey
Copy link
Collaborator Author

jcoupey commented Dec 16, 2019

Note: no change expected on problems with no incompatibilites (e.g. CVRP/VRPTW benchmarks) but it would be interesting to measure impact on situations where defined skills result in a lot of incompatibilities between jobs and vehicles.

@jcoupey
Copy link
Collaborator Author

jcoupey commented Feb 6, 2020

Quick feedback on the couple tests I've been running.

  1. Pushing incompatibilities to the extreme: each vehicle has it's own job set and they're disjoints so no move between two different routes is ever valid. I noticed a ~10x computing time speedup.

  2. With a more "reasonable" setting (vehicles are restricted to a subset of 40% of all jobs which overlap between vehicles), I noticed a ~3.5x computing speedup.

Of course this is very problem-dependant and the speedup only applies to problems with a natural clustering of jobs to vehicles (through skills or other constraints).

# for free to join this conversation on GitHub. Already have an account? # to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant