Greedy, suboptimal solver for the Travelling Salesman Problem
Project description
Suboptimal Travelling Salesman Problem (TSP) solver
In pure Python.
This project provides a pure Python code for searching suboptimal solutions to the TSP. Additionally, demonstration scripts for visualization of results are provided.
The library does not requires any libraries, but demo scripts require:
 Numpy
 PIL (Python imaging library)
 Matplotlib
The library works under both Python 2 and 3.
Modules provided:
 tsp_solver.greedy : Basic greedy TSP solver in Python
 tsp_solver.greedy_numpy : Version that uses Numpy matrices, which reduces memory use, but performance is several percents lower
 tsp_solver.demo : Code for the demo applicaiton
Scripts provided
 demo_tsp : Generates random TSP, solves it and visualises the result. Optionally, result can be saved to the numpyformat file.
 tsp_numpy2svg : Generates neat SVG image from the numpy file, generated by the demo_tsp.
Both applications support a variety of commandline keys, run them with help option to see additional info.
Installation
Install from PyPi:
# pip install tsp_solver2
or
$ pip install user tsp_solver2
(Note taht tsp_solver package contains an older version).
Manual installation:
# python setup.py install
Alternatively, you may simply copy the tsp_solver/greedy.py to your project.
Usage
The library provides a greedy solver for the symmetric TSP. Basic usage is:
from tsp_solver.greedy import solve_tsp
#Prepare the square symmetric distance matrix for 3 nodes:
# Distance from A to B is 1.0
# B to C is 3.0
# A to C is 2.0
D = [[],
[1.0],
[2.0, 3.0]]
path = solve_tsp( D )
#will print [1,0,2], path with total length of 3.0 units
print(path)
The triangular matrix D
in the above example represents the following graph with three nodes A, B, and C:
Square matrix may be provided, but only left triangular part is used from it.
Utility functions
tsp_solver.util.path_cost(distance_matrix, path) Caclulate total length of the given path, using the provided distance matrix.
Using fixed endpoints
It is also possible to manually specify desired start and/or end nodes of the path. Note that this would usually increase total length of the path. Example, using the same distance matrix as above, but now requiring that path starts at A (index 0) and ends at C (index 2):
D = [[],
[1.0],
[2.0, 3.0]]
path = solve_tsp( D, endpoints = (0,2) )
#will print path [0,1,2]
print(path)
New in version 0.4: it is not possible to specify only one of two end points:
solve_tsp( D, endpoints = (None,2) )
solve_tsp( D, endpoints = (0,None) )
Round trip paths
To find a round trip path, that returns to the starting node, specify the same value to both endpoints:
path = solve_tsp( D, endpoints = (0,0) )
#will print path [0,1,2,0]
print(path)
Note that round trip paths are one step longer.
Neither solution quality nor complexity depends on the endpoints specified, so it is safe to use (0,0) when don't care.
Algorithm
The library implements a simple "greedy" algorithm:
 Initially, each vertex belongs to its own path fragment. Each path fragment has length 1.
 Find 2 nearest disconnected path fragments and connect them.
 Repeat, until there are at least 2 path fragments.
This algorightm has polynomial complexity.
Optimization
Greedy algorithm sometimes produces highly nonoptimal solutions. To solve this, optimization is provided. It tries to rearrange points in the paths to improve the solution. One optimization pass has O(n^4) complexity. Note that even unlimited number of optimization paths does not guarantees to find the optimal solution.
Performance
This library neither implements a stateoftheart algorithm, nor it is tuned for a high performance.
It however can find a decent suboptimal solution for the TSP with 4000 points in several minutes. The biggest practical limitation is memory: O(n^2) memory is used.
Demo
To see a demonstration, run
$ make demo
without installation. The demo requires Numpy and Matplotlib python libraries to be installed.
Testing
To execute unit tests, run
$ make test
Change log
Version 0.4.1
Added possibility to search for round trip paths, when endpoints coincide.
Version 0.4
Added possibility to specify only one of end points.
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for tsp_solver20.4.1py3noneany.whl
Algorithm  Hash digest  

SHA256  63eab1688f288cdf08ea145d39656f47e0412bb31da5e5075497f25ad4d214b7 

MD5  477a1a30b1a058f6f1c49681d187fa51 

BLAKE2256  b91758515f3c3105ce61c8ea4a544a312502c77ceee7f32affc9e7937446d787 