nearest_neighbor(distmat)

Approximately solve a TSP using the nearest neighbor heuristic. distmat is a square real matrix where distmat[i,j] represents the distance from city i to city j. The matrix needn't be symmetric and can contain negative values. Return a tuple (path, pathcost).

Optional keyword arguments:

• firstcity::Union{Int, Nothing}: specifies the city to begin the path on. Passing nothing or not specifying a value corresponds to random selection.
• closepath::Bool = true: whether to include the arc from the last city visited back to the first city in cost calculations. If true, the first city appears first and last in the path.
• do2opt::Bool = true: whether to refine the path found by 2-opt switches (corresponds to removing path crossings in the planar Euclidean case).

farthest_insertion(distmat; ...)

Generate a TSP path using the farthest insertion strategy. distmat must be a square real matrix. Return a tuple (path, cost).

Optional arguments:

• firstCity::Int: specifies the city to begin the path on. Not specifying a value corresponds to random selection.
• do2opt::Bool = true: whether to improve the path by 2-opt swaps.

cheapest_insertion(distmat::Matrix, initpath::AbstractArray{Int})

Given a distance matrix and an initial path, complete the tour by repeatedly doing the cheapest insertion. Return a tuple (path, cost). The initial path must have length at least 2, but can be simply [i, i] for some city index i which corresponds to starting with a loop at city i.

Currently the implementation is a naive $n^3$ algorithm.

cheapest_insertion(distmat; ...)

Complete a tour using cheapest insertion with a single-city loop as the initial path. Return a tuple (path, cost).

Optional keyword arguments:

• firstcity::Union{Int, Nothing}: specifies the city to begin the path on. Passing nothing or not specifying a value corresponds to random selection.
• do2opt::Bool = true: whether to improve the path found by 2-opt swaps.

two_opt(distmat, path)

Improve path by doing 2-opt switches (i.e. reversing part of the path) until doing so no longer reduces the cost. Return a tuple (improved_path, improved_cost).

On large problem instances this heuristic can be slow, but it is highly recommended on small and medium problem instances.

See also simulated_annealing for another path generation heuristic.

simulated_annealing(distmat; ...)

Use a simulated annealing strategy to return a closed tour. The temperature decays exponentially from init_temp to final_temp. Return a tuple (path, cost).

Optional keyword arguments:

• steps::Int = 50n^2: number of steps to take; defaults to 50n^2 where n is number of cities
• num_starts::Int = 1: number of times to run the simulated annealing algorithm, each time starting with a random path, or init_path if non-null. Defaults to 1.
• init_temp::Real = exp(8): initial temperature which controls initial chance of accepting an inferior tour.
• final_temp::Real = exp(-6.5) final temperature which controls final chance of accepting an inferior tour; lower values roughly correspond to a longer period of 2-opt.
• init_path::Union{Vector{Int}, Nothing} = nothing: path to start the annealing from. Either a Vector{Int} or nothing. If a Vector{Int} is given, it will be used as the initial path; otherwise a random initial path is used.

repetitive_heuristic(distmat::Matrix, heuristic::Function, repetitive_kw::Symbol; keywords...)

For each i in 1:n, run heuristic with keyword repetitive_kw set to i. Return the tuple (bestpath, bestcost). By default, repetitive_kw is :firstcity, which is appropriate for the farthest_insertion, cheapest_insertion, and nearest_neighbor heuristics.

Any keywords passed to repetitive_heuristic are passed along to each call of heuristic. For example, repetitive_heuristic(dm, nearest_neighbor; do2opt = true) will perform 2-opt for each of the n nearest neighbor paths.

lowerbound(distmat)

Lower bound the cost of the optimal TSP tour. At present, the bounds considered are a simple bound based on the minimum cost of entering and exiting each city and a slightly better bound inspired by the Held-Karp bounds; note that the implementation here is simpler and less tight than proper HK bounds.

The Held-Karp-inspired bound requires computing many spanning trees. For a faster but typically looser bound, use TravelingSalesmanHeuristics.vertwise_bound(distmat).