Media Coverage
July 2010
The Benefits and Challenges of Steiner Trees
Those of you who have been reading this column for a long time will know that I am particularly fond of logistical problems that are inherently difficult to solve. I was recently working on one of these and thought that it would be interesting to share some of the details.
The problem is as follows: assume we have a set of towns as in the figure below and we need to design distribution lanes such that all the towns are connected. More simply, think of adding in pipelines to connect all the towns using the minimum amount of pipe. This same problem can arise when building computer-, phone- or water-distribution networks. In logistics you can think of examples where distribution lanes need to be established between the town at minimal cost.
To find the least cost solution (the one that uses the least pipe), a simple algorithm can be used. The algorithm starts by connecting the two closest towns and then continues to find the shortest link that does not create a cycle and joining those towns until all the towns are connected. This is known as the minimum spanning tree algorithm or MST. The result of the MST is shown below.
This is a very useful algorithm, but if we are allowed a little bit more freedom in how we build the pipe network we can get a better solution. One obvious extension is to say, let us not restrict ourselves to only having pipes go between towns directly, but allow the introduction of new points that the pipes can go through. These can also be thought of as cross-docks in the logistics context. If we allow these points to go anywhere and do not restrict the number of points, we can get better (lower cost) solutions. These new points are called Steiner points. In the figure, the points in blue are the newly introduced Steiner points and the Steiner tree is shown in the third frame of the figure.
The total length of pipe in the MST is 18 units; for the Steiner tree it is 17.6 units. While this seems like a minor saving of a few percent, in larger problems the savings can be significant. But finding Steiner points involves two problems; how many Steiner points should be used and where should they be placed.
Unfortunately, finding the answer to these questions is very hard. Finding the Steiner point is another one of the famous NP hard problems, like finding the best travelling salesman route. So, as the number of towns increases, the complexity of finding the solution rises exponentially. Even with a moderate number of towns, it becomes impractical to find an optimal solution. However, like the Travelling Salesman Problem, there are very good heuristic approaches to find approximate solutions for large problem.
If you have any comments or questions, please e-mail me at david.lubinsky@opsi.co.za.
