A general and scalable fleet design approach for rich vehicle routing problems
Francesco Bertoli  1, 2@  , Philip Kilby  1, 2@  , Tommaso Urli  1, 2, *@  
1 : National ICT Australia  (NICTA)  -  Website
Australian Technology Park ; Level 5, 13 Garden Street ; Eveleigh NSW 2015 // Tower A ; 7 London Circuit ; Canberra City ACT 2601 // Lvl 2 / Bldg 193 (Dept. of Electrical and Electronic Engineering) ; The University of Melbourne VIC 3010 // Level 4, 223 Anzac Parade ; Kensington NSW 2052 // Level 5, Axon Building (47) ; Staff House Road ; St Lucia Qld 4072 // Innovation House ; First Avenue ; Mawson Lakes SA 5095 -  Australia
2 : Australian National University  (ANU)  -  Website
The Australian National University Canberra ACT 0200 Australia -  Australia
* : Corresponding author

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.


Online user: 1