Sustainability is a monumental issue that should be considered in designing a logistics system. In order to incorporate sustainability concepts in our study, a waste collection problem with economic, environmental, and social objective functions was addressed. The first objective function minimized overall costs of the system, including establishment of depots and treatment facilities. Addressing environmental concerns, greenhouse gases emission was minimized by the second objective function and the third one maximized distances between each customer and treatment facilities. Treatment facility is noxious for human health and should be located in the maximum distance from the urban area. Initially, the locations of depots and treatment facilities were determined. Then, heterogeneous vehicles started to collect waste from the location of each customer and take it to treatment facilities. The problem included two types of open and close routes. Moreover, each vehicle had a capacity restriction, servicing time, and route length. There were different types of waste and each vehicle had a different capacity for them. Three metaheuristic algorithms combined with clustering approach were proposed to look for the best solutions in rational time. The Non-dominated Sorting Genetic Algorithm-II (NSGA-II), improved Strength Pareto Evolutionary Algorithm (SPEA-II), and Multi-Objective Evolutionary Algorithm based on Decomposition (MOEA/D) were compared in terms of performance metrics. According to the results, NSGA-II outweighed other algorithms in the presented model.