A new methodology to optimize regionalized wastewater treatment systems is presented. The approach, developed for the River Ave basin, relies upon a clustering analysis algorithm to identify independent sub-sets of polluting sources within the basin. Then for each cluster, heuristic methods are used to generate a network representing the most promising configurations for the regional system, auxiliary models are applied to estimate detailed costs, and a k-shortest path algorithm is used to specify the configurations minimizing cost while achieving a pre-defined efficiency level. To illustrate the proposed method, an application to a sub-section of the basin with seven textile industry units is included.