Summary of the impact

Efficient city-wide water distribution systems (WDS) are vital to the health and financial wellbeing of the cities' inhabitants. The impact of research on evolutionary algorithms and heuristics at Exeter has been to provide efficient water distribution system designs on a city-wide basis for a large city, the City of Ottawa. As part of a programme of building and upgrading infrastructure costing in excess of $225M CAD, the City has implemented large-scale capital projects based on designs produced by genetic algorithm technology, made possible by utilising the heuristics and modular optimisation developed by Keedwell and colleagues at the University of Exeter.

Underpinning research

Research relating to the case study has been undertaken by Keedwell and colleagues in the Centre of Water Systems (CWS) since 2001, primarily under two EPSRC grants, GR/R14712/01 and GR/R73393/01. This research has focussed on the development of novel optimisation algorithms and variants of evolutionary algorithms (EAs) to solve problems in the water industry. The work has concentrated on developing and improving algorithms for optimising networks with 100s or 1000s of variables with the concomitant combinatorial explosion in the search space. It has predominantly focussed on problems in real-world water distribution where modernisation has increased the sophistication of network models, thereby increasing both the number of variables to be optimised and the computational complexity of the objective function. This provides a significant and escalating challenge to the optimising algorithm, and it is this that has motivated Keedwell's research.

Working with Khu (Exeter 2000-2009) at CWS in 2004 Keedwell [1] developed a memetic algorithm using local search in the multi-objective optimisation of water distribution systems which demonstrated that local search incorporating dominance could produce trade-offs between the objectives that were closer to optimal than traditional evolutionary 03c0algorithms. This approach reduced the number of objective function calculations significantly, a property that was to become important in the delivery of solutions for the Ottawa Water Distribution Master Plan.

Subsequently, Keedwell and Khu [2][3][4] provided a breakthrough in water distribution system optimisation research in 2005-6 with the introduction of a cellular-automaton (CA) inspired approach [4]. The technique combined the computational tractability of a cellular automaton and its inherent properties of localism, parallelism and heterogeneity with the task of designing water distribution networks from an engineer's perspective. The CA-inspired heuristic moved the field away from incrementally increasing solution optimality for a set of fixed test problems to embrace the potential of an algorithm that could be applied to large networks, regardless of computational complexity, and to return results in reasonable time. The CA technique was shown to optimise large-scale networks from UK water companies in a fraction of the number of evaluations (5-50) required by EAs (typically 20,000+). This demonstrated the benefits of modifying multiple variables simultaneously, an approach that was key to the efficient optimisation of the Ottawa water distribution system where custom decision variables were used, each affecting many parameters of the water distribution system in a particular locality. Recognising that there was the potential to combine the low-resolution CA search and fine tuning of a GA, Keedwell further developed a number of hybrid CA-GA algorithms [3][4] that provide well-optimised solutions in much reduced computational time in comparison with a standard evolutionary algorithm.

Keedwell's work on incorporating engineering expertise into the optimisation process and the use of cellular automata in water engineering continues to be an area of active research. Topics of current focus are the use of interactive evolution and grammar-based techniques to incorporate further engineering expertise in the optimisation process [6] and cellular automata to model flooding in urban areas [7], the topic of an EPSRC award (EP/H015736/1).

References to the research

Key peer-reviewed publications

References [2][3][4] best indicate the quality of the research.

Details of the impact

The impact of climate change, population migration towards cities and increasing regulation will put increasing strain on the world's water distribution systems in the coming years. They will need to be capable of delivering an increasingly scarce resource to a greater number of people whilst minimising the financial and environmental costs of the provision of clean water. By providing optimised water distribution system designs, the research undertaken by Keedwell, in conjunction with industrial partners Mouchel Ltd, Delcan Corporation and the City of Ottawa, has made a significant and lasting impact on the water distribution system and therefore the people of Ottawa as indicated by the Program Manager for Infrastructure Policy at the City: "The use of EA had a direct influence on the Master Plan that was finalized in 2009, and the direction established at that time has been maintained in the current Master Plan update" [D] and the Project Manager at Delcan Corporation: "The current Master Plan is derived from our [genetic algorithm based] solution, and there are many projects that will be implemented based on the plan." [E]

The Ottawa Water Distribution Master Planning project is intended to deliver the necessary capital infrastructure upgrades to accommodate the projected population increases in the Ottawa area for planning horizons ranging from 2011 to 2031; see [C] for the full scope of the project. To facilitate EA optimisation of the master plan, a large software model was created, incorporating a hydraulic model developed by the team, that calculated the objectives, capital and operational costs and engineering quality scores for each WDS configuration proposed. Configurations were described by the EA decision variables, which were pipe and tank diameters, pump and valve settings. A significant innovation in this area was the specification of `custom decision variables' that combined several network settings into one EA variable [A][B], which allowed the engineers to specify local combinations of settings that correspond to known feasible configurations, reducing decision variable complexity. The resulting software was therefore capable of integrating detailed engineering knowledge into the optimisation, leading the Program Manager to comment: "Application of EA technology to the preparation of the 2009 Master Plan permitted the efficient evaluation of a very large number of combinations and permutations of infrastructure and system configuration alternatives that were identified at the time."[D]

Inspired by the work in [1], a local search heuristic was developed to locally optimise the EA solutions and correct sub-optimal decision variable settings individually, rather than as part of a much more computationally complex combinatorial problem. This heuristic was often able to create simultaneously lower-cost and better-performing solutions even after long optimisation runs. As an example, after one EA run of 174,000 iterations, the heuristic was able to improve on the highly optimised solution by $77,000CAD with a simultaneous increase in engineering performance.

The optimisation process has been used to support master planning decisions for the City of Ottawa estimated to cost almost $225M CAD (approx. £135m at current exchange rates), and is part of a wider master planning project including wastewater and other infrastructure upgrades. This capital investment will provide the residents of Ottawa with a system designed to optimise water quality, quantity, reliability and affordability. The evolutionary algorithm and the additional innovations incorporated from the research at Exeter have contributed to the level of service for customers and affordability (by minimising future capital and operating costs) of the final master planned solution as described by the City themselves: "The results of the EA study ultimately guided the development of a cost-effective plan which will improve the level of service to a large and rapidly developing community in the City's South Urban Area." [D]. It is not possible to derive an exact figure for the savings yielded by the EA-based solution as the study relates to the expansion of existing infrastructure for which there is no comparable human-derived solution. What is certain though, is that with projects of this magnitude, even small efficiencies in the EA and EA-heuristic design will significantly impact the wellbeing of the residents of this large city far into the future, to 2031 and beyond. In addition, this project has had wider impact on the practice of infrastructure planning at the City of Ottawa, as described in the corroborating letter: "The experience that the City of Ottawa gained with this project has encouraged staff to consider similar approaches to infrastructure planning and design, as well as other activities that can benefit from EA technology, such as the calibration of complex system models". [D]

Sources to corroborate the impact

Reports were published by the consulting engineers involved in two academic-industrial conferences as follows:

A. Randall-Smith, M, Rogers C, Keedwell E, Diduch R, Kapelan Z, (2006) Optimized Design of the City of Ottawa Water Network: a Genetic Algorithm Case Study 8th Annual Water Distribution Systems Analysis Symposium, pp 1-20. American Association of Civil Engineers. doi: 10.1061/40941(247)87

B. Rogers C, Randall-Smith M, Keedwell E, Diduch R. (2009) Application of Optimization Technology to Water Distribution System Master Planning, World Environmental and Water Resources Congress, Kansas City, Missouri, 17th - 21st May 2009, pp 1-10. American Association of Civil Engineers. doi: 10.1061/41036(342)36

C. The final Master Plan to which the research contributed can be found here http://ottawa.ca/en/city-hall/planning-and-development/official-and-master-plans/infrastructure-master-plan

D. Corroborating letter from the Program Manager, Infrastructure Planning, Planning and Growth Department at the City of Ottawa, dated 30^th September 2013.

E. Corroborating e-mail from Project Manager at Delcan Corporation, dated 17^th May 2010.