Fleet size and mix split-delivery vehicle routing: a study of MIP formulations
Arthur Maheo  1, 2@  , Tommaso Urli  1, 2, *@  , Philip Kilby  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 benchmark various Mixed Integer Programming (MIP) models for a real-world daily delivery problem arising in Queensland, Australia. Our client is faced with the task of satisfying the demand of ambient and refrigerated goods to be delivered at often remote grocery stores. This study has been carried out in the context of a tender for the delivery of goods called by a large grocery stores chain. Since winning the tender would require restructuring the available fleet, our client is also interested in streamlining the design of an efficient fleet, able to carry out the deliveries over the long term.

From a classification standpoint, this represents a ``rich'' Vehicle Routing Problem (RVRP). In this particular variant, the vehicles have different operation costs and capacities, but only some of them are refrigerated. Moreover, some of the demands are larger than a truckload, therefore requiring split deliveries. Finally, because we are also interested in designing an efficient fleet to support the demand, we allow the solver to choose the most suitable set of vehicles.

This problem has been addressed in [Kilby and Urli, 2015] using a Constraint Programming (CP) approach. The results are compared to an admittedly simple MIP model, but suggest that a MIP-based decomposition scheme could obtain better scalability results.

This work is a preparatory step aimed at identifying the best among various different MIP models for the daily problem. The best performing model will then be used within a decomposition scheme to address the complete multi-day variant.


Online user: 1