Skip to content
New issue

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

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

Already on GitHub? Sign in to your account

Early abort for relocate and Or-opt moves #147

Closed
jcoupey opened this issue Aug 16, 2018 · 1 comment
Closed

Early abort for relocate and Or-opt moves #147

jcoupey opened this issue Aug 16, 2018 · 1 comment

Comments

@jcoupey
Copy link
Collaborator

jcoupey commented Aug 16, 2018

Commit 696aa4b introduced an early abort when evaluating a relocate step for the TSP local search, saving quite a few loops. It's based on the fact that we can be sure that a bunch of potential gains won't be better than the one already known, even without complete evaluation.

It seems like we could port this principle to the CVRP local search phase, both for relocate and or-opt moves, respectively here and here.

The good part is that the necessary values are already pre-computed in solution_state::node_gains and solution_state::edge_gains.

@jcoupey jcoupey added this to the v1.3.0 milestone Aug 16, 2018
@jcoupey jcoupey mentioned this issue Sep 5, 2018
4 tasks
@jcoupey
Copy link
Collaborator Author

jcoupey commented Sep 7, 2018

Done in #155.

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

No branches or pull requests

1 participant