In this paper we consider the problem of designing a feasible and efficient fleet to carry out the daily activities of a freight company over an extensive planning horizon, e.g., one year. Such activities require to operate the fleet so as to satisfy the demand of a set of customers subject to a variety of real-world constraints, e.g., capacities, time windows, driving regulations, etc., and are commonly modelled as ``rich'' Vehicle Routing Problems (RVRP).

One approach to solve the long-term fleet design problem consists in aggregating the single-day problems into a multi-day problem, and solving it using a fleet size and mix (FSMVRP) formulation. In a FSMVRP, the solver is allowed to choose which (and how many) vehicles to use, as long as the overall fleet is consistent throughout the horizon. The problem with this approach is that, when the length of the horizon grows, scalability issues arise, and obtaining good-quality solutions becomes hard.

Here, we propose an iterative two-stage method based on a novel MIP formulation. In our approach, every single-day problem is solved individually, and the solutions are used to generate a new fleet that is guaranteed to be feasible in the multi-day context. Our approach is independent of the underlying RVRP problem, provided that a suitable solver is available, and has shown encouraging scalability properties.

As a case study, we consider a split-delivery multi-compartment vehicle routing problem arising in a real-world fuel delivery context, and we produce an efficient fleet based on 300 days of demand data.