Skip to main content

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 sub-optimal 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 numpy-format file.
  • tsp_numpy2svg : Generates neat SVG image from the numpy file, generated by the demo_tsp.

Both applications support a variety of command-line 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:

  1. Initially, each vertex belongs to its own path fragment. Each path fragment has length 1.
  2. Find 2 nearest disconnected path fragments and connect them.
  3. Repeat, until there are at least 2 path fragments.

This algorightm has polynomial complexity.

Optimization

Greedy algorithm sometimes produces highly non-optimal 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 state-of-the-art 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

tsp_solver2-0.4.1.tar.gz (13.4 kB view details)

Uploaded Source

Built Distribution

tsp_solver2-0.4.1-py3-none-any.whl (13.4 kB view details)

Uploaded Python 3

File details

Details for the file tsp_solver2-0.4.1.tar.gz.

File metadata

  • Download URL: tsp_solver2-0.4.1.tar.gz
  • Upload date:
  • Size: 13.4 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.2.0 pkginfo/1.5.0.1 requests/2.22.0 setuptools/49.1.1 requests-toolbelt/0.9.1 tqdm/4.47.0 CPython/3.8.1

File hashes

Hashes for tsp_solver2-0.4.1.tar.gz
Algorithm Hash digest
SHA256 96e5814b9a06c44f5dd89a0d83bf2b9be0f7a65740d8956975de5f9ce402922e
MD5 e3045f033b2a7ca3083e7a204fac40c0
BLAKE2b-256 7ed65a9a87fe672381a78c5ed1bb8d4e0b42e0748013de48aafc016bb8ac50c5

See more details on using hashes here.

File details

Details for the file tsp_solver2-0.4.1-py3-none-any.whl.

File metadata

  • Download URL: tsp_solver2-0.4.1-py3-none-any.whl
  • Upload date:
  • Size: 13.4 kB
  • Tags: Python 3
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.2.0 pkginfo/1.5.0.1 requests/2.22.0 setuptools/49.1.1 requests-toolbelt/0.9.1 tqdm/4.47.0 CPython/3.8.1

File hashes

Hashes for tsp_solver2-0.4.1-py3-none-any.whl
Algorithm Hash digest
SHA256 63eab1688f288cdf08ea145d39656f47e0412bb31da5e5075497f25ad4d214b7
MD5 477a1a30b1a058f6f1c49681d187fa51
BLAKE2b-256 b91758515f3c3105ce61c8ea4a544a312502c77ceee7f32affc9e7937446d787

See more details on using hashes here.

Supported by

AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Pingdom Monitoring Sentry Error logging StatusPage Status page