pith. sign in

arxiv: 2607.01489 · v1 · pith:2GHVCHP6new · submitted 2026-07-01 · 🧮 math.OC

Admission and Assortment Optimization for Multi-size Automated Parcel Lockers

Carlos An\'ibal Su\'arez , Antoine Deza , Tal Raviv This is my paper

Pith reviewed 2026-07-03 19:11 UTC · model grok-4.3

classification 🧮 math.OC
keywords parcel lockersadmission controlassortment optimizationMarkov decision processalways-accept policylocal searchcapacity design
0
0 comments X

The pith

The always-accept policy is optimal or nearly optimal for admitting parcels into multi-size automated lockers.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper models admission decisions for parcels of varying sizes into compatible lockers as a Markov decision process that tracks occupancy by size class. It establishes that the simple always-accept policy, which takes any feasible parcel, is exactly optimal when parcels are picked up quickly and has only negligible gaps from optimality when holding times are longer. For the related problem of choosing how many lockers of each size to install, the work supplies an exact algorithm for moderate instances and demonstrates that a basic local-search heuristic recovers the optimal design in all cases where the optimum can be certified exactly. These results matter because they show that complex optimal policies can often be replaced by a rule that requires no computation at decision time while still controlling rejection costs effectively.

Core claim

The always-accept policy is optimal in fast-pickup regimes and nearly optimal when holding times are longer across two-, three-, and four-size experiments, with observed optimality gaps negligible even when it is not optimal. For the locker-assortment problem the objective is not discrete convex, yet an exchange-neighborhood local search finds the certified optimum in every instance for which exact certification is computationally tractable.

What carries the argument

The finite-state infinite-horizon average-cost Markov decision process whose state is the vector of occupied lockers by size class; the always-accept policy that admits every feasible parcel; and the bound-and-enumerate algorithm together with exchange-neighborhood local search for the assortment design problem.

If this is right

  • AA is optimal when pickup rates are high.
  • AA remains near-optimal when holding times increase.
  • Optimality gaps stay negligible across tested size counts.
  • Exchange-neighborhood local search recovers the exact optimum whenever certification is feasible.
  • The same local search scales as a heuristic to larger locker systems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Real-time control systems for parcel lockers could be simplified to a stateless rule without material loss of performance.
  • The same always-accept logic may apply to other substitutable-capacity problems such as multi-size vehicle loading or hotel-room assignment.
  • Because the assortment objective is not discrete convex, similar non-convex design problems may also be solvable by neighborhood search rather than requiring specialized convex methods.
  • The approach could be tested on real locker occupancy traces to check whether the modeled Markovian assumptions hold under actual arrival and pickup patterns.

Load-bearing premise

The admission problem can be accurately captured by a finite-state infinite-horizon average-cost Markov decision process whose state tracks only the current occupancy by size class and whose costs are linear in rejections.

What would settle it

An instance in which the always-accept policy incurs a non-negligible optimality gap relative to the value function obtained by relative value iteration, or an assortment instance in which exchange-neighborhood local search returns a design whose cost exceeds the certified optimum.

Figures

Figures reproduced from arXiv: 2607.01489 by Antoine Deza, Carlos An\'ibal Su\'arez, Tal Raviv.

Figure 1
Figure 1. Figure 1: MDP transition support for b = (2, 1) where B and A denote before- and after￾replenishment copies; stacked rectangles denote arrival-contingent decisions; pickup arcs map post￾decision states to feasible next before states. The infinite-horizon average-cost MDP is described by the Bellman equation h(x) + g = EA " min y∈U(x,A) (Xn i=1 πi(xi + Ai − yi) + E [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: DTMC transition support induced by AA for [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: AA optimality for π2/π1 = 4 and ρ1 = ρ2 = 1. Optimality is obtained by Theorem 1 in striped cells and by exact value iteration in dotted cells. We next examine instances with n = 3 and 4 parcel classes [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Stress-test AA optimality for π2/π1 = 20 and ρ1 = ρ2 = 1. White cells report the relative gap. setting and an extension with an extra-large size, while the MDP formulation itself allows any number of sizes. In all capacity vectors, the number of lockers decreases as size increases, reflecting the fact that larger lockers are usually less numerous [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Average daily penalty over the locker-assortment grid with [PITH_FULL_IMAGE:figures/full_fig_p014_5.png] view at source ↗
read the original abstract

We study admission control and capacity design for automated parcel lockers with multiple parcel and locker sizes. A smaller parcel can use a larger locker, but doing so may block a future larger parcel whose rejection is more costly. We formulate the admission problem as a finite-state, infinite-horizon average-cost Markov decision process and solve small instances exactly by relative value iteration. We analyze the always-accept (AA) policy, which admits every feasible parcel into the remaining compatible capacity, and give a sufficient condition for its optimality. Across two-, three-, and four-size experiments, AA is optimal in fast-pickup regimes and nearly optimal when holding times are longer; observed optimality gaps are negligible even when AA is not optimal. We then study the locker-assortment problem, which minimizes facility cost plus optimal expected rejection cost. We give an exact bound-and-enumerate algorithm for moderate-size instances. Although the objective is not discrete convex, exchange-neighborhood local search finds the certified optimum in every instance for which exact certification is computationally tractable, and it scales as a heuristic to larger systems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper formulates admission control for multi-size automated parcel lockers as a finite-state infinite-horizon average-cost MDP whose state is the occupancy vector by size class. It derives a sufficient condition for optimality of the always-accept (AA) policy from the average-cost Bellman operator, reports that AA is optimal or near-optimal (with negligible gaps) in two-, three-, and four-size numerical experiments under fast-pickup and longer holding-time regimes, and studies the locker-assortment problem of minimizing facility cost plus optimal expected rejection cost. An exact bound-and-enumerate algorithm is given for moderate instances; although the objective is not discrete convex, exchange-neighborhood local search recovers the certified optimum on all tractable instances.

Significance. If the modeling and algorithmic claims hold, the work supplies both a practical policy (AA) with a verifiable optimality condition and certified solution methods for the joint admission-assortment design problem in parcel logistics. The exhaustive certification of local search on all solvable instances and the explicit sufficient condition for AA optimality are concrete strengths that support the reported performance claims.

minor comments (3)
  1. [§3] §3 (MDP formulation): clarify whether the linear rejection-cost assumption is without loss of generality or requires justification for the specific application; the current statement leaves the modeling choice implicit.
  2. [Tables 1-3] Table 1–3 (numerical results): report the exact number of instances solved to optimality by bound-and-enumerate versus those solved only by local search, and state the largest instance size for which exact certification remains tractable.
  3. [§4.2] §4.2 (assortment algorithm): the description of the bound-and-enumerate procedure would benefit from a short pseudocode block or explicit enumeration order to make the implementation reproducible.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No major comments were provided in the report, so we interpret the request as pertaining to minor improvements in presentation or clarity, which we will incorporate in the revised version.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper models the admission problem directly as an average-cost MDP with state equal to occupancy vector by size class and linear rejection costs. The sufficient condition for AA optimality is derived from the Bellman operator on this MDP. The assortment problem is solved by an exact bound-and-enumerate procedure whose correctness does not rely on fitted parameters or prior self-citations. No step reduces a claimed prediction or optimality result to a definition or fit of the same quantity. The derivation chain is self-contained against the stated MDP assumptions.

Axiom & Free-Parameter Ledger

2 free parameters · 1 axioms · 0 invented entities

Abstract-only review; the model depends on unspecified arrival processes, holding-time distributions, and rejection-cost parameters that are treated as inputs. No invented entities are introduced.

free parameters (2)
  • rejection costs by size
    Costs for rejecting parcels of different sizes are parameters that drive the objective; their specific values are not given in the abstract.
  • arrival rates and holding-time parameters
    Parameters governing parcel arrivals and pickup times are required to define the MDP transition probabilities and are not reported.
axioms (1)
  • domain assumption The system dynamics admit a finite-state representation based solely on current occupancy counts by size class.
    Abstract states the admission problem is formulated as a finite-state MDP.

pith-pipeline@v0.9.1-grok · 5721 in / 1363 out tokens · 27118 ms · 2026-07-03T19:11:40.469352+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

  1. [1]

    Louis Faugère and Benoit Montreuil

    doi: 10.1080/ 00207543.2017.1395490. Louis Faugère and Benoit Montreuil. Smart locker bank design optimization for urban omnichannel logistics: Assessing monolithic vs. modular configurations.Computers & Industrial Engineering, 139:105544,

    work page arXiv 2017

  2. [2]

    Itai Gurvich and Ohad Perry

    doi: 10.1016/j.cie.2018.11.054. Itai Gurvich and Ohad Perry. Overflow networks: Approximations and implications to call center outsourcing.Operations Research, 60(4):996–1009,

    work page doi:10.1016/j.cie.2018.11.054 2018

  3. [3]

    Stanisław Iwan, Kinga Kijewska, and Justyna Lemke

    doi: 10.1287/opre.1120.1070. Stanisław Iwan, Kinga Kijewska, and Justyna Lemke. Analysis of parcel lockers’ efficiency as the last mile delivery solution – the results of the research in poland.Transportation Research Procedia, 12:644–655,

    work page doi:10.1287/opre.1120.1070

  4. [4]

    Michael Kahr

    doi: 10.1016/j.trpro.2016.02.018. Michael Kahr. Determining locations and layouts for parcel lockers to support supply chain viability at the last mile.Omega, 113:102721,

    work page doi:10.1016/j.trpro.2016.02.018 2016

  5. [5]

    doi: 10.1016/j.omega.2022.102721. Anton J. Kleywegt and Jason D. Papastavrou. The dynamic and stochastic knapsack problem. Operations Research, 46(1):17–35,

    work page doi:10.1016/j.omega.2022.102721 2022

  6. [6]

    doi: 10.1287/opre.46.1.17. Anton J. Kleywegt and Jason D. Papastavrou. The dynamic and stochastic knapsack problem with random sized items.Operations Research, 49(1):26–41,

    work page doi:10.1287/opre.46.1.17

  7. [7]

    27 Abraham Leung, Ugo Lachapelle, and Matthew Burke

    doi: 10.1287/opre.49.1.26.11185. 27 Abraham Leung, Ugo Lachapelle, and Matthew Burke. Spatio-temporal analysis of australia post parcel locker use during the initial system growth phase in queensland (2013–2017).Journal of Transport Geography, 110:103634,

    work page doi:10.1287/opre.49.1.26.11185 2013

  8. [8]

    Bohao Ma, Yiik Diew Wong, and Chee-Chong Teo

    doi: 10.1016/j.jtrangeo.2023.103634. Bohao Ma, Yiik Diew Wong, and Chee-Chong Teo. Parcel self-collection for urban last-mile deliver- ies: A review and research agenda with a dual operations–consumer perspective.Transportation Research Interdisciplinary Perspectives, 16:100719,

    work page doi:10.1016/j.jtrangeo.2023.103634 2023

  9. [9]

    Bohao Ma, Chee-Chong Teo, and Yiik Diew Wong

    doi: 10.1016/j.trip.2022.100719. Bohao Ma, Chee-Chong Teo, and Yiik Diew Wong. Location analysis of parcel locker network: Effects of spatial characteristics on operational performance.Transportation Research Part E: Logistics and Transportation Review, 192:103776,

    work page doi:10.1016/j.trip.2022.100719 2022

  10. [10]

    Simona Mancini and Margaretha Gansterer

    doi: 10.1016/j.tre.2024.103776. Simona Mancini and Margaretha Gansterer. Dynamic stochastic parcel locker assignment with uncertain pick-up times.Omega, 140:103478,

    work page doi:10.1016/j.tre.2024.103776 2024

  11. [11]

    Ido Orenstein and Tal Raviv

    doi: 10.1016/j.omega.2025.103478. Ido Orenstein and Tal Raviv. Parcel delivery using the hyperconnected service network.Trans- portation Research Part E: Logistics and Transportation Review, 161:102716,

    work page doi:10.1016/j.omega.2025.103478 2025

  12. [12]

    Ido Orenstein, Tal Raviv, and Elad Sadan

    doi: 10.1016/j.tre.2022.102716. Ido Orenstein, Tal Raviv, and Elad Sadan. Flexible parcel delivery to automated parcel lockers: Models, solution methods and analysis.EURO Journal on Transportation and Logistics, 8(5): 683–711,

    work page doi:10.1016/j.tre.2022.102716 2022

  13. [13]

    doi: 10.1007/s13676-019-00144-7. Jason D. Papastavrou, Srikanth Rajagopalan, and Anton J. Kleywegt. The dynamic and stochastic knapsack problem with deadlines.Management Science, 42(12):1706–1718,

    work page doi:10.1007/s13676-019-00144-7

  14. [14]

    Do parcel lockers reduce delivery times? evidence from the field.Transportation Research Part E: Logistics and Transportation Review, 172:103070, 2023a

    Andisheh Ranjbari, Caleb Diehl, Giacomo Dalla Chiara, and Anne Goodchild. Do parcel lockers reduce delivery times? evidence from the field.Transportation Research Part E: Logistics and Transportation Review, 172:103070, 2023a. doi: 10.1016/j.tre.2023.103070. Andisheh Ranjbari, Caleb Diehl, Giacomo Dalla Chiara, and Anne Goodchild. What is the right size f...

    work page doi:10.1016/j.tre.2023.103070 2023

  15. [15]

    Samyukta Sethuraman, Ankur Bansal, Setareh Mardan, Mauricio G

    doi: 10.1016/j.tre.2023.103216. Samyukta Sethuraman, Ankur Bansal, Setareh Mardan, Mauricio G. C. Resende, and Timothy L. Jacobs. Amazon locker capacity management.INFORMS Journal on Applied Analytics, 54(6): 455–470,

    work page doi:10.1016/j.tre.2023.103216 2023

  16. [16]

    Donald M

    doi: 10.1287/inte.2023.0005. Donald M. Topkis.Supermodularity and Complementarity. Princeton University Press, Princeton, NJ,

    work page doi:10.1287/inte.2023.0005 2023

  17. [17]

    doi: 10.1016/j.tre.2025.104541. 28

    work page doi:10.1016/j.tre.2025.104541 2025