In this paper we introduce the discrete time window assignment vehicle routing problem. This problem consists of assigning a single time window from a set of candidate time windows to each customer before demand is known, and when demand becomes known constructing vehicle routes that satisfy the assigned time windows. The objective is to minimize the expected total transportation costs. We develop a state-of-the-art branch-price-and-cut algorithm to solve this problem to optimality. We present results of computational experiments performed with this algorithm. Finally we illustrate the benefits of using an exact method to solve this problem with respect to a heuristic that is frequently used in practice.
Published December 2012 , 21 pages