Robust Optimization Applied to the Vehicle Routing Problem with Time Windows and Multiple Deliverymen

The Vehicle Routing Problem with Time Windows and Multiple Deliverymen (VRPTWMD) is a variant of the traditional Vehicle Routing Problem with Time Windows (VRPTW), in which, in addition to the classical constraints, the possibility of multiple deliverymen traveling with the vehicle is considered, allowing the reduction of service time at customers. Customers are grouped into clusters, so that vehicles travel primary routes (between clusters) and deliverymen travel secondary routes (within clusters) to serve them. Variants involving routing with two decision levels (vehicle routes and deliveryman routes) and the division of customers into clusters are scarcely explored in the literature. The two-echelon approach (VRPTWMD2R) considers travel times and service times on the secondary routes (deliveryman routes), with service times in particular showing significant variability, requiring this parameter to be treated as uncertain. In this context, this work proposes a robust optimization (RO) model for VRPTWMD2R, considering uncertainties in service times, based on models for the deterministic variant of the problem and mathematical modeling techniques in RO, such as the linearization of recursive equations used in this case. The proposed model is validated through computational experiments using benchmark instances from the literature that prove equivalence when considering the deterministic case. Monte Carlo simulation results demonstrate the benefits of incorporating uncertainty into VRPTWMD2R, showing a reduction in risk when adopting greater conservatism, while solution costs increase, illustrating the trade-off that must be considered for decision-making.