Skip to main content

A TSP solver for Python without any dependencies.

Project description

elkai - a Python 3 TSP solver

elkai is a Python 3 library for solving travelling salesman problems without external dependencies, based on LKH by Keld Helsgaun.

💾 To install it run pip install elkai

💻 Supported platforms: elkai is available on Windows, Linux, OS X for Python 3.5 and above as a binary wheel.

Build status image

Example usage

import elkai
elkai.solve_int_matrix([
    [1, 1],
    [1, 1]
]) # Output: [0, 1]

Documentation

solve_int_matrix(matrix, runs=10) solves an instance of the asymmetric TSP problem with integer distances.

  • matrix: an N*N matrix representing an integer distance matrix between cities.

    An example of N=3 city arrangement:

    [                  # cities are zero indexed, d() is distance
        [0, 4,  9],    # d(0, 0), d(0, 1), d(0, 2)
        [4, 0, 10],    # d(1, 0), d(1, 1), ...
        [2, 4,  0]     # ... and so on
    ]
    
  • runs: An integer representing how many iterations the solver should perform. By default, 10.

  • Return value: The tour represented as a list of indices. The indices are zero-indexed and based on the distance matrix order.

solve_float_matrix(matrix, runs=10) has the same signature as the previous, but allows floating point distances. It may be inaccurate.

FAQ

What's the difference between LKH and elkai?

elkai is a library that contains the LKH solver and has some wrapper code to expose it to Python. The advantage is that you don't have to compile LKH yourself or download LKH executables and then manually parse the output.

How accurately does it solve TSP problems?

Instances with known solutions, which are up to N=315 cities, can be solved optimally.

Can you run multiple threads?

The library doesn't not release the GIL during the solution search, so other threads will be blocked. If you want to solve multiple problems concurrently you may try the multiprocessing module.

P.S.: The LKH solver was written in C with one problem per process in mind. We try to clean up the global state before and after solving a problem, but leaks are possible - if you want to help out, run Valgrind or similar diagnostics and submit an issue/PR.

Project details


Release history Release notifications

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for elkai, version 0.0.7
Filename, size & hash File type Python version Upload date
elkai-0.0.7-cp35-cp35m-macosx_10_6_x86_64.whl (95.1 kB) View hashes Wheel cp35
elkai-0.0.7-cp35-cp35m-manylinux1_x86_64.whl (94.9 kB) View hashes Wheel cp35
elkai-0.0.7-cp35-cp35m-win32.whl (80.6 kB) View hashes Wheel cp35
elkai-0.0.7-cp35-cp35m-win_amd64.whl (91.8 kB) View hashes Wheel cp35
elkai-0.0.7-cp36-cp36m-macosx_10_6_x86_64.whl (95.1 kB) View hashes Wheel cp36
elkai-0.0.7-cp36-cp36m-manylinux1_x86_64.whl (94.9 kB) View hashes Wheel cp36
elkai-0.0.7-cp36-cp36m-win32.whl (80.6 kB) View hashes Wheel cp36
elkai-0.0.7-cp36-cp36m-win_amd64.whl (91.8 kB) View hashes Wheel cp36
elkai-0.0.7-cp37-cp37m-macosx_10_6_x86_64.whl (95.1 kB) View hashes Wheel cp37
elkai-0.0.7-cp37-cp37m-manylinux1_x86_64.whl (94.9 kB) View hashes Wheel cp37
elkai-0.0.7-cp37-cp37m-win32.whl (80.6 kB) View hashes Wheel cp37
elkai-0.0.7-cp37-cp37m-win_amd64.whl (91.8 kB) View hashes Wheel cp37
elkai-0.0.7.tar.gz (81.7 kB) View hashes Source None

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN SignalFx SignalFx Supporter DigiCert DigiCert EV certificate StatusPage StatusPage Status page