Pareto archived dynamically dimensioned search (PA-DDS) has been modified to solve combinatorial multi-objective optimization problems. This new PA-DDS algorithm uses discrete-DDS as a search engine and archives all non-dominated solutions during the search. PA-DDS is also hybridized by a general discrete local search strategy to improve its performance near the end of the search. PA-DDS inherits the simplicity and parsimonious characteristics of DDS, so it has only one algorithm parameter and adjusts the search strategy to the user-defined computational budget. Hybrid PA-DDS was applied to five benchmark water distribution network design problems and its performance was assessed in comparison with NSGAII and SPEA2. This comparison was based on a revised hypervolume metric introduced in this study. The revised metric measures the algorithm performance relative to the observed performance variation across all algorithms in the comparison. The revised metric is improved in terms of detecting clear differences between approximations of the Pareto optimal front. Despite its simplicity, Hybrid PA-DDS shows high potential for approximating the Pareto optimal front, especially with limited computational budget. Independent of the PA-DDS results, the new local search strategy is also shown to substantially improve the final NSGAII and SPEA2 Pareto fronts with minimal additional computational expense.