Given the continuous aging of pipeline infrastructure buried underground, water utilities need to make a strategic plan on how to maintain the entire water distribution systems (WDSs) to ensure the required standard of supply. This paper investigates the nexus of three key factors that have a significant impact on the decision-making process of the rehabilitation plan for WDSs. The factors considered include the problem formulations, the pipe selection methods for identifying critical components of WDSs, and the multi-objective evolutionary algorithms (MOEAs). The nexus was revealed by considering all the combinations of two variants for each factor. The optimal rehabilitation problem of the Exeter network was used as a case study. Results exhibit that the problem formulation determined the range of Pareto fronts essentially, which should give the highest priority in the decision-making process. The pipe selection method played a secondary role, mainly affecting the shape of Pareto fronts. Optimization algorithms also had a considerable impact on the optimality of solutions, subject to their characteristics and parameter settings. This paper also highlights that breakthroughs need to focus on these key factors to facilitate a more cost-effective solution to the rehabilitation of large WDSs.