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.
| Subject : | : | Abstracts |
| Topics | : | Rich VRP |
| PDF version | : |  PDF version |
