The water distribution system (WDS) rehabilitation problem is defined here as a multi-objective optimisation problem under uncertainty. Two alternative problem formulations are considered. The first objective in both approaches is to minimise the total rehabilitation cost. The second objective is to either maximise the overall WDS robustness or to minimise the total WDS risk. The WDS robustness is defined as the probability of simultaneously satisfying minimum pressure head constraints at all nodes in the network. Total risk is defined as the sum of nodal risks, where nodal risk is defined as the product of the probability of pressure failure at that node and consequence of such failure. Decision variables are the alternative rehabilitation options for each pipe in the network. The only source of uncertainty is the future water consumption. Uncertain demands are modelled using any probability density functions (PDFs) assigned in the problem formulation phase. The corresponding PDFs of the analysed nodal heads are calculated using the Latin Hypercube sampling technique. The optimal rehabilitation problem is solved using the newly developed rNSGAII method which is a modification of the well-known NSGAII optimisation algorithm. In rNSGAII a small number of demand samples are used for each fitness evaluation leading to significant computational savings when compared to the full sampling approach. The two alternative approaches are tested, verified and their performance compared on the New York tunnels case study. The results obtained demonstrate that both new methodologies are capable of identifying the robust (near) Pareto optimal fronts while making significant computational savings.