Stochastic Fleet Size and Mix Consistent Vehicle Routing Problem for Last Mile Delivery
arXiv:2512.09764
The paper proposes a two‑stage stochastic mixed‑integer model that simultaneously decides the size and composition of a delivery fleet and the routing plan, adapting routes after actual customer demand is observed, and introduces a path‑based reformulation with a Kernel Search heuristic to solve realistic last‑mile delivery instances.
Abstract
In this paper, we address the joint optimization of fleet size and mix, along with vehicle routing, under uncertain customer demand. We propose a two-stage stochastic mixed-integer programming model, where first-stage decisions concern the composition of the delivery fleet and the design of consistent baseline routes. In the second stage, approximate recourse actions are introduced to adapt the initial routes in response to realized customer demands. The objective is to minimize the total delivery cost, including vehicle acquisition, travel distance, and penalty costs for unserved demand. To tackle the computational challenges arising in realistic problem instances, we develop a path-based reformulation of the model and design a Kernel Search-based heuristic to enhance scalability. Computational experiments on small synthetic instances, generated through a population-density-based sampling approach, are conducted to validate the formulation and assess the effects of demand stochasticity through standard stochastic measures, after applying a scenario reduction technique. Additional tests on large-scale real-world instances, based on data from the Italian postal company, demonstrate the effectiveness of the proposed approach and provide managerial and practical insights.