Many utilities face the problem of designing distribution networks.  These networks need to reach all (or nearly all) households to distribute (or collect) the commodity supplied by the utility.  This may be electricity, gas, water, data (cable or optical fibre) or sewerage.

Typically these distribution networks are built as a subset of some underlying network.  Most commonly this is the street network.  The reason for this is obvious – the street network connects all households and businesses – which are the final demand points of utilities.  Some networks may piggyback on existing networks.  For example an optical fibre rollout may be done using existing power poles.

From a mathematical point of view we can consider the underlying points of demand (households or small collections of households) as nodes in a graph.  The potential connections between these nodes are arcs.  We refer to this network of potential connections as the underlying network.  If the distribution network can be represented as a tree (and this is often the case) then the problem of determining the best distribution network is similar to the minimum spanning tree problem solved on the underlying network (http://en.wikipedia.org/wiki/Minimum_spanning_tree).  This problem is straightforward to solve with an algorithm that is relatively easy to understand.  The main information required is the cost of the candidate arcs.  For example, it may be relatively cheap to string new cable between existing poles (for electricity or data networks), but much more expensive to dig a trench to install cable underground in an area with no overhead poles.

The problem faced by a utility will however have many practical considerations that cannot be handled by the classical minimum spanning tree algorithm.  These will include:

• The problem is really one of building several spanning trees, each of which can handle a maximum demand.  This arises because of underlying technical restrictions such as transformer capacity; the need to have pumping stations for water, gas and sewerage; the maximum number of optical fibre connections to a hub; etc.
• The cost of arcs in the tree depends on the downstream demand.  This arises because the pipes or cables need to get bigger as the tree collects more downstream demand.
• Splitting nodes in the tree may be expensive.  This can occur because of splicing costs (in optical fibre networks) or the need to distribute pressure evenly.
• The spanning trees will themselves need to be connected back to the “mains” network.  Indeed the problem of designing the mains network may need to be considered as part of the overall problem, though typically most of the cost will be in the feeder network due to the sheer number of connections required.
• The maximum network length from the mains to a node is limited due to pressure/voltage losses.

Recently Biarri has undertaken a Proof of Concept project with a utility to look at designing a distribution network.  We have formulated and solved an optimisation based approach to give solutions guaranteed to be within a very small margin of the optimal solution.  On a sample network covering around 2000 households we were able to achieve:

• An optimal solution in two minutes on standard PC’s
• 6% reduction in equipment costs
• Huge reduction in planning effort – it took many man weeks to design the same area by hand

The speed of the solution process frees up the network designer to consider higher level issues that are not part of the optimisation model, such as the possible saving from using different technical approaches.  These choices can be modelled as a series of “What if…?” scenarios.

We plan to extend the work done so far to cover even more of the practical issues faced by utilities.  A technical paper covering the work will be prepared in 2010.