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
print(elkai.solve_int_matrix(M))
# Output: [0, 2, 1]
elkai.solve_int_matrix(matrix, runs=10):
-
matrix
: an N*N matrix representing an integer distance matrix between cities.- N=3 example: (can be any indexed structure: list, numpy array etc)
[ # 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. -
Returns: The tour represented as a list of indices. The indices are zero-indexed and based on the distance matrix order.
elkai.solve_float_matrix(matrix, runs=10) has the same signature as the previous, but allows floating point distances. It may be inaccurate.
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.