Attended home delivery (AHD) e-grocers steer demand by deciding, at each incoming customer request, which delivery time slots to offer, so that the expected profit of the resulting delivery schedule is maximized. Mackert (2019) established the first fully choice-based dynamic time slot management method: a generalized attraction model (GAM) of customer choice, a mixed-integer linear program (MILP) approximating the opportunity cost of accepting a request, and a linearized offer-set optimization that runs online. The paper itself identifies the boundaries of this paradigm: it becomes too slow beyond roughly 100 vans and very long booking horizons, its choice model captures only one context effect (assortment cardinality) for a homogeneous customer population, planning is single-day, and the per-request profit objective ignores service levels and long-run customer value. The open problem is the joint extension of this decision pipeline along all four axes at once — an online choice-based dynamic slotting method that is simultaneously industrially scalable, behaviorally realistic (context effects, customer heterogeneity, inter-day choice dependencies), multi-day, and reconciled with service-level and long-run customer-value objectives — or a rigorous demonstration that such a joint extension is unattainable. Each of these axes has so far been addressed only in isolation, typically in tactical, offline, or pricing variants; their joint integration in the online setting remains open.

Background

In attended home delivery (AHD), an e-grocer or e-tailer delivers goods to customers who must be present, within a customer-chosen narrow time window. Because narrow windows make fulfillment expensive, retailers manage demand by time slot management (TSM): deciding which delivery time slots (typically 1–2 hour windows on a delivery day) to offer in which geographic areas, at what price, or to whom (Agatz, Campbell, Fleischmann, and Savelsbergh, 2011). In dynamic slotting, this decision is made separately for each incoming customer request: the retailer offers an assortment (a subset) of the still-feasible slots, the customer chooses according to a choice model or walks away, and the retailer's goal is to maximize expected total profit — revenue minus vehicle routing cost — of the final delivery schedule. Because a vehicle routing problem with time windows underlies the fulfillment, accepting an order today consumes capacity whose value is only revealed later; the induced marginal value of capacity is the opportunity cost. Exact computation of opportunity cost requires solving a stochastic dynamic program whose state includes the set of accepted orders, which is intractable (the 'curses of dimensionality', i.e. state and outcome spaces that grow exponentially with the number of accepted orders and remaining periods), so practical methods approximate it. Yang and Strauss (2017) used approximate dynamic programming (replacing the exact value function of the underlying dynamic program with tractable approximations) for AHD pricing; Klein, Mackert, Neugebauer, and Steinhardt (2018) introduced a model-based MILP approximation of opportunity cost for dynamic time slot pricing in AHD. Customer choice is commonly represented by discrete-choice models: in the multinomial logit model (MNL) each alternative has an attractiveness ('attraction') value and the choice probability of an alternative is its attraction divided by the sum of attractions of all offered alternatives plus a no-purchase term; MNL can systematically overestimate choice probabilities when the offer set is large. The generalized attraction model (GAM) of Gallego, Ratliff, and Shebalov (2015) repairs this by allowing part of each alternative's attraction to accrue to the no-purchase option when the alternative is not offered, of which MNL is a special case. Assortment optimization is the problem of choosing the offered subset to maximize expected profit under a given choice model; under basic attraction models this admits efficient linearized formulations, but context effects — dependence of a customer's preferences on which other alternatives are offered, such as the compromise effect (a tendency to prefer intermediate rather than extreme alternatives) — make utilities depend endogenously on the offer set and complicate optimization. Mackert (2019) combined these threads into the first choice-based dynamic time slot management method: a GAM captures a cardinality-based context effect (dissatisfaction growing with the number of offered slots) for a homogeneous customer population per area; a MILP approximates the opportunity cost of slot capacity, scaling linearly in its decision variables, using insertion heuristics (cheap procedures that estimate the routing cost of adding a stop to an existing route) for accepted orders and a seed-based scheme for expected future orders; and a non-linear binary program for the per-arrival offer decision, linearized via the choice model's structure, runs online and yields 4–7% higher average profit than benchmark policies in the computational study. The paper's own conclusions delimit the paradigm: the MILP-based approximation and per-arrival computations become too slow for settings with roughly more than 100 vans and booking horizons of thousands of periods, motivating decomposition of the routing component; the GAM covers only the cardinality context effect while the empirically observed compromise effect and other context dependencies remain to be incorporated; customers may exhibit choice dependencies across delivery days, requiring multi-day planning with inter-temporal capacity interactions; the per-request profit objective can induce customer rejection with negative long-run consequences, and explicit service-level constraints (for example, minimum or maximum numbers of offered slots) or long-run customer-value terms are unresolved; and attraction/dissatisfaction parameters are homogeneous per area, leaving heterogeneous customer segments out of scope.

Problem Statement

Extend choice-based dynamic time slot management in attended home delivery — the per-arrival decision of which subset of feasible delivery time slots to offer so that the expected profit of the resulting delivery schedule is maximized, under an explicit customer choice model and an approximate opportunity cost of capacity — beyond the prototype of Mackert (2019) (single-day planning, a choice model covering only the cardinality context effect, a homogeneous customer population per area, moderate fleet sizes, and a pure per-request profit objective) to a method that jointly satisfies four requirements on one decision pipeline: (R1) Industrial-scale tractability: online per-arrival decisions must remain fast enough for real-time use on instances with fleets on the order of 100 or more vehicles and booking horizons of hundreds to thousands of periods. (R2) Behavioral realism: the choice model must capture context effects beyond assortment cardinality (for example, compromise-type preferences) and heterogeneous customer segments, with the demand model integrated into — not bypassed by — the opportunity-cost approximation and the offer-set optimization. (R3) Multi-day scope: planning must span multiple delivery days with inter-temporal capacity interactions and choice dependencies across days, rather than repeating a single-day problem. (R4) Profit–service reconciliation: the objective or constraints must account for service levels (for example, minimum offered-slot requirements) and/or long-run customer value, so that short-run profit maximization cannot induce systematically harmful customer rejection. The four requirements are scientifically linked — they act on the same approximation-and-offer pipeline — and the problem is closed only by a method meeting them jointly in the online setting. Equally closing: a rigorous impossibility or fundamental-accuracy-limit result showing that requirements (R1)–(R4) cannot be jointly met by any method in this problem class; a result establishing that any subset of the requirements is jointly unattainable closes the problem equally, since it entails that the full joint extension is unattainable.

References

  1. Jochen Mackert (2019). Choice-based dynamic time slot management in attended home delivery. Computers & Industrial Engineering 129, 333–345. doi:10.1016/j.cie.2019.01.048, https://doi.org/10.1016/j.cie.2019.01.048
  2. Niels Agatz, Ann Campbell, Moritz Fleischmann, Martin Savelsbergh (2011). Time slot management in attended home delivery. Transportation Science 45(3), 435–449. doi:10.1287/trsc.1100.0346, https://doi.org/10.1287/trsc.1100.0346
  3. Xinan Yang, Arne K. Strauss (2017). An approximate dynamic programming approach to attended home delivery management. European Journal of Operational Research 263(3), 935–945. doi:10.1016/j.ejor.2017.06.034, https://doi.org/10.1016/j.ejor.2017.06.034
  4. Robert Klein, Jochen Mackert, Michael Neugebauer, Claudius Steinhardt (2018). A model-based approximation of opportunity cost for dynamic pricing in attended home delivery. OR Spectrum 40(4), 969–996. doi:10.1007/s00291-017-0501-3, https://doi.org/10.1007/s00291-017-0501-3
  5. Guillermo Gallego, Richard Ratliff, Sergey Shebalov (2015). A General Attraction Model and Sales-Based Linear Program for Network Revenue Management Under Customer Choice. Operations Research 63(1), 212–232. doi:10.1287/opre.2014.1328, https://doi.org/10.1287/opre.2014.1328
  6. Sebastian Koch, Robert Klein (2020). Route-based approximate dynamic programming for dynamic pricing in attended home delivery. European Journal of Operational Research 287(2), 633–652. doi:10.1016/j.ejor.2020.04.002, https://doi.org/10.1016/j.ejor.2020.04.002
  7. Magdalena A. K. Lang, Catherine Cleophas, Jan Fabian Ehmke (2021). Multi-criteria decision making in dynamic slotting for attended home deliveries. Omega 102, 102305. doi:10.1016/j.omega.2020.102305, https://doi.org/10.1016/j.omega.2020.102305
  8. Magdalena A. K. Lang, Catherine Cleophas, Jan Fabian Ehmke (2021). Anticipative Dynamic Slotting for Attended Home Deliveries. Operations Research Forum 2(4). doi:10.1007/s43069-021-00086-9, https://doi.org/10.1007/s43069-021-00086-9
  9. Georg Bechler, Claudius Steinhardt, Jochen Mackert, Robert Klein (2021). Product line optimization in the presence of preferences for compromise alternatives. European Journal of Operational Research 288(3), 902–917. doi:10.1016/j.ejor.2020.06.029, https://doi.org/10.1016/j.ejor.2020.06.029
  10. Katrin Waßmuth, Charlotte Köhler, Niels Agatz, Moritz Fleischmann (2023). Demand management for attended home delivery—A literature review. European Journal of Operational Research 311(3), 801–815. doi:10.1016/j.ejor.2023.01.056, https://doi.org/10.1016/j.ejor.2023.01.056
  11. Armando Peixoto, Sara Martins, Pedro Amorim, Andreas Holzapfel (2024). Strategies to improve customer service in delivery time slot management. International Transactions in Operational Research 31(2), 692–720. doi:10.1111/itor.13371, https://doi.org/10.1111/itor.13371
  12. David Fleckenstein, Robert Klein, Claudius Steinhardt (2023). Recent advances in integrating demand management and vehicle routing: A methodological review. European Journal of Operational Research 306(2), 499–518. doi:10.1016/j.ejor.2022.04.032, https://doi.org/10.1016/j.ejor.2022.04.032
  13. Özden Gür Ali, Pedro Amorim (2024). Personalized choice model for forecasting demand under pricing scenarios with observational data—The case of attended home delivery. International Journal of Forecasting 40(2), 706–720. doi:10.1016/j.ijforecast.2023.04.008, https://doi.org/10.1016/j.ijforecast.2023.04.008
  14. David Fleckenstein, Robert Klein, Vienna Klein, Claudius Steinhardt (2025). On the Concept of Opportunity Cost in Integrated Demand Management and Vehicle Routing. Transportation Science 59(1), 125–142. doi:10.1287/trsc.2024.0644, https://doi.org/10.1287/trsc.2024.0644
  15. Jean-François Cordeau, Manuel Iori, Dario Vezzali (2024). An updated survey of attended home delivery and service problems with a focus on applications. Annals of Operations Research 343(2), 885–922. doi:10.1007/s10479-024-06241-9, https://doi.org/10.1007/s10479-024-06241-9
  16. David Fleckenstein, Robert Klein, Vienna Klein, Claudius Steinhardt (2025). Explaining the performance impact of opportunity costs approximation in integrated demand management and vehicle routing. EURO Journal on Transportation and Logistics 14, 100166. doi:10.1016/j.ejtl.2025.100166, https://doi.org/10.1016/j.ejtl.2025.100166
  17. Dorsa Abdolhamidi, Virginie Lurkin (2025). A tactical time slot management problem under mixed logit demand. OR Spectrum (advance online publication). doi:10.1007/s00291-025-00838-7, https://doi.org/10.1007/s00291-025-00838-7
  18. Ali Nalbant, Barış Yıldız (2025). A machine learning approach for marginal fulfillment cost estimation in last mile delivery. Transportation Research Part C: Emerging Technologies 178, 105163. doi:10.1016/j.trc.2025.105163, https://doi.org/10.1016/j.trc.2025.105163