MP in Action‎ > ‎Other Applications‎ > ‎

Simulation and Optimization Join Forces to Schedule London's Water

This article is based on a talk given by David Burnell, Manager of the Corporate Modelling Group of Thames Water to the Mathematical Programming Study Group.

London Ring Main

Thames Water inherited a water distribution network for London which was developed by the Victorians. This was based on trunk mains radiating from four main water treatment works. Some of the pipes were 100 years old and could no longer be relied upon to meet constantly rising demand. Rather than simply replacing pipes (which would have caused enormous disruption), Thames Water decided to build the London Ring Main, a 2.5m diameter tunnel 80km long running 45m below London.

Before the Ring Main was built, the distribution of London's water had involved few choices. Demand caused water levels to fall at the local service reservoirs, which had to be refilled from the trunk mains which supplied them. The Ring Main tied together the separate distribution trees creating for the first time a true network in which there are multiple options as to how to meet demand in an area.

There are five locations where water can be poured into the Ring Main and 11 where it can be pumped out. Water flows around it under pressure and the only active components are the pumps on the output shafts. The problem which Thames Water faced was therefore to determine for each of the 5 input shafts how much water to pour into the Ring Main and when, and for each of the 11 output shafts how much to pump out and when.

Formalising the Problem

In practice the problem of scheduling the Ring Main cannot be considered separately from the problem of scheduling London's other trunk mains. This is because the Ring Main provides an alternative way of delivering water and the costs of both distribution mechanisms must be considered if operating costs are to be minimised. The problem is thus one of scheduling London's entire water supply.

Before work could begin on developing scheduling algorithms, a model had to be developed of the distribution network. This had to have enough detail for the results of the scheduling to be useful but not so much that the problem was intractable. All the main pumps and valves had to be represented, along with the treatment works and reservoirs, but the pipe network could be simplified dramatically. Demand was shown at demand nodes, which could represent quite large trees of local distribution pipes.

The process of developing this model of the distribution network was long and required many iterations. A critical aspect of the entire scheduling process is that pressures in pipes must be maintained between limits. Tower blocks at the tops of hills must be supplied but old pipes under the City must not burst. This meant that the model had to be sufficiently faithful for the calculations of pressures to yield valid results.

Finally, as one of the main aims of scheduling the Ring main is to minimise costs, the capabilities of the pumps had to be modelled. The higher the lift (i.e. increase in pressure) a pump is required to deliver, the lower the flow rate. Pumps are designed to work at some combination of lift and flow rate, at which they have their greatest efficiency, as shown in Figure 1.

Figure 1: Performance of Typical Pump

Approaches to Scheduling

There were two basic approaches which could be taken to tackling the problem:

  • simulation, to calculate the hydraulics, but the resulting schedule might not be the cheapest;
  • optimization, but accuracy would be lost in linearising the hydraulic constraints and the schedule might not be feasible.

It was decided to combine the two approaches in a multi-stage scheduling system, as shown in Figure 2.

Figure 2: Stages of Trunk Scheduling

Planning Daily Flows

The first module, NETPLAN, is concerned with setting target flows for use in the more detailed scheduling of the next day's activities. It slices the day into seven time periods (e.g. night, morning peak, mid-morning) and solves a transportation problem. The decision variables are how much water to take from each source in each time period and how much to transport to each destination. Water may be held in service reservoirs to take advantage of lower electricity costs overnight and lower-cost sources. The result is a consistent plan of supply, demand and reservoir levels at the end of each time period. However, although this plan is consistent, it may not be feasible once the hydraulic constraints are considered.

Calculating the Hydraulics

The next stage is to calculate the pressures and flow rates in the network. NETPLAN has proposed the flows which are required in each time period. But we cannot solve the hydraulic equations using these flow rates: we need a schedule of pumping operations which yield the required flows.

This "chicken and egg" problem is tackled as follows. The schedule period is split into regimes in which some set of pumps is working and some set of reservoirs is filling; the other pumps are off and the other reservoirs are emptying. With some mild simplifications it is now possible to solve the hydraulic equations and work out pressures and flow rates for steady state operations under this regime. The cost of operating the pumps is also calculated.

Each regime results in some net movement of water from sources to destinations. Given a set of regimes each of which is hydraulically feasible, it is then possible to combine them with the aim of meeting the NETPLAN targets.   In principle this is a straightforward blending problem: mix the regimes to achieve the targets while minimising costs. In practice it is more complex because regimes should be scheduled so as to minimise the number of pump switches. An LP blending module, NETBLEND, is used followed by a Travelling Salesman Problem algorithm, NETSEQ, to sequence the regimes.

Identifying Regimes

There remains the problem of identifying which regimes to use, i.e. for which set of working pumps and filling reservoirs the hydraulic equations should be solved. There are roughly 100 degrees of freedom here and so 2100 possible regimes. The following approach has been adopted:

  1. consider the regimes which were used yesterday;
  2. blend these together; if they are acceptable, stop;
  3. otherwise identify some new regimes based on the marginal costs from NETBLEND;
  4. solve the hydraulics for the new regimes, trimming pump settings as necessary to satisfy pressure constraints;
  5. add the new regimes and go to step 2

Once a complete schedule has been built, it is then simulated in detail by NETSIM to check that the entire schedule is feasible (there is a possibility that reservoirs may go outside their limits during a NETPLAN time period). If there are problems, parts of the scheduling process are iterated.

Practical Experience

The trunk scheduling system has yielded savings of a few per cent on pumping costs against a good controller. It has also been used extensively in training staff. In many ways, however, its greatest benefits have been in promoting better understanding of how the network works. It has also proved invaluable in dealing with the unexpected, such as when a contractor severed a power cable at a main treatment works, putting all the pumps out of action.

Related articles include Prize-Winning Planning at Harris Semiconductors and How to Minimize Capital Gains Tax. To find other articles, refer to the MP in Action page.