Note that current version does not support number of points smaller than 5!
PyConcorde is a Python wrapper around the Concorde TSP solver.
PyConcorde allows you to compute solutions to the Traveling Salesman Problem with just a few lines of Python code. It uses the state-of-the-art Concorde solver and provides a convenient Python layer around it.
Note: until commit e065497 (pre version 0.1) PyConcorde was called PyTSP. It was renamed to emphasize the central role of the underlying Concorde solver.
PyConcorde runs under Python 2.7 and 3.5 and up. It needs the Concorde TSP solver and QSOpt linear programming library. Further instructions on building/downloading those can be found below.
To build PyConcorde, clone the repository:
git clone https://github.com/jvkersch/pyconcorde
cd pyconcorde
Then run
pip install -e .
This will download and build Concorde (and its dependency QSOpt) and then build
PyConcorde. While this may take a few minutes, downloading Concorde only
happens the first time the install script is run (unless you remove the data
directory).
If you already have Concorde and/or QSOpt installed (or an equivalent linear
solver), you can use those instead. Simply set the environment variable
CONCORDE_DIR (or QSOPT_DIR) to point to the folder where you installed
Concorde (or QSOpt).
Detailed instructions to build Concorde can be found at this web page.
PyConcorde is a very light-weight library. The main entry point is the
TSPSolver class. Here we use it to read in the Berlin52 dataset, a dataset of
52 locations in Berlin (part of the TSPlib test data).
>>> from concorde.tsp import TSPSolver
>>> from concorde.tests.data_utils import get_dataset_path
>>> fname = get_dataset_path("berlin52")
>>> solver = TSPSolver.from_tspfile(fname)
Problem Name: berlin52
Problem Type: TSP
52 locations in Berlin (Groetschel)
Number of Nodes: 52
Rounded Euclidean Norm (CC_EUCLIDEAN)(Extension) Use self-defined distance matrix:
from concorde.tsp import TSPSolver
dist_matrix = [[0, 1, 2, 3], [1, 0, 3, 4], [2, 3, 0, 1], [3, 4, 1, 0]]
# solver only supports integral edge weights, so here float will be rounded to two
# decimals, multiplied by 100 and converted to integer
solver = TSPSolver.from_data(dist_matrix=dist_matrix)As you can see above, PyConcorde (or rather, Concorde) is somewhat chatty and will print various message to the standard output. Now that we have a solver instance, let's compute a solution. On my machine this is almost instantaneous.
>>> solution = solver.solve()
(... output snipped for brevity ...)Again, Concorde will display a variety of messages while it's running. The end
result is a ComputedTour object called solution with information about the
tour that we just computed:
>>> solution.found_tour
True
>>> solution.optimal_value
7542.0
>>> solution.tour
array([ 0, 48, 31, 44, 18, 40, 7, 8, 9, 42, 32, 50, 10, 51, 13, 12, 46,
25, 26, 27, 11, 24, 3, 5, 14, 4, 23, 47, 37, 36, 39, 38, 35, 34,
33, 43, 45, 15, 28, 49, 19, 22, 29, 1, 6, 41, 20, 16, 2, 17, 30,
21], dtype=int32)
If you are looking for a pure Python TSP implementation, check out tsp-solver. It is not competitive with Concorde in terms of speed or memory usage, but has the advantage of being written in pure Python, which makes it more readily inspectable.
If you have another TSP algorithm that can be called from within Python, and you want to have it added here, please open an issue.
PyConcorde needs Concorde and QSOpt. Downloading and building these packages should happen automatically on Linux/Mac OS, but please file an issue if you experience any trouble during this step.
Note that Windows is currently unsupported. If you get the library to work on Windows, please open a ticket to describe any tweaks (or better yet, a Pull Request).
PyConcorde is licensed under the Modified BSD license. Note that Concorde and QSOpt are released under different licenses, and that PyConcorde does not include any code from these packages.