LKH.jl

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

LKH.jl

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.

Installation

`] 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):

```using CVRPLIB, LKH
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)```