pyconcorde
pyconcorde copied to clipboard
Add handling for asymmetric TSP
As discussed in #28 , I've made the following changes to handle asymmetric TSP (for example real-world driving/walking problems).
- Add
symmetricize()
function in util.py. - Add
is_symmetric
boolean property ofProblem
, so that asymmetric problems can be tracked through to the solution, which necessarily needs to be modified (removing ghost nodes that were added insymmetricize()
). - Add
remove_ghost_nodes()
method to Solution - Add
raise ValueError
when a non-integer matrix is passed (Concorde provides solution of 0 with float matrices) - Add uk_cities.py example
So far as I'm aware, this code does not break any existing functionality with symmetric matrices, nor other problem solutions.
If you're happy with the changes I've made, I'm happy to explain more in the readme and create another PR.
Thanks!