Service Time Window Design in Last-Mile Delivery
S. Davod Hosseini, Borzou Rostami, Mojtaba Araghi · 2025
Read Service Time Window Design in Last-Mile Delivery by S. Davod Hosseini, Borzou Rostami, Mojtaba Araghi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-01032.txt.
Introduction
Davod Hosseini, Borzou Rostami, and Mojtaba Araghi design delivery time windows that a courier can promise without lying, in a 2025 operations paper. A window too wide annoys customers; too narrow invites missed promises. For a fixed route, their models trade window length against violation risk, letting the firm set its own risk price per customer. When the travel time distribution is known, one model applies; when it is not, a robust twin takes over.
Both models yield closed-form windows. Tested on standard datasets, the robust version kept its promises within the firm's tolerance every time, while the plain model broke a few. Routing and windows can also be planned jointly.
Catalog record
| CREATOR | S. Davod Hosseini, Borzou Rostami, Mojtaba Araghi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 132 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-01032
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Service Time Window Design in Last-Mile Delivery S. Davod Hosseini, Borzou Rostami, Mojtaba Araghi Abstract Our study focuses on designing reliable service time windows for customers in a last-mile delivery system to boost dependability and enhance customer satisfaction. To construct time windows for a pre-determined route (e.g., provided by commercial routing software), we introduce two criteria that balance window length and the risk of violation. The service provider can allocate different penalties reflecting risk tolerances to each criterion, resulting in various time windows with varying levels of service guarantee. Depending on the degree of information available about the travel time distribution, we develop two modeling frameworks based on stochastic and distributionally robust optimization. In each setting, we derive closed-form solutions for the optimal time windows, which are functions of risk preferences and the sequence of visits. We further investigate fixed-width time windows, which standardize service intervals, and the use of a policy that allows vehicles arriving before the lower bounds to wait rather than incur a penalty. Next, we integrate service time window design with routing optimization into a unified framework that simultaneously determines optimal routing and time window allocations. We demonstrate the efficacy of our models on a rich collection of instances from well-known datasets. While a small portion of the time windows designed by the stochastic model was violated in out-of-sample tests, the distributionally robust model consistently delivered routes and time windows within the service provider’s risk tolerance. Our proposed frameworks are readily compatible with existing routing solutions, enabling service providers to design time windows aligned with their risk preferences. It can also be leveraged to produce the most efficient routes with narrow time windows that meet operational constraints at controlled levels of service guarantee. keywords On-time last-mile delivery, uncertain travel times, correlation, time window assignment, risk analysis, routing optimization † † authors: Sobey School of Business, Saint Mary’s University, Halifax, Canada [email protected] Alberta School of Business, University of Alberta, Edmonton, Canada [email protected] Lazaridis School of Business and Economics, Wilfrid Laurier University, Waterloo, Canada [email protected] † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: † † affiliation: 1 Introduction The exponential growth of e-commerce has substantially amplified the volume of business-to-consumer deliveries, witnessing a 54% surge in domestic parcel delivery volumes across the European Union between 2016 and 2020 ( European Commission and SMEs 2022 ) . In the fulfillment of online orders, the so-called last mile , the delivery of the order from the carrier to the customer’s doorstep, is arguably the least efficient and most expensive stage in the delivery process ( Macioszek 2018 ) . This, along with the consistent growth of urban population, could cause more traffic congestion in a city center, creating a negative impact on the well-being of the city economically, socially, and environmentally ( Deng et al. 2021 ) . On the other hand, however, research has shown that customers prioritize timely delivery and reliability when choosing an online retailer, and delivery performance is a significant factor in customer satisfaction and loyalty ( Salari et al. 2022 ) . Unlike on-demand delivery (such as food deliveries), where the product should be delivered as soon as possible, most online purchases are scheduled to be delivered during a time window provided by the retailer’s or a third-party delivery system. In spite of that, Deloitte reports a failure rate of 10%-15% on the first attempt at home delivery by carrier companies in Spain ( Deloitte 2020 ) . Similar numbers are reported for US, Germany, and UK with an average cost of 15 USD per failed delivery ( Loqate 2022 ) . Failed deliveries also give rise to enormous amounts of extra emissions ( Van Loon et al. 2015 ) , a deterioration of service levels ( Mangiaracina et al. 2019 ) , and collection and delivery point expenses ( Liu et al. 2019 ) . Along with inaccurate delivery information, the absence of recipients is one of the major causes of failed deliveries. Some research efforts have focused on predicting the probability of failed delivery attempts using machine learning algorithms ( Lim et al. 2023 ) . Many innovations have also been used in recent years to reduce the failed delivery incidents such as decoupling the delivery and pickup by using smart lockers ( Lyu and Teo 2022 ) . However, such a strategy is not suitable for many deliveries, e.g., perishable products such as flowers, bulky items such as furniture, or packages requiring a signature. For instance, 58% of big and bulky last mile deliveries were rescheduled ( DispatchTrack 2022 ) . Leaving the item at the door, even when possible, is not an effective solution as some areas have witnessed an increase in parcel thefts, prompting the police to recommend scheduling deliveries for when someone is at home ( WaterlooRegionalPolice 2023 ) . Thus, the need to provide customers with reliable delivery time frame still exists. A promised delivery time window helps reduce last-mile operations costs as well as customers’ uncertainty and the inconvenience of waiting, and so becomes a lever to manage customer expectations and improve customer satisfaction ( Cui et al. 2020 ) . However, most businesses that entail pick-up/delivery (including the front runners in this market such as Amazon and FedEx) or service (home services such as installations, repairs, and maintenance as well as home healthcare services such as nursing and physical therapy) only provide their customers with an arrival day or a wide time window within the day. For example, on average less than 10% of packages are assigned delivery time windows in the dataset released for 2021 Amazon Last Mile Routing Research Challenge ( Merchan et al. 2022 ) . Even when the two- to four-hour “Estimated Delivery Window”s are provided by Amazon, “they are not guaranteed and may be subject to change. Deliveries can arrive before or after estimated windows” ( Amazon 2023 ) . To optimize resources and streamline operations in last-mile delivery, companies often use approaches to consolidate multiple orders within a specific geographic area. As a common practice in the industry, a single vehicle makes multiple stops to pick up or drop off goods or products from/at different locations along a predetermined route. Although this approach enhances efficiency and significantly reduces the shipping cost of smaller lots, it increases the coordination complexity. Specifically, it complicates the estimation of delivery time window, as a single disruption along the route will affect all the remaining delivery promises and the error will be amplified as one moves further in the network. Moreover, a late delivery to a customer cannot be offset by an early delivery to another customer as customers expect on-time delivery; nearly one in three customers considers early deliveries to be just as bad as late deliveries ( DispatchTrack 2022 ) . Our study is motivated by such widespread and growing applications of this type of last-mile operation in both pick-up/delivery businesses and the service industry. Service providers, visiting multiple customers in each delivery route, desire to design the route and narrow but reliable visit time windows that are guaranteed with some level of confidence. However, even for a given route, designing such reliable time windows is