tspsolve

Algorithms for the traveling salesman problem (TSP) in Python.

Implemented so far:

• Nearest neighbor algorithm

  import tspsolve
  
  # Create matrix of distances d
  path = tspsolve.nearest_neighbor(d)
  

• 2-opt improvement

  import tspsolve
  
  # Create matrix of distances d and an initial path
  new_path = tspsolve.two_opt(d, path, verbose=True)
  

For Euclidiean TSP, the distance matrix can be computed efficiently with

dx = numpy.subtract.outer(x, x)
dy = numpy.subtract.outer(y, y)
d = numpy.sqrt(dx ** 2 + dy ** 2)

Installation

tspsolve is available from the Python Package Index, so simply type

pip install -U tspsolve

to install or upgrade.

Testing

To run the tspsolve unit tests, check out this repository and type

pytest

Distribution

To create a new release

1. bump the __version__ number,

2. publish to PyPi and GitHub:

   make publish
   

License

tspsolve is published under the MIT license.