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 LKHusing 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 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 the TSPLIB format:
using LKH
opt_tour, opt_len = solve_tsp("gr17.tsp")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)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)- Concorde.jl: Julia wrapper of the Concorde TSP Solver.
- LKH.jl: Julia wrapper of the LKH heuristic solver.
- TSPLIB.jl: Reads TSPLIB-format files (
*.tsp) - CVRPLIB.jl: Reads TSPLIB-format files from CVRPLIB
- TravelingSalesmanExact.jl: Julia implementation of Dantzig, Fulkerson, and Johnson's Cutting-Plane Method.