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. 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 logistic service providers face. We model the DDTWAVRP as a semi-Markov Decision Process (MDP) with a finite time horizon. We propose to use Deep Controlled Learning (DCL). This deep reinforcement learning approach tackles the computational challenges of large state-decision spaces through approximate policy iteration, efficient state sampling, and effective dataset construction to evaluate the value of delay. We compare the performance of the proposed methodology with five other benchmark policies. Our numerical study shows a 7.4% improvement in total cost that includes waiting time of customers and routing cost, and an 11.2% decrease in routing cost 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.