Is waiting worth it? the value of delaying time window assignment in vehicle routing problems

We explore the critical balance between immediate and delayed communication of time windows to customers in next-day business services, e.g., repairs, high-value deliveries, or installments. Faster communication benefits customers but potentially harms routing quality, including on-time delivery and transport costs. This paper addresses the Dynamic Delayed Time Window Assignment Vehicle Routing Problem (DDTWAVRP), a complex decision-making challenge service providers face. We model the DDTWAVRP as a semi-Markov Decision Process (MDP) with a finite time horizon. We propose two online algorithms as a solution methodology to evaluate the value of delay, namely, the rollout and the multiple scenario approach policy. Rollout policy simulates and approximates the value function to create robust solutions, whereas the multiple scenario approach policy searches for the most popular solution amongst sampled scenarios. We compare the performance of the proposed methodologies with other benchmark policies from the literature. Our numerical study shows an 11.82 % decrease in routing durations if we allow delaying a time window assignment. Compared to only assigning time windows once all demand is known, routing costs only increase marginally. We show that the decision to delay a time window assignment depends on the current state and must be tailored to customers.