Steiner trees

Navigation:  Network and Location Analysis > Network Construction, Optimal Routes and Optimal Tours >

Steiner trees

Previous pageReturn to chapter overviewNext page

A feature of the MST solutions described is that they minimize network length for a spanning tree rather than minimizing the length of a network of straight line segments connecting all vertices that permits the inclusion of intermediate points. Adding intermediate points can reduce the total network length, by a factor of up to 3/2 for the L2 metric and 2/3 for the L1 metric. For example, any three neighboring vertices may be connected using an intermediate (or Steiner) point that will reduce their local MST, iff the angle between the two legs of the local MST is less than 120 degrees (Figure 7‑7A) and the vertices are unweighted. The optimum location for an intermediate point in this case is such that each link from the chosen point to the three vertices lies at an angle of 120 degrees from the other two — i.e. they are equally spaced (Figure 7‑7B).

Whilst an MST may be systematically modified in this manner, accepting solutions that reduce total network length, this will not necessarily result in a minimal length Steiner tree. Algorithms that commence with the original point set and examine a much wider range of options may yield significantly improved solutions. For example, taking 4 points at a time may identify solutions in which two additional points are warranted, with these points being themselves inter-linked. In the most general case, with m<=n-2 Steiner points and n vertices a very large number of alternative topologies are possible — over 60,000 with just n=7. The Steiner MST problem is NP-hard, although efficient approximation algorithms now exist. Such facilities are not provided in current GIS software — see for example, Robins and Zelikovsky (2000) for more details.

Figure 7‑7 Steiner MST construction

A. MST

B. MST with 1 Steiner point

clip0362.zoom50

clip0363.zoom50

Note that these networks and solution procedures assume that network flows and directions are not relevant, and that every vertex has equal weight. If vertices have unequal weights (e.g. number of beds in a hospital, demand for certain goods, or weight of material input for some manufacturing operation) then the Steiner point solution will be altered. In fact such problems have been described briefly earlier in this Guide, in connection with locating centroids using the L2 metric (Section 4.2.5, Centroids and centers). For n vertices each of which has an associated weight, wi, the least distance network in the plane from a single additional point (the point of minimum aggregate travel, MAT, or Weber point) is defined by coordinates that are determined iteratively.

The iteration equations for the MAT point, M6, are provided in Section 4.2.5, Centroids and centers. Typically the number of iterations required for convergence is very small (often 5 or fewer). This provides an example of a simple optimal location problem that is closely related to the Steiner network problem. If a pre-existing network is provided as part of the problem, and demand is located at the vertices, an optimal Weber point will always be found at a network vertex. An important generalization of this problem is the case where p locations are sought (e.g. warehouses) to service demand at n vertices (e.g. retail outlets). In this case the network-based version is known as the p-median problem. Such problems are discussed in more detail in Section 7.4, Location and Service Area Problems.