Sediment transport in sewer systems is an important issue of interest to engineering practice. Several models have been developed in the past to predict a threshold velocity or shear stress resulting in self-cleansing flow conditions in a sewer pipe. These models, however, could still be improved. This paper develops three new self-cleansing models using the Evolutionary Polynomial Regression-Multi-Objective Genetic Algorithm (EPR-MOGA) methodology applied to new experimental data collected on a 242 mm diameter acrylic pipe. The three new models are validated and compared to the literature models using both new and previously published data sets. The results obtained demonstrate that three new models have improved prediction accuracy when compared to the literature ones. The key feature of the new models is the inclusion of pipe slope as a significant explanatory factor in estimating the threshold self-cleansing velocity.