Abstract Models for routing vehicles have been applied to solve a variety of transport route design problems. Also, it has taken an important trend on environmental care in consideration of the negative environmental impact generated by the emissions resulting from transportation. Another relevant aspect of environment care is the collection of solid wastes due to the high quantities generated by human activities. In this paper, we developed a bi-objective model for routing vehicles for solid waste collection that considers the minimization of costs associated with both vehicles and CO 2 emissions. The model considers heterogeneous fleet, capacity, hard time windows, and speed variation in an urban center. A case study in the Caribbean region of Colombia is studied, with a total of 50 nodes in the network. Because of the computational hardness, nodes are clustered in five sets of 10 nodes to obtain optimal solutions. The sum of costs showed a reduction of 9.447% compared to current costs (50 nodes without clustering). Subsequently, we reviewed and restructured some constraints that allowed to soften the complexity of the model and obtain improved solutions with reduced current costs by 16.55%.