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.