A Julia wrapper for the Lin-Kernighan-Helsgaun (LKH) solver.
Author chkwon
11 Stars
Updated Last
6 Months Ago
Started In
November 2020


Build Status codecov

This package provides a Julia wrapper for the LKH-3 library for solving Traveling Salesman Problems (TSP) and various Vehicle Routing Problems (VRPs).

While this Julia package is under MIT License, the underlying LKH library comes in a different license. Check with the LKH library homepage.


] add LKH

Usage for TSP

Using a distance matrix

using LKH
M = [
    0  16   7  14
   16   0   3   5
    7   3   0  16
   14   5  16   0 
opt_tour, opt_len = solve_tsp(M)

The distance matrix M can be either symmetric or asymmetric, but must be integer-valued.

Using coordinates

using LKH
n_nodes = 10
x = rand(n_nodes) .* 10000
y = rand(n_nodes) .* 10000
opt_tour, opt_len = solve_tsp(x, y; dist="EUC_2D")
opt_tour, opt_len = solve_tsp(x, y; dist="MAN_2D")
opt_tour, opt_len = solve_tsp(x, y; dist="MAX_2D")
opt_tour, opt_len = solve_tsp(x, y; dist="GEO")

Available dist functions are listed in TSPLIB_DOC.pdf. (Some may not be implemented in this package.)

Using a TSPLIB format file input

Using the TSPLIB format:

using LKH
opt_tour, opt_len = solve_tsp("gr17.tsp")

Passing solver parameters

In all cases, solver parameters are passed as keyword arguments.

opt_tour, opt_len = solve_tsp(M; INITIAL_TOUR_ALGORITHM="GREEDY", RUNS=5, TIME_LIMIT=10.0)

Usage for VRPs

For example, for the Capacitated Vehicle Routing Problem (CVRP):

cvrp, vrp_file_path, solution_file_path = readCVRP("E-n101-k14")
@time opt_tour, opt_len = solve_tsp(vrp_file_path, TIME_LIMIT=1.0)

Related Projects