In the last few years, the application of decision making to logistic problems has become crucial for public organizations. In particular, waste management involves a set of economic, social, labor and environmental aspects, which implies a big effort from these companies that must provide a good service. In general, any real waste management scenario contemplates multiple criteria, to find, according to the decision maker's requirements, the most suitable solution. The dimension and complexity of real Waste Collection Problems (WCPs) recommends the use of metaheuristic strategies to find high quality solutions in short computational time. As it is customary in multiobjective optimization, we do not have a unique optimal solution, but we are seeking for a good approximation of the set of efficient solutions. In this paper, we formulate the WCP as a Capacitated Vehicle Routing Problem, with the following objectives: minimize the overall travel cost, balance the driven routes (in terms of distance and time), and minimize the number of routes.

We propose a solution method based on the hybridization between Iterated Greedy and Variable Neighborhood Search. Additionally, it uses the Wierzbicki achievement scalarizing function to perform an efficient search of the multi-objective solution space. We explore different designs of our method and compare it with the well-known NSGA-II solver on a large set of public domain instances.