The Discrete Time Window Assignment Vehicle Routing Problem

Registration to Remy Spliet, spliet@ese.eur.nl is required for availability of lunch.

We consider a vehicle routing setting in which customer demand is stochastic. This stochasticity of demand is modelled using several scenarios. Time windows have to be assigned to customers in a planning stage, during which demand is not yet known. Time windows are selected from a discrete number of candidates for each customer. After demand is learned, a vehicle routing schedule is constructed by solving a vehicle routing problem with time window constraints, using the assigned time windows. The Discrete Time Window Assignment Vehicle Routing Problem, DTWAVRP, is the problem to assign time windows such that the expected costs of the vehicle routes are minimized.

This problem is frequently encountered in practice in retail networks. It is very common to fix time windows for a long period of time without knowing demand. Operations at the customer side are often highly dependent on the specific time window assigned to them, consider for instance hiring delivery handling personnel. Prior to dispatching demand is learned, a customer might for instance place an order the evening before deliveries are made. This gives some time to design an efficient vehicle routing schedule. Typically demand has a large impact on which routing schedules are feasible and which are not. And time windows should be chosen in the planning phase that are robust for these fluctuations in demand.

We solve the DTWAVRP to optimality using a branch-and-cut-and-price algorithm. We use a set partitioning type of formulation for the DTWAVRP. We find lower bounds by solving the LP relaxation of the DTWAVRP using our formulation, by means of column generation. The pricing problem is an elementary shortest path problem with time window and capacity constraints. We try to speed up our algorithm by applying ng-path relaxation as well as by implementing several heuristics to solve the pricing problem. We strengthen the lower bound by generating valid inequalities such as the subset row inequalities.