This paper’s aim is to develop a model for the household waste collection and transportation problem in the city of Sousse, one of the largest cities in Tunisia. Several vehicles with a finite capacity are located at the depot. The vehicles must collect the waste accumulated in all bins. The waste is then delivered to a transfer center, before vehicles return to the depot. The proposed model determines the routes of the vehicles and the number of bins to be assigned to each potential location, while minimizing the collection costs and the environmental impact. The problem can be considered as a bi-objective optimization problem, as cost minimization will be ensured by the optimal assignment of the determined minimum number of bins. We also consider the stochastic aspect of population size, which is supposed to follow a normal distribution. Our model is then a stochastic bi-objective programming model. A solution is obtained with reasonable computational effort using a hierarchical approach consisting of two stages as “cluster-first route-second”. In the first stage, a set of n locations of bins is assigned into k disjoint clusters using the K-means clustering algorithm. In the second stage, a certainty equivalent program to the bi-objective stochastic program is proposed, based on a chance-constrained, recourse and a goal programming approach. The model is tested and implemented using real data from the municipality of Sousse. The study shows that our model leads to lower environmental impact and an almost 38% reduction in the economic costs. © 2019, Springer-Verlag GmbH Germany, part of Springer Nature.