In modern society, sustainable transportation practices in smart cities are becoming increasingly important for both companies and citizens. These practices constitute a global trend, which affects multiple sectors resulting in relevant socio-economic and environmental challenges. Moreover, uncertainty plays a crucial role in transport activities; for instance, travel time may be affected by road work, the weather, or accidents, among others. This paper addresses a rich extension of the capacitated vehicle routing problem, which considers sustainability indicators (i.e., economic, environmental and social impacts) and stochastic traveling times. A simheuristic approach integrating Monte Carlo simulation into a multi-start metaheuristic is proposed to solve it. A computational experiment is carried out to validate our approach, and analyze the trade-off between sustainability dimensions and the effect of stochasticity on the solutions.