Multi-objective optimization methods require many thousands of objective function evaluations. For urban water resource problems such evaluations can be computationally very expensive. The question as to which optimization method is the best choice for a given function evaluations budget in urban water resource problems remains unexplored. The main objective of this paper is to address this question. The second objective is to develop a new optimization algorithm, efficient multi-objective ant colony optimization-I (EMOACO-I), which exploits the good performance of ant colony optimization enhanced using ideas borrowed from evolutionary optimization. Its performance was compared against three established methods (NSGA-II, SMPSO, εMOEA) using two case studies based on the urban water resource systems serving two major Australian cities. The case study problems involved two or three objectives and 10 or 13 decision variables affecting infrastructure investment and system operation. The results show that NSGA-II was the worst performing method. However, none of the remaining methods was unambiguously superior. For example, while EMOACO-I converged more rapidly, its diversity was comparable but not superior to the other methods. Greater differences in performance were found as the number of objectives and case study complexity increased. This suggests that pooling the results from a number of methods could help guard against the vagaries in performance of individual methods.