Overview
TravelingSalesmanHeuristics implements basic heuristics for the traveling salesman problem. TravelingSalesmanHeuristics implements the nearest neighbor, farthest insertion, and cheapest insertion strategies for path generation, the 2-opt strategy for path refinement, and a simulated annealing heuristic which can be used for path generation or refinement. A simple spanning tree type lower bound is also implemented.
When to use
Though the traveling salesman problem is the canonical NP-hard problem, in practice heuristic methods are often unnecessary. Modern integer programming solvers such as CPLEX and Gurobi can quickly provide excellent (even certifiably optimal) solutions. If you are interested in solving TSP instances to optimality, I highly recommend the JuMP package. The very slick TravelingSalesmanExact package implements the problem formulation and provides some nifty visualization utilities. Even if you are not concerned with obtaining truly optimal solutions, using a mixed integer programming solver is a promising strategy for finding high quality TSP solutions. If you would like to use an integer programming solver along with JuMP or TravelingSalesmanExact but don't have access to commercial software, HiGHS can work well.
Use of this package is most appropriate when you want decent solutions to small or moderate sized TSP instances with a minimum of hassle: one-off personal projects, if you can't install a mixed integer linear programming solver, prototyping, etc.
A word of warning: the heuristics implemented are
- heuristics, meaning you won't get any optimality guarantees and, except on very small instances, are unlikely to find the optimal tour;
- general purpose, meaning they do not take advantage of any problem specific structure;
- simple and (hopefully) readable but not terribly high performance, meaning you may have trouble with large instances. In particular the two-opt path refinement strategy slows down noticeably when there are >400 cities.
Installation
TravelingSalesmanHeuristics is a registered package, so you can install it with the REPL's Pkg mode: ]add TravelingSalesmanHeuristics. Load it with using TravelingSalesmanHeuristics.
Usage
All problems are specified through a square distance matrix D where D[i,j] represents the cost of traveling from the i-th to the j-th city. Your distance matrix need not be symmetric or non-negative.
Because problems are specified by dense distance matrices, this package is not well suited to problem instances with sparse distance matrix structure, i.e. problems with large numbers of cities where each city is connected to few other cities.
TravelingSalesmanHeuristics supports distance matrices with arbitrary real element types: integers, floats, rationals, etc. However, mixing element types in your distance matrix is not recommended for performance reasons.
TravelingSalesmanHeuristics does not support distance matrices with arbitrary indexing; indices must be 1:n in both dimensions for n cities.
The simplest way to use this package is with the solve_tsp function:
TravelingSalesmanHeuristics.solve_tsp — Functionsolve_tsp(distmat; quality_factor = 40)Approximately solve a TSP by specifying a distance matrix. Return a tuple (path, cost).
The optional keyword quality_factor (real number in [0,100]; defaults to 40) specifies the tradeoff between computation time and quality of solution returned. Higher values tend to lead to better solutions found at the cost of more computation time.
It is not guaranteed that a call with a high quality_factor will always run slower or return a better solution than a call with a lower quality_factor, though this is typically the case. A quality_factor of 100 neither guarantees an optimal solution nor the best solution that can be found via extensive use of the methods in this package.
TravelingSalesmanHeuristics does not support distance matrices with arbitrary indexing; indices must be 1:n in both dimensions for n cities.
See also: individual heuristic methods such as farthest_insertion
See here for some benchmarks of different quality_factors on various instances.