The transportation of recyclable waste collection is significant for reducing the effect of greenhouse gases. In this study, we investigate a multi-depot green vehicle routing problem in which one group of vehicles starts their routes from different points – excluding depots – and the other group of vehicles starts from one of the multiple depots and additional the serving areas of vehicles are predetermined. Although the groups of vehicles serve different areas, the problem is merged together since the depots have capacity. Furthermore, the objective of the problem is to minimize carbon emissions related to traveling distance and vehicle load on the route. We modeled this as a mixed integer programming problem and we developed variable neighborhood search algorithms with two different strategies. The performance of both approaches was evaluated using test instances which have been modified from published literature.