The traveling salesman problem

Suppose that we have a bidirectional complete directed graph (that is, for each pair of nodes a, b there is a directed arc from a to b) and a cost function on the arcs.

We would like to find a minimum cost Hamiltonian cycle in the graph. This is called the traveling salesman problem.

The TSP-related classes in Satsuma are: CheapestLinkTsp<TNode>, InsertionTsp<TNode>, Opt2Tsp<TNode>, HamiltonianCycle. They do not generally use the basic Satsuma types Node, Arc and IGraph, as the input graph in a TSP is always a bidirectional complete directed graph. Instead, there is a generic type parameter which is the type of the nodes to visit. TSP-solving classes like InsertionTsp<TNode> accept a collection of nodes and a cost function defined on node pairs, and produce a cost-effective visiting order of the supplied nodes.

TSP cost functions must always be finite. The algorithms generally perform well if the cost function is symmetric (that is, the cost of traveling from a to b is the same as traveling from b to a). In particular, they perform the best for metric cost functions (that is, the triangle inequality must hold as well).

Warning

As the traveling salesman problem is NP-hard, there is no known optimal polynomial solution, and it is unlikely that one exists. Therefore, all classes employ some kind of heuristic and the returned tours will be probably suboptimal.

The following example demonstrates how a reasonably cheap tour on Euclidean points can be found using a Satsuma TSP solver:

// create a node collection: in this example, they are geographical locations
var points = new PointD[]
{
    new PointD(47.50704, 19.04592),
    new PointD(47.50284, 19.03171),
    new PointD(47.472331, 19.062706),
    new PointD(47.515373, 19.082839)
};

// define a cost function: in this example, it is the Euclidean distance
Func<PointD, PointD, double> cost = (p, q) => p.Distance(q);

// create a TSP solver instance and calculate a tour
InsertionTsp<PointD> tsp = new InsertionTsp<PointD>(points, cost);
tsp.Run();
Console.WriteLine("Total tour cost: "+tsp.TourCost);
Console.WriteLine("Visiting order:");
foreach (PointD p in tsp.Tour()) Console.WriteLine(p);