Vehicle routing with time windows, multiple deliverymen, and two decision levels under uncertainty: robust optimization approaches

This work addresses a robust variant of the Vehicle Routing Problem with Time Window and Multiple Couriers with two levels of decision, involving synchronization between primary vehicles and local courier routes. Second-tier operation uncertainties, affecting demand, travel times and service times, are considered to be modeled by budgeted uncertainty sets. Two exact approaches are evaluated: a compact formulation based on the linearization of robust recursive equations, and a Benders decomposition, in which the robust subproblem is treated by reformulation. The article presents the base deterministic model, the uncertainty sets, the robust recursions, their linearizations and the structure of the proposed algorithm. Computational results in small instances indicate better aggregate performance of the compact formulation, although Benders decomposition becomes more competitive in R-class instances and under temporal uncertainty.