In the last few years, the application of decision making to logistic problems has become crucial for public and private organizations. Efficient decisions clearly contribute to improve operational aspects such as cost reduction or service improvement. The particular case of waste collection service considered in this paper involves a set of economic, labor and environmental issues that translate into difficult operational problems. They pose a challenge to nowadays optimization technologies since they have multiple constraints and multiple objectives that may be in conflict. We therefore need to resort to multiobjective approaches to model and solve this problem, providing efficient solutions in short computational times. In particular, we consider four different objectives to model the waste collection problem: travel cost, route length balance, route time balance, and number of routes. We propose an iterated greedy algorithm coupled with a variable neighborhood search to minimize an achievement function to determine a good approximation to the Pareto front. The performance of our method is empirically analyzed on a set of instances (both generated and real), and compared with the well-known NSGA-II and SPEA2 methods. The comparison favors our proposal.