Traveling Salesperson Problem

This is an example of the classic traveling salesperson problem.

Formally, we are given a set of n nodes V (points, vertices, cities, holes), and a distance function $D:V\times V\rightarrow \Re$giving travel time between any given pair of nodes.

We want to find a tour (Hamiltonian circuit, permutation) of the nodes $v_1,\ldots,v_n$ such that $\sum_{i=1}^{n-1} D(v_i,v_{i+1}) + D(v_n,v_1)$ is minimized. It's the shortest trip that visits every city once and only once.

We'll assume the distance function D is symmetric: D(u,v)=D(v,u) for all u and v in V.

In the metric TSP, we additionally assume that distances obey the triangle inequality: for all u and v and w in V, $D(u,v) \le D(u,w)+D(w,v)$ (shortcut is never worse).