The optimisation of water distribution networks (WDNs) by evolutionary algorithms has gained much coverage in the literature since it was first proposed in the early 1990s. Despite being well studied, the problem and objectives continue to evolve as demands on water companies change. Motivated by the increased focus on reducing the risk of discolouration, this study examines a three objective version of the WDN design problem which takes into account cost, head excess and discolouration risk. Using this formulation, this paper presents a method for producing optimised network designs aimed at reducing discolouration risk in the network design phase and thus reducing the associated long-term maintenance and operational burdens of the system. This paper discusses the use of a discolouration risk model and, using this model, the optimisation of network design, specifically pipe diameters, to produce a range of high quality self-cleaning networks. The network designs are optimised using the Markov-chain hyper-heuristic (MCHH), a new multi-objective online selective hyper-heuristic. The MCHH is incorporated in to the known NSGA-II and SPEA2 and supplied with a range of heuristics tailored for use on the WDN design problem. The results demonstrate an improvement in performance obtained over the original algorithms.