From Stochastic Programming to Deep Learning:Advancing Time Window Assignment and Vehicle Routing in Last-Mile Logistics

Modern shopping is built around a simple human impulse: we like to get what we want quickly and without hassle. In today’s retail world, that impulse shows up everywhere: one-click orders, instant confirmations, and packages that appear the same day. E-commerce has not just responded to this impulse; it has learned to harness it. Websites are designed to make buying frictionless, and delivery networks are engineered to turn a click into a knock at the door, sometimes within hours. As this “need for now” has grown, speed has set the pace. What used to be a luxury, next-day delivery, is close to a basic expectation. Same-day delivery is moving in the same direction. Big companies like Amazon and Walmart have invested in local warehouses, dense delivery networks, and sophisticated software. Grocers and specialized carriers add an extra layer: they promise not just a fast day, but a specific time window eg. between 12:00 and 13:00, between 19:00 and 20:00, so customers can plan their lives and still get fresh food or a repair visit when it actually helps them. Speed alone, however, isn’t enough. People also care deeply about reliability, knowing when the doorbell will ring. For many purchases, especially attended home deliveries like groceries or high-value items, predictability matters almost as much as speed. A promise that is precise and kept builds trust; a promise that’s vague or broken erodes it. That is why many providers now offer narrow time windows, live tracking, and proactive updates: confident, believable promises are a competitive advantage. From the outside, time windows look like simple customer service. Behind the scenes, they are a delicate operational puzzle. Real life adds bumps: demand fluctuates, some customers cancel, traffic disruptions appear, and service times vary. Promising too early can paint the operation into a corner; promising too late can frustrate customers. And since orders arrive all day, decisions made now affect what is still possible later. This is the heart of the work studied in this thesis: how to make smart, reliable promises under uncertainty in ways that keep customers happy and keep operations efficient. We explore three closely related settings that you can think of as different time window assignment practices, each reflecting how and when commitments are made. Assigning delivery time windows is far from straightforward. Providers face multiple sources of uncertainty, including fluctuating demand, variable travel times, and dynamic booking patterns. Early commitments can improve customer experience but restrict routing flexibility, while delayed communication allows for more efficient planning but risks frustrating customers. These trade-offs are particularly complex in three contexts: (i) next-day delivery with stochastic travel times, where windows must be promised before full uncertainty is revealed, (ii) dynamic next-day booking systems, where providers must decide when to communicate commitments, and (iii) same-day services, where customers select time slots in real time and the design of the slot menu directly influences both customer choices and operational feasibility. In Chapter 2, we address the fundamental Time Window Assignment Vehicle Routing Problem with Stochastic Travel Times (TWATSP-ST), a long-standing challenge in last-mile logistics. We propose the Two-Step Benders Decomposition with Scenario Clustering (TBDS), the first exact method capable of solving TWATSP-ST instances to optimality. The approach combines a two-step decomposition of binary and continuous first-stage decisions with a scenario-retention strategy that strengthens the master problem’s relaxation. This yields both computational efficiency and improved solution quality, outperforming benchmark methods. Beyond performance, TBDS provides structural insights into optimal solutions, such as the strategic allocation of high-variance travel-time arcs and the role of flexible time window lengths in buffering against uncertainty. Chapter 3 turns to dynamic settings and introduces the Dynamic Delayed Time Window Assignment Vehicle Routing Problem (DDTWVRP). This model captures the value of postponing time window communication until more information is revealed, bridging two research traditions: immediate assignment at order arrival and assignment at vehicle dispatch. Methodologically, we model the problem as a semi-Markov decision process and develop two anticipatory algorithms: a rollout policy that simulates downstream costs and a scenario-based policy that emphasizes robustness. Conceptually, our findings show that delaying commitments improves routing efficiency without undermining fairness, ensuring that customers are not disadvantaged by their location or booking time. These results highlight the operational importance of flexibility in time window communication. Chapter 4 examines the same-day delivery context, where customers select from offered slots at booking. Here, the challenge extends beyond routing to the design of slot menus, which strongly shape customer choices and system feasibility. To address this, we introduce a Transformer-based deep learning model that jointly optimizes slot offerings and routing in real time. Leveraging attention mechanisms, the model captures complex temporal and spatial dependencies, outperforming benchmark policies in efficiency, service levels, and scalability. It enables providers to serve more customers at lower costs while maintaining fairness, and it proves robust across diverse layouts and demand patterns. Collectively, the three chapters provide a comprehensive perspective on time window assignment, showing how exact optimization, anticipatory decision-making, and machine learning can be combined to align operational efficiency with customer promises in last-mile logistics. This thesis advances the study of time window assignment in vehicle routing by developing novel models and methodologies that integrate stochastic optimization, anticipatory decision-making, and machine learning. Together, these contributions provide a unified framework for balancing efficiency, reliability, and fairness in last-mile delivery systems, and they illustrate how optimization and learning can be combined to meet the growing demands of customer-centric logistics.