LKH.jl

A Julia wrapper for the Lin-Kernighan-Helsgaun (LKH) solver.
Author chkwon
Popularity
2 Stars
Updated Last
1 Year Ago
Started In
November 2020

LKH.jl

Build Status codecov

This package provides a Julia wrapper for the LKH library for solving Traveling Salesman Problems (TSP).

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

Installation

] add LKH

Usage

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 have not been 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)

Related Projects