In this paper we introduce the time window assignment vehicle routing problem (TWAVRP). In this problem, time windows have to be assigned before demand is known. Next, a realization of demand is revealed, and a vehicle routing schedule is made that satisfies the assigned time windows. The objective is to minimize the expected traveling costs. We propose a branch-price-and-cut algorithm to solve the TWAVRP to optimality. We provide results of computational experiments performed using this algorithm. Finally, we offer insight on the value of an exact approach for the TWAVRP by comparing the optimal solution to the solution found by assigning time windows based on solving a vehicle routing problem with time windows with average demand.

Additional Metadata
Keywords Pricing problem with linear node costs, Time window assignment, Vehicle routing problem
Persistent URL dx.doi.org/10.1287/trsc.2013.0510, hdl.handle.net/1765/85967
Journal Transportation Science
Citation
Spliet, R, & Gabor, A.F. (2015). The time window assignment vehicle routing problem. Transportation Science, 49(4), 721–731. doi:10.1287/trsc.2013.0510