In this paper we present a Vehicle Routing Problem (VRP) faced by a large distribution company in the Northeast of Spain. The company distributes products from its central facilities to a chain of around 400 stores all over the country. One of the peculiarities of the VRP of this company –which is common among real-life VRPs– is the presence of a heterogeneous fleet where vehicles with different capacities can make multiple trips during a single day. This variant of the problem, which we refer as Heterogeneous Fleet and Multi-trip Vehicle Routing Problem, has been barely studied in the literature. To solve the problem, we use an algorithm based on the well-known savings heuristic with a biased-randomization effect and three local search operations. Our approach is simple to implement as it needs few parameters and no fine-tuning processes, which are usually cumbersome and require experts’ involvement. We obtain savings of around 12% in transportation costs, which represent around €30,000 saved per week.