Growing urbanisation causes pressures on many environmental assets such as groundwater systems, waterways, atmosphere, ecosystems and others. To manage and mitigate the negative effects of these pressures, environmental programs are typically launched, which comprise of eligible projects in different affected locations. The implementation of individual projects has a cost. However, due to budget constraints, most frequently not all suggested projects can be implemented which makes necessary to choose a subset. In this paper, we use a cost utility approach and a subsequent combinatorial optimisation based on metaheuristics to determine a project portfolio which returns a maximum aggregated utility while keeping the budget constraint. To ensure that the mutual exclusiveness of projects at one particular site is guaranteed, we further developed the employed metaheuristics. We apply this approach within a waterway health program in a river catchment in Brisbane, Australia, and compare its results to a commonly used selection process that does not involve combinatorial optimisation. We find that the use of combinatorial optimisation leads to a considerable improvement of the selection process and can help to more effectively allocate environmental expenditure. [ABSTRACT FROM AUTHOR]