The optimal tours described in Section 7.3.4 are subsets of a more general class of problem, the travelling salesman problem (TSP). The TSP involves making a tour of every vertex in a given set, returning to the starting point, such that the tour length is minimized. Applications include: salesmen visiting customers; rubbish trucks servicing business premises; delivery trucks servicing retail outlets; security staff patrolling premises and many more. There are many non-geographic applications, ranging from VLSI design to the analysis of DNA sequences. The majority of geographic instances involve modest numbers of locations to visit (e.g. stores, cities) but variants of the problem (e.g. the need to dispatch multiple vehicles from a central depot on tours to visit their own subset of stores) can increase the problem complexity substantially. Pure TSP problems (i.e. based on a point set with no pre-defined network) are not supported within GIS packages. Where such networks are defined, very few GIS packages provide TSP functionality — one exception being TransCAD. An excellent introduction to TSP problems and solutions is provided by William Cook, one of the authors of the Concorde software package described later in this subsection) at: http://www.tsp.gatech.edu/index.html

Since every TSP tour involves visiting each location once, deleting one link from this tour will leave a spanning tree. This tree must be at least as long as the MST and will typically be longer (an upper bound for symmetric planar graphs is 1.5 times the MST length). The number, t, of possible tours with a symmetric (i.e. non-directed) graph consisting of n vertices is t=(n‑1)!/2. This number grows extremely rapidly with n and cannot realistically be systematically evaluated for large n. For example, with n=10, t=181,440. Solving the problem exactly is thus an O(n!) problem and has been shown to be NP-complete. An internationally collated set of test problems are provided in the dataset known as TSPLIB. These include test datasets for symmetric and asymmetric TSPs, HCPs, SOPs and CVRPs. See www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/ for more details.

A formal statement of the basic TSP is:

where c_ij is the cost of travel from i to j (e.g. cost weighted distance), and x_ij=1 if a direct link exists from i to j in a tour, or 0 otherwise. Here n is the number of sites in the tour, where typically i=1 is the tour start point (e.g. a depot) and i=2,3,...n are the sites to be visited (e.g. customers).

Solutions of many TSP problems have certain attributes that may be used to assist algorithm development. These include the fact that the TSP for a point set, S, must lie entirely within the convex hull of the set, and any vertices located on this hull must be traversed such that their clockwise or anti-clockwise sequential arrangement is preserved. Clearly also the TSP must not be self-intersecting. Heuristic solutions, notably the Lin-Kernighan or LK-heuristic, which is a development of the n-opt heuristic, make use of any self-intersections that are found to generate an improved solution with the self-intersection removed by a form of symmetric resequencing or flipping of the order of visited nodes. The result is a very fast approximate algorithm that yields exact or near exact solutions for many problems. Exact algorithms also exist, some of which are fast. Concorde, cited earlier, uses a procedure based on linear programming and cutting plane techniques to obtain exact solutions to relatively large problems (many 1000s of vertices). This code, which is very fast with moderate-sized problems, is amongst the best available. However, users should be aware that rounding issues exist in its treatment of decimal coordinates - to avoid problems it is advisable to multiply all values by one or more powers of 10 before undertaking analyses.

There are close relationships between the generation of the Delaunay triangulations, the generation of MSTs and the solution of Euclidean (plane) TSPs. This was noted earlier on in the research into TSP heuristics, and forms the basis of some methods. To illustrate this linkage we will use a test dataset from TSPLIB consisting of n=130 vertices (CH130.TSP). Figure 7‑11 illustrates several aspects of these relationships. Figure 7‑11A shows the source point set and Figure 7‑11B gives the Delaunay triangulation (DT) of this set. The total length of the edges in the triangulation is 30157 units.

Figure 7‑11C and Figure 7‑11D show the minimum spanning tree (MST) for the point set, produced using the Concorde software and overlain on the DT. The MST consists of 129 edges with a total length of 5166 units. Figure 7‑11E and Figure 7‑11F show the same pair, but in this case showing the exact TSP solution obtained using the linear programming and cutting planes method that is implemented in Concorde. Processing on a modestly powered desktop PC was completed in a few seconds. The total number of edges in this case was 130 with a total length of 6110 units.

Finally, Figure 7‑12A shows the solution provided using the LK heuristic, which was generated almost instantly for this problem. Notice that the top right corner of this solution differs slightly from that of the exact solution in Figure 7‑11F. This solution also has 130 edges but a slightly greater length of 6124 units. In all cases edge weights were computed using symmetric Euclidean distances. Interestingly, with a random pattern of n points with an MBR that has area A, the expected length of the Euclidean TSP has been estimated as:

For the example illustrated in Figure 7‑11A n=130 and A=471,937 units, giving an expected tour length if the point set were random of 5874 units. The optimal result is slightly greater than this, reflecting the fact that the point set is slightly more uniform than random. With the Manhattan or L₁ metric the expected tour length is greater, being the same general expression but with k»19/20.