PyTSP.jl

An interface to Conrcorde TSP solver
Author chkwon
Popularity
1 Star
Updated Last
2 Years Ago
Started In
August 2020

PyTSP.jl

Build Status codecov

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.

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

Used By Packages

No packages found.