This work addresses the challenge of establishing delivery schedules to consumers who buy goods online or buy furniture and appliances. The difficulties faced by home delivery companies are due to the high level of uncertainty of the future demand. Several works done in the past that tackled this problem assumed to some point that future demand is known or only considered daily schedules. As information systems have more and more historical data, it is possible to build scenarios of the future demand, and we propose a stochastic programming approach to offer more robust delivery schedules that span over several days.

In this talk, we present a heuristic to solve the stochastic multi-period time windows assignment problem. We consider a home delivery company that wishes to plan the delivery schedules for a time horizon across its delivery areas. The solution approach is based on the concept of a priori optimization. That is, time windows are assigned to the delivery areas in the first stage without taking into account the future demand. Then, in the second stage, future customers are known and routes satisfying the first stage time windows are planned. The objective is to minimize the expected cost of the second stage. The resolution approach of the first stage consists of a Variable Neighborhood Search that tries to move the time windows to different periods in order to improve the current solution. The second stage is solved with the Adaptive Large Neighborhood Search. Computational experiments demonstrate the value of this approach.