pyconcorde icon indicating copy to clipboard operation
pyconcorde copied to clipboard

Add handling for asymmetric TSP

Open mikedbjones opened this issue 1 year ago • 0 comments

As discussed in #28 , I've made the following changes to handle asymmetric TSP (for example real-world driving/walking problems).

  1. Add symmetricize() function in util.py.
  2. Add is_symmetric boolean property of Problem, so that asymmetric problems can be tracked through to the solution, which necessarily needs to be modified (removing ghost nodes that were added in symmetricize()).
  3. Add remove_ghost_nodes() method to Solution
  4. Add raise ValueError when a non-integer matrix is passed (Concorde provides solution of 0 with float matrices)
  5. 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!

mikedbjones avatar Jul 04 '23 23:07 mikedbjones