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.

import numpy as np
import elkai

M = np.zeros((3, 3), dtype=int)
M[0, 1] = 4
M[1, 2] = 5

solution = elkai.solve_int_matrix(M)

print(solution)
# Output: [0, 2, 1]

graph TD;
    0-->|4|1;
    1-->|0|0;
    0-->|0|2;
    1-->|5|2;
    2-->|0|1;

elkai.solve_int_matrix(matrix: List[List[int]], runs=10) -> List

• matrix is a list of lists or 2D numpy array containing the distances between cities
• runs is the solver iteration count

An example matrix with 3 cities would be:

[                 # cities are zero indexed, d() is distance
   [0, 4,  3],    # d(0, 0), d(0, 1), d(0, 2)
   [4, 0, 10],    # d(1, 0), d(1, 1), ...
   [2, 4,  0]     # ... and so on
]

So, the output would be [0, 2, 1] because it's best to visit 0 => 2 => 1 => 0.

⚠️ The final return to the start is implied and is NOT part of the output list, i.e. len(output) == N

elkai.solve_float_matrix(matrix: List[List[float]], runs=10) -> List

Same behaviour as above, with float distances supported. Note that there may be precision issues.

How to manually build the library?

You need CMake, a C compiler and Python 3.5+. You need to install the dev dependencies first: pip install scikit-build ninja. To build and install, run python setup.py install.

How accurately does it solve asymmetric TSP problems?

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

What's the difference between LKH and elkai?

elkai packages the C LKH code into a nicer C library and then wraps it and compiles it into a Python wheel. Note: Dr. Helsgaun has released the LKH project for non-commercial use only, so elkai as a derivative work must be used this way too.

Does it lock the GIL during a run?

Yes.