Multi-period time window assignment for attended home delivery

We study a multi-period stochastic variant of the Time Window Assignment Vehicle Routing Problem, where customers’ demands, locations, and service times are uncertain. Customers are partitioned into geographical zones, each of which has to be visited a predetermined number of times over a planning period of several days. Whenever a zone is visited, a time window is assigned. Time windows are decided before knowing customers and their demands. A fleet of homogeneous vehicles is available to serve customers each day. At a tactical level, the problem looks for a static time window assignment that minimizes the expected traveling costs plus the expected penalty costs for unserved customers. We propose a two-stage formulation and a solution approach, which relies on the Sample Average Approximation Method, while encompassing a perturbation method to assign time windows in the first stage and an Adaptive Large Neighborhood Search to optimize routes in the second stage. We experimentally evaluate three instance sets, including real ones from a Canadian company, comparing our results to lower bounds from the exact solution of a deterministic equivalent formulation over a finite number of scenarios. Our method outperforms the manual approach used by the company.