This work addresses the challenge of establishing delivery schedules for consumers who buy goods online or who buy furniture and appliances in a store. Home delivery companies have several challenges in managing their distribution network efficiently due to the high level of uncertainty of the future demand. The existence of a delivery schedule becomes essential to ensure customer satisfaction and to reduce the delivery costs. Several works have tackled this problem in the literature and most of them try to build a delivery schedule using a restricted set of time windows to increase the consolidation and reduce delivery costs. In this talk, we evaluate the current alternatives and propose new ones to increase the offering of time windows. Our evaluation scheme is a two-step procedure based on stochastic programming. The first step generates a set of delivery schedules 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. Both stages are solved using dedicated metaheuristics. The final delivery schedules are evaluated by a Monte-Carlo procedure that simulates the arrival of customers and the selection of a time window. The different alternatives are compared in terms of transportation cost, number of served customers and number of offered time windows.