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

Improve 2-opt #27

Closed
jcoupey opened this issue Feb 9, 2016 · 0 comments
Closed

Improve 2-opt #27

jcoupey opened this issue Feb 9, 2016 · 0 comments

Comments

@jcoupey
Copy link
Collaborator

jcoupey commented Feb 9, 2016

In the symmetric case, trying the move with edges (e_2, e_1) is the same as with (e_1, e_2). So better stop at some point to avoid testing pairs in both orders. This would improve timing on all problems (as even asymmetric instances use this at some point) and might be a huge speed-up for big instances, where local search is the most time-consuming phase.

The change should be made with caution as:

  • the two loops should go through the edges in the same order to easily avoid duplicates, without having to remember every pair;
  • in the inner loop, going through the edges in the order of the current tour IS mandatory for efficient computation of the cost of the part that has to be reversed (asymmetric case).
jcoupey added a commit that referenced this issue Feb 10, 2016
Conflicts:
	src/heuristics/local_search.cpp
@jcoupey jcoupey closed this as completed in 2794ab6 Mar 1, 2016
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