LKHpy is a Python library for solving travelling salesman (TSP) and vehicle routing (VRP) problems based on [LKH 3]. The library aims to minimize overheads and optimize the communication between the LKH library written in C and the Python interface. All IO operations have been removed. The Python bindings of existing C code is done via pybind11. We added some performance improvements thanks to this customized version of LKH 3. If you find the code useful, please cite the original paper of Keld Helsgaun and consider giving this repo a star.

For those who are interested in developing the code, see doc.

Installation

Easy installation via pip

pip install LKHpy

Note

Built versions are tested against the latest Ubuntu and macOS. LKH 3 does not support Windows (no one should use Windows anyway), and neither does LKHpy. As a workaround, use WSL.

Usage

Import

import LKHpy as LK

Using cost matrix (distance matrix)

See PARAMETERS for parameter lists. Some custom parameters are defined by LKHpy and must start with '#'.

params = {
        '#SHOW_OUTPUT': False,
        'SPECIAL': '',
        'INITIAL_TOUR_ALGORITHM': 'NEAREST-NEIGHBOR',
        'MTSP_OBJECTIVE': 'MINMAX',
        'MAX_CANDIDATES': 6,
        'MAX_TRIALS': 10000,
        'SALESMEN': 2,
        'RUNS': 1,
        'TOTAL_TIME_LIMIT': 7}
cost_matrix = [[0, 1, 2], [1, 0, 3], [2, 3, 0]] # int
solution = LK.cost_matrix(cost_matrix, params)

Using coordinates

Euclid distance

coordinates = [[1, 2], [2, 1], [3, 3], [1, 3]] # int
solution = LK.euclid(coordinates, params)

GEOM and GEO distance (latitude longitude)

coordinates = [[0.1, 0.1], [0.2, 1.2], [1.3, 0.3]] # double
solution = LK.geo(coordinates, params)

coordinates = [[0.1, 0.1], [0.2, 1.2], [1.3, 0.3]] # double
solution = LK.geom(coordinates, params)

Using a .par file

See examples/par_file

solution = LK.par_file('example.par')

LKHpy custom parameters

Parameter	Meaning	Default
#SHOW_OUTPUT	Show output by LKH	False