The time window assignment vehicle routing problem with product dependent deliveries

This paper presents a new formulation for a time window assignment vehicle routing problem where time windows are defined for multiple product segments. This two-stage stochastic optimization problem is solved by means of a fix-and-optimize based matheuristic. The first stage assigns product dependent time windows while the second stage defines delivery schedules. Our approach outperforms a general-purpose solver and achieves an average cost decrease of 5.3% over expected value problem approaches. Furthermore, a sensitivity analysis on three operational models shows that it is possible to obtain significant savings compared to the solutions provided by a large European food retailer.