In this work, a method based on the variable neighborhood search metaheuristic (VNS) is proposed to solve the integrated routing-packaging problem.The method considers three-dimensional packing constraints, heterogeneous fleet and environmental impact.Using the Split coding proposed by Prins ( 2004), the routes satisfying the Capacitated Vehicle Routing Problem's capacity constraints are selected.The GRASP algorithm proposed by (Martínez et al., 2015) is used to validate the packing constraints of the Three-Dimensional Single Knapsack Problem associated to the selected routes.Environmental impact is included in the optimization scheme, adding a fuel consumption term in the objective function.Additionally, a similar implementation that does not consider the fuel consumption was developed, in order to measure the impact of having a green vehicle routing approach.Computational results show that a mixed integer programming (MIP) solver is capable of obtaining optimal solutions for each of the aforementioned scenarios in reasonable computing times.