Vehicle routing in a Spanish distribution company: Saving using a savings-based heuristic

In this article 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 VRP, 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 per cent in transportation costs, which represent around €30 000 saved per week.