Transport activities have relevant negative impacts on the social, economic and environmental context, which are reflected by some indicators such as accident rate, gross domestic product or emissions of greenhouses gasses. The growing concern about developing more efficient towns has led to a trend towards sustainability issues and smart cities, in which a number of technologies provide enough information to create smart sustainable cities. Thus, the traditional design of routes needs to be changed to incorporate sustainability criteria into the decision-making. For instance, the information systems reveal the state of roads in real-time, which may help to reduce congestion, waiting times and unnecessary stops that increase the negative impacts. A large part of the academic advances related to vehicle routing problems is focused on the environmental impacts ignoring negative direct effects on the population welfare. In contrast, this work presents a powerful algorithm based on the VNS metaheuristic that integrates the sustainability dimensions as decision criteria to provide smart solutions to a rich vehicle routing problem with multi-depots. The algorithm has been tested in realistic instances and compared against a state-of-the-art algorithm. Our experimental results show how the social, environmental and economic impacts vary according to the decision criterion.