Network analysis - Spatial Data Analysis: An Introduction for GIS Users - page 83

h e shortest distance for any node that has not yet been included as part of the
shortest route is 1.915. h is is the distance value for node 2 and node 2 is included
at this stage. Node 2 is connected to nodes 3 and 4. h e distance from node 1 to node 3
via node 2 is 1.915 + 0.890 = 2.805 and is smaller than the existing distance value for
node 3, so the distance value for node 3 is replaced and the parent node changed to 2.
Node 4 is already included so it is not considered. h e end result is the table 'At er
iteration 4.
h e distance of 2.634, for node 6, is the smallest distance for a non-included node.
Node 6 is included at this stage. Node 6 is connected to the remaining non-included
node, node 3. h e distance from node 1 to node 3 via nodes 4 and 6, however, is greater
than the existing distance value so it remains the same. h is is the i nal stage and
results in the table 'At er iteration 5.
h e distance values for each node are the shortest path distances to that node from
node 1. For example, the shortest path from node 1 to node 4 is 1.566 units while the
shortest path from node 1 to node 6 is via node 4 and is 2.634 units (1.566 + 1.068).
Wise (2002) and Chang (2008) provide further worked examples of the use of the
shortest path algorithm.

The travelling salesperson problem

6.6

h ere are many other methods for the analysis of networks that could be outlined. For
instance, algorithms for solving the so-called 'travelling salesperson problem' (TSP)
are ot en encountered in GIS textbooks. h e TSP entails i nding the shortest possible
route that visits each of a set of points once only and returns to the starting point. h e
number of possible routes increases markedly with the number of locations that must be
visited. Where there are n locations that must be visited, including the origin (e.g. the
depot), the number of possible routes is given by ( n - 1)!, where ! indicates the factorial
of a number. As an example, 3! is 3 ¥ 2 ¥ 1 = 6. In practice, most trips can be taken in
two directions and then the possible number of routes is given by ( n - 1)! / 2 (Longley et al. ,
2005a), so if there are eight locations to be visited, n - 1 = 7 and 7! = 7 ¥ 6 ¥ 5 ¥ 4 ¥ 3 ¥ 2 ¥
1 = 5040 and the number of possible routes is 5040 / 2 = 2520. In practice, for a large
number of places to visit, it is not feasible to identify the optimal route, but approaches
exist to rapidly identify routes that may not be the best, but which approach the opti-
mal route according to some criterion. Wise (2002) provides a summary of the TSP
and possible approaches to it.

Location-allocation problems

6.7

A major class of problems for which network analysis tools provide a solution is the
matching of resources to particular people or groups. h e term 'location-allocation'
refers to the location of facilities and the allocation of resources from a given facility