TravelingSalesmanExact.jl

ATT(city1, city2)

The ATT distance measure as specified in TSPLIB: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp95.pdf.

euclidean_distance(city1, city2)

The usual Euclidean distance measure.

find_cycle(perm_matrix, starting_ind)

Returns the cycle in the permutation described by perm_matrix which includes starting_ind.

get_ATT48_cities() -> Vector{Vector{Int}}

A simple helper function to get the problem data for the ATT48 TSPLIB problem.

Example

julia> using TravelingSalesmanExact, HiGHS

julia> cities = TravelingSalesmanExact.get_ATT48_cities()
48-element Vector{Vector{Float64}}:
 [6734.0, 1453.0]
 [2233.0, 10.0]
 [5530.0, 1424.0]
 [401.0, 841.0]
 [3082.0, 1644.0]
 [7608.0, 4458.0]
 [7573.0, 3716.0]
 [7265.0, 1268.0]
 [6898.0, 1885.0]
 [1112.0, 2049.0]
 ⋮
 [6271.0, 2135.0]
 [4985.0, 140.0]
 [1916.0, 1569.0]
 [7280.0, 4899.0]
 [7509.0, 3239.0]
 [10.0, 2676.0]
 [6807.0, 2993.0]
 [5185.0, 3258.0]
 [3023.0, 1942.0]

julia> get_optimal_tour(cities, HiGHS.Optimizer, distance = TravelingSalesmanExact.ATT)
([5, 42, 24, 10, 45, 35, 4, 26, 2, 29  …  30, 36, 46, 33, 20, 47, 21, 32, 39, 48], 10628.0)

get_cycles(perm_matrix)

Returns a list of cycles from the permutation described by perm_matrix.

get_default_optimizer()

Gets the default optimizer, which is set by set_default_optimizer.

get_optimal_tour(
    cities::AbstractVector,
    optimizer = get_default_optimizer();
    distance = euclidean_distance,
    kwargs...
)

get_optimal_tour(
    cost::AbstractMatrix
    optimizer = get_default_optimizer();
    kwargs...
)

Solves the travelling salesman problem for a list of cities using JuMP by formulating a MILP using the Dantzig-Fulkerson-Johnson formulation and adaptively adding constraints to disallow non-maximal cycles. Returns an optimal tour and the cost of the optimal path. Optionally specify a distance metric.

The second argument is mandatory if a default optimizer has not been set (via set_default_optimizer). This argument should be a function which creates an optimizer, e.g.

get_optimal_tour(cities, HiGHS.Optimizer)

There are five boolean optional keyword arguments:

• verbose (default: false) indicates whether or not to print lots of information as the algorithm proceeds.
• symmetric indicates whether or not the cost matrix is symmetric. By default, issymmetric is used to check.
• lazy_constraints indicates whether lazy constraints should be used (which requires a compatible solver, like GLPK).
• slow artificially sleeps after each solve to slow down the output for visualization purposes. Only takes affect if verbose==true.
• silent_optimizer calls JuMP.set_silent on the resulting model to prevent the optimizer from emitting logging information.
• heuristic_warmstart=true: whether or not to warmstart the solves using a heuristic solution. Not supported by all solvers.

Example

julia> using TravelingSalesmanExact, HiGHS, LinearAlgebra

julia> set_default_optimizer!(HiGHS.Optimizer)
HiGHS.Optimizer

julia> cities = [[0, 0], [0, 1], [1, 1], [1, 0]]
4-element Vector{Vector{Int64}}:
 [0, 0]
 [0, 1]
 [1, 1]
 [1, 0]

julia> tour, cost = get_optimal_tour(cities)
([4, 1, 2, 3], 4.0)

julia> cost_matrix = [norm(cities[i] - cities[j]) for i = 1:4, j = 1:4]
4×4 Matrix{Float64}:
 0.0      1.0      1.41421  1.0
 1.0      0.0      1.0      1.41421
 1.41421  1.0      0.0      1.0
 1.0      1.41421  1.0      0.0

julia> tour, cost = get_optimal_tour(cost_matrix)
([4, 1, 2, 3], 4.0)

plot_cities(cities)

Uses UnicodePlots's lineplot to make a plot of the tour of the cities in cities, in order (including going from the last city back to the first).

show_tour(cities, perm_matrix)

Show a plot of the tour described by perm_matrix of the cities in the vector cities.

remove_cycles!(model, solutions)

Find the (non-maximal-length) cycles in the current solutions solutions and add constraints to the JuMP model to disallow them. Returns the number of cycles found.

set_default_optimizer(O)

Sets the default optimizer. For example,

using HiGHS
set_default_optimizer(HiGHS.Optimizer)

simple_parse_tsp(filename; verbose = true)

Try to parse the ".tsp" file given by filename. Very simple implementation just to be able to test the optimization; may break on other files. Returns a list of cities for use in get_optimal_tour.