PyTSP.jl

This Julia package provides access to the Concorde TSP Solver and the Lin-Kernighan-Held (LKH) solver via pyconcorde and elkai, respectively.

As both PyConcorde and elkai are Python libraries, this package merely provides a Julia wrapper using PyCall.jl.

In Windows, this package does not work. Consider using Windows Subsystem for Linux (WSL).

Note: Now, there are direct Julia wrappers of Concorde and LKH, which work in Windows, macOS, and Linux 64-bit systems.

• Concorde.jl: Julia wrapper of the Concorde TSP Solver.
• LKH.jl: Julia wrapper of the LKH heuristic solver.

License

MIT License only applies to PyTSP.jl. The Python parts, PyConcorde and elkai, come in difference licenses. The underlying solvers, the Conrcorde TSP Solver and LKH, require special licenses for commercial usage. Please check their websites.

Installation

] add PyTSP

Usage

Concorde

Concorde uses integers for distance calculation. Your (x, y) coordinate inputs should be scaled appropriately.

using PyTSP
n_cities = 20
factor = 1e5
x = rand(n_cities) .* factor
y = rand(n_cities) .* factor

# The Concorde TSL Solver via pyconcorde
tour, len = solve_TSP_Concorde(x, y, norm="EUC_2D")

([1, 2, 19, 13, 18, 11, 4, 14, 7, 6, 15, 10, 8, 16, 20, 5, 9, 3, 12, 17], 389803)

LKH

Since LKH also benefits from integer inputs, this package uses integer as default.

using PyTSP
n_cities = 20
factor = 1e5
x = rand(n_cities) .* factor
y = rand(n_cities) .* factor

# The LKH  heuristic solver via elkai
tour_LKH, length_LKH = solve_TSP_LKH(x, y)

([1, 2, 19, 13, 18, 11, 4, 14, 7, 6, 15, 10, 8, 16, 20, 5, 9, 3, 12, 17], 389803)

You can also input a distance matrix, either Matrix{Int} or Matrix{Float64}.

using PyTSP
n_cities = 20
factor = 1e5
x = rand(n_cities) .* factor
y = rand(n_cities) .* factor

M = distance_matrix(x, y) # returns a rounded Matrix{Int}
tour_LKH, length_LKH = solve_TSP_LKH(M)

N = distance_matrix_float(x, y) # returns a Matrix{Float64}
tour_LKH, length_LKH = solve_TSP_LKH(N)

Related Projects

• 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)
• PyTSP.jl: Julia wrapper of Python TSP libraries: pyconcorde and elkai, which are Python wrappers of the Concorde and LKH solvers, respectively.
• TravelingSalesmanExact.jl: Julia implementation of Dantzig, Fulkerson, and Johnson's Cutting-Plane Method.