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

Finish the incomplete implementations of the 3-opt* (inter-route 3-opt) #5

Open
yorak opened this issue Jul 24, 2020 · 1 comment
Open

Comments

@yorak
Copy link
Owner

yorak commented Jul 24, 2020

VeRyPy has a proven implementation of 3-opt* that operates on the entire solutions (which resides in local_search/solution_operators.py. Proven here means that it is able to replicate results from the literature.

3-opt* was one of the trickiest heuristics to implement, and, hence, there were many attempts, some of which remain incomplete. These were left where they were, because, even if the 3-opt* solution operation is verified to work through replication of Stewart & Golden results, VeRyPy would benefit from supporting implementations. For example, the 2 and 3 route heuristics as incompletely implemented in the do_3optstar_2route_move and do_3optstar_3route_move would allow a more convenient use of the 3-opt* in some special occasions. Another advantage would a unified interface to 3-opt* although with a slight performance and maintenance penalty.

While you, good reader, are at it, please also consider writing the do_naive_3optstar_move. In fact, thinking about it, that would be perfect place to start!

@yorak
Copy link
Owner Author

yorak commented Apr 30, 2021

I transferred these incomplete implementations to the separate inter_route_3opt_operators.py file so that they are not used by accident.

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

No branches or pull requests

1 participant