search

yorak / VeRyPy

A python library with implementations of 15 classical heuristics for the capacitated vehicle routing problem.
MIT License
263 stars 55 forks source link

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

Open yorak opened 4 years ago

yorak commented 4 years ago

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 commented 3 years ago

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