The Time Window Assignment Vehicle Routing Problem

In many distribution networks, it is vital that time windows in which deliveries are made are assigned to customers for the long term. However, at the moment of assigning time windows demand is not known. In this paper we introduce the time window assignment vehicle routing problem, the TWAVRP. In this problem time windows have to be assigned before demand is known. Next the realization of demand is revealed and an optimal vehicle routing schedule has to be made that satisfies the time window constraints. We assume that different scenarios of demand realizations are known, as well as their probability distribution. The TWAVRP is the problem of assigning time windows such that the expected traveling costs are minimized. We propose a formulation of the TWAVRP and develop two variants of a column generation algorithm to solve the LP relaxation of this formulation. Numerical experiments show that these algorithms provide us with very tight LP-bounds to instances of moderate size in reasonable computation time. We incorporate the column generation algorithm in a branch and price algorithm and find optimal integer solutions to small instances of the TWAVRP. In our numerical experiments, the branch and price algorithm typically finds the optimal solution very early in the branching procedure and spends most time on proving optimality.