Restoring service-guarantee mappings for fixed-length windows and waiting policies in distributionally robust service time-window design

For last-mile delivery systems, Hosseini, Rostami, and Araghi (2025) developed a framework that designs reliable service time windows along a vehicle route under stochastic and possibly correlated travel times, in both a stochastic setting (fully known travel-time distribution) and a distributionally robust setting (only mean and covariance known). In the base framework, the optimal windows have closed forms that carry explicit service guarantees: the penalty parameters directly control unilateral and joint violation probabilities. Two practically important extensions—fixed-length (standardized-width) time windows and a policy allowing vehicles to wait when arriving before a window's lower bound—were analyzed only in the stochastic setting, and the authors point out that allowing waiting disrupts the penalty-to-violation-probability linkage. The open problem is to embed both extensions into the distributionally robust framework and to re-characterize the explicit service-guarantee mappings there, or to prove that no such mappings of the original form survive and identify the modified penalty structure or constraints that restore them.

Background

In last-mile delivery, a service provider often promises each customer a time window during which the delivery vehicle will arrive. When the provider (rather than the customer) chooses these windows, the problem is known in the operations-research literature as the self-imposed time window problem (Jabali et al. 2015; Vareias et al. 2019; Ulmer et al. 2024). Wider windows are more likely to be met but less attractive to customers, so window design trades window length against arrival-violation risk under uncertain travel times.

Hosseini, Rostami, and Araghi (2025) study this design problem on a predetermined route (e.g., one produced by commercial routing software) with stochastic, possibly correlated arc travel times. For each customer $k$ with window $[\ell_k, u_k]$ and route decision $y^k$, they minimize a three-term cost

$H^k(y^k, \ell_k, u_k) = a_w^k (u_k - \ell_k) + a_\ell^k H_\ell^k(y^k, \ell_k) + a_u^k H_u^k(y^k, u_k),$

where $(a_w^k, a_\ell^k, a_u^k)$ are penalty parameters expressing the provider's tolerance for window width, earliness, and tardiness, and $H_\ell^k$, $H_u^k$ quantify early and late arrival relative to the window. Two information regimes are considered. Under stochastic programming, the joint travel-time distribution is fully known and $H_\ell^k, H_u^k$ are expectations; Proposition 2.3 of that paper shows the optimal window endpoints behave like distribution quantiles, so customer $k$ receives an explicit guarantee: the probability of arriving after $\bar{\ell}_k$ is at least $1 - a_w^k/a_\ell^k$, the probability of arriving before $\bar{u}_k$ is at least $1 - a_w^k/a_u^k$, and the joint probability of arriving inside the window is at least $1 - a_w^k/a_\ell^k - a_w^k/a_u^k$. Under distributionally robust optimization (DRO), only partial distributional information is available; instead of optimizing against one distribution, one optimizes against the worst-case distribution in an ambiguity set, here a moment-based set $\mathcal{F}(\bar{\mu}, \bar{C})$ of all travel-time distributions with given mean vector $\bar{\mu}$ and covariance matrix $\bar{C}$ (in the style of Delage and Ye 2010 and Wiesemann et al. 2014). Using a classical closed-form bound for the worst-case expectation of a positive-part loss over distributions with known mean and covariance, Proposition 2.6 derives closed-form optimal windows in this DRO setting. Hoogeboom et al. (2021) treat a related robust routing problem with time window assignment, but without moment-based ambiguity sets or explicit penalty-to-probability mappings of this kind.

The paper introduces two practical extensions, both analyzed only in the stochastic setting — Extension 1 through distribution-level optimality conditions and their sample average approximation (SAA, i.e., replacing expectations by averages over sampled travel-time scenarios), and Extension 2 through an SAA formulation of the waiting model. Extension 1 imposes fixed-length windows $[\ell_k, \ell_k + w]$ with a common decision width $w$, standardizing service intervals; its per-customer cost $a_w w + a_\ell^k \mathbb{E}[(\ell_k - \tau^k)^+] + a_u^k \mathbb{E}[(\tau^k - \ell_k - w)^+]$ uses a single shared width penalty $a_w$ in place of $a_w^k$, and its first-order conditions $F^k(\bar{\ell}_k) = a_w/a_\ell^k$ and $F^k(\bar{\ell}_k + \bar{w}) = 1 - a_w/a_u^k$ — where $F^k$ is the cumulative distribution function of the arrival time $\tau^k$, and hence the guarantees $1 - a_w/a_\ell^k$, $1 - a_w/a_u^k$, and the joint confidence level $1 - (a_w/a_\ell^k + a_w/a_u^k)$ — hold at the distribution level, with SAA invoked only to bypass integration over the full travel-time distribution. Extension 2 allows waiting: if the vehicle arrives before $\ell_k$, service starts at $\ell_k$ rather than immediately, so the actual service start time becomes the recursive quantity $T^k = \max\{T^{i_{k-1}} + \tilde{t}_{i_{k-1}k}, \ell_k\}$, where $i_{k-1}$ is the predecessor on the route and $\tilde{t}$ is the random travel time; any waiting or delay at earlier stops propagates forward, so that $T^k \ge \ell_k$ holds pathwise. The per-customer cost under waiting retains only the width and tardiness terms, $a_w^k (u_k - \ell_k) + a_u^k \mathbb{E}[(T^k - u_k)^+]$ — the earliness penalty $a_\ell^k$ disappears — and the authors state that this feature disrupts the original probabilistic linkage between penalties and guarantees: the confidence level $1 - a_w^k/a_u^k$ of Propositions 2.1–2.3 becomes inapplicable to tardiness violations, and restoring it would require redefining the penalty structure or imposing additional constraints on $T^k$. Neither extension was embedded in the DRO framework (the paper notes that extending the fixed-window concept to a DRO setting entails considerable mathematical complexity), and the conclusion explicitly defers this integration to future research.

Problem Statement

Within the service time-window design framework of Hosseini, Rostami, and Araghi (2025), for a given vehicle route through customers with stochastic and possibly correlated arc travel times, extend the distributionally robust setting — where the travel-time distribution is known only through moment information (ambiguity sets such as $\mathcal{F}(\bar{\mu}, \bar{C})$ of distributions with given mean and covariance, or its generalization in which the mean is known only up to an ellipsoid and the covariance only up to a Frobenius-norm ball; these two moment-based sets are admissible alternatives, and the requested results for items 1–3 may be established for either one of them, used consistently throughout) — to the paper's two practical extensions, which were analyzed only under a fully known distribution:

1. Fixed-length time windows: embed the extension assigning every customer a window $[\ell_k, \ell_k + w]$ with a single decision width $w$ into the DRO model — under the source's Extension 1 cost, in which a single shared width penalty $a_w$ charges $a_w w$ — obtaining optimal windows (closed form or provably tight characterization) under the worst-case distribution in the ambiguity set.

2. Waiting before lower bounds: embed the extension in which the actual service start at customer $k$ is the recursive quantity $T^k = \max\{T^{i_{k-1}} + \tilde{t}_{i_{k-1}k}, \ell_k\}$, with waiting at earlier stops propagating forward, into the same DRO model; following the source's Extension 2, the per-customer cost retains only the width and tardiness terms $a_w^k (u_k - \ell_k) + a_u^k \mathcal{H}_u^k$, with the tardiness term $\mathcal{H}_u^k$ evaluated as the worst-case expectation $\sup_{P} \mathbb{E}_{P}[(T^k - u_k)^+]$ over the ambiguity set and no earliness term.

3. Service-guarantee mappings: re-characterize, for each embedded extension in the DRO setting, the explicit relationships between the penalty parameters appearing in that extension's cost and the worst-case violation probabilities over the ambiguity set. For the fixed-width extension (item 1), these are the unilateral earliness and tardiness probabilities and the joint probability of arriving inside the window, measured on the arrival time $\tau^k$ and parameterized by $(a_w, a_\ell^k, a_u^k)$, analogous to the stochastic-setting guarantees $1 - a_w/a_\ell^k$, $1 - a_w/a_u^k$, and the joint confidence level $1 - (a_w/a_\ell^k + a_w/a_u^k)$, and to the DRO closed forms of Proposition 2.6. For the waiting extension (item 2), the waiting cost retains only $(a_w^k, a_u^k)$ and $T^k \ge \ell_k$ holds pathwise, so the objects to be characterized are the worst-case tardiness probability of the event $\{T^k > u_k\}$ over the ambiguity set and the resulting probability of the event $\{T^k \le u_k\}$ that service starts inside the window, analogous to the stochastic-setting confidence level $1 - a_w^k/a_u^k$; no earliness guarantee measured on the raw arrival is required there, because it is not parameterized by any penalty of the waiting model. In each case, either produce such a mapping, or prove that no mapping of this form survives the corresponding extension under moment ambiguity — the waiting recursion for item 2, the fixed-width coupling for item 1 — and identify the modified penalty structure or the additional constraints on $T^k$ that restore an explicit guarantee. Here "a mapping of this form" means a distribution-free confidence-level formula that expresses the (worst-case) violation-probability bound directly in terms of the penalty parameters, as the confidence levels of Propositions 2.3 and 2.6 do, and is claimed to hold for all admissible penalty values and all travel-time distributions in the ambiguity set; a negative result must specify the class of candidate mappings ruled out and the range of penalties, routes/instances, and distributions over which nonexistence is claimed.

The common objective is that the two practical policies become available with the same kind of a priori risk control — penalty parameters that directly determine violation-probability guarantees — that the base framework provides. As in the source, items 1 and 2 are two separate DRO embeddings: each extension enters the moment-based DRO model with its own per-customer cost, and the guarantee characterization of item 3 is sought for each embedded extension; a single combined DRO model imposing fixed widths and waiting simultaneously is not part of the stated goal.

References

1. Hosseini, Davod; Rostami, Borzou; Araghi, Mojtaba (2025). Service Time Window Design in Last-Mile Delivery. arXiv:2508.01032. DOI: 10.48550/arXiv.2508.01032. https://arxiv.org/abs/2508.01032
2. Bharti, Bharti; Bekker, René; Levering, Nikki; Mandjes, Michel (2026). A framework for window design in delivery schedules. arXiv:2601.19601. DOI: 10.48550/arXiv.2601.19601. https://arxiv.org/abs/2601.19601
3. Mahes, Roshan; Boon, Marko A. A.; Kuiper, Alex; Mandjes, Michel; Bijma, Fetsje (2024). Dynamic Time-Window Updates in Last-Mile Delivery: 'Follow Your Parcel'. SSRN preprint. DOI: 10.2139/ssrn.4919725. https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4919725
4. Hoogeboom, M.; Adulyasak, Y.; Dullaert, W.; Jaillet, P. (2021). The Robust Vehicle Routing Problem with Time Window Assignments. Transportation Science. DOI: 10.1287/trsc.2020.1013. https://doi.org/10.1287/trsc.2020.1013
5. Ulmer, M.; Goodson, J.; Thomas, B. (2024). Optimal Service Time Windows. Transportation Science. DOI: 10.1287/trsc.2023.0004. https://doi.org/10.1287/trsc.2023.0004
6. Vareias, A.; Repoussis, P.; Tarantilis, C. (2019). Assessing Customer Service Reliability in Route Planning with Self-Imposed Time Windows and Stochastic Travel Times. Transportation Science. DOI: 10.1287/trsc.2017.0748. https://doi.org/10.1287/trsc.2017.0748
7. Jabali, O.; Leus, R.; Van Woensel, T.; de Kok, T. (2015). Self-imposed time windows in vehicle routing problems. OR Spectrum. DOI: 10.1007/s00291-013-0348-1. https://doi.org/10.1007/s00291-013-0348-1
8. Delage, E.; Ye, Y. (2010). Distributionally Robust Optimization under Moment Uncertainty with Application to Data-Driven Problems. Operations Research. DOI: 10.1287/opre.1090.0741. https://doi.org/10.1287/opre.1090.0741
9. Wiesemann, W.; Kuhn, D.; Sim, M. (2014). Distributionally Robust Convex Optimization. Operations Research. DOI: 10.1287/opre.2014.1314. https://doi.org/10.1287/opre.2014.1314