Is waiting worth it? the value of delaying time window assignment in vehicle routing problems
研究了次日配送服务中，延迟向客户告知时间窗对路径规划质量的影响，提出两种在线算法，发现允许灵活延迟可降低11.82%的路径时长，且不损害公平性或服务可靠性。
• We study the balance between immediate and delayed time window communication in next-day delivery. • To assess the value of delay, we propose two online algorithms: one that approximates the value function and another that identifies the most frequent solution among sampled scenarios. • Both algorithms consistently outperform established benchmark policies across multiple performance metrics. • Our results show that allowing customer-specific flexibility in when time windows are communicated yields measurable operational benefits without compromising fairness or service reliability. 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.