pith. sign in

arxiv: 2604.27622 · v1 · submitted 2026-04-30 · 🧮 math.OC

Exact formulations for rectangular-warehouse single-picker routing with scattered storage in single-block and two-block layouts

George Dunn This is my paper

Pith reviewed 2026-05-07 07:55 UTC · model grok-4.3

classification 🧮 math.OC
keywords warehouse routingsingle picker routingmixed-integer linear programmingscattered storagerectangular layoutsexact optimizationsingle-block warehousetwo-block warehouse
0
0 comments X

The pith

Two new MILP formulations simplify exact single-picker routing in rectangular warehouses by using structural properties of optimal tours.

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

The paper develops two mixed-integer linear programming formulations for the single-picker routing problem and its scattered-storage variant in single-block and two-block rectangular warehouses. These models exploit properties of optimal tours to simplify how connectivity is modeled and to drop redundant edges. Extensive tests on large random benchmark sets show faster solves than prior exact methods and network-flow baselines, especially for scattered storage. The approach supports embedding optimal routing directly into larger planning or design optimizations where dynamic programming is difficult to integrate.

Core claim

We propose two mixed-integer linear programming formulations that exploit structural properties of optimal tours to simplify connectivity modelling and remove redundant edge configurations: a Configuration Connectivity model tailored to single-block layouts and an Edge Connectivity model that extends to two-block layouts. In extensive computational experiments on large randomly generated benchmark sets for single-block and two-block rectangular layouts, we compare these formulations against established MILP and network-flow baselines for SPRP and SPRP-SS and report computational gains tied to the structural restrictions.

What carries the argument

Exploitation of structural properties of optimal tours in MILP formulations to simplify connectivity modeling and eliminate redundant edge configurations for single-block and two-block warehouse routing.

If this is right

  • Exact optimal routes become available for both SPRP and SPRP-SS in the tested layouts.
  • The models run faster than prior exact baselines on large random instances.
  • Routing subproblems can be embedded directly inside warehouse design or planning optimizations.
  • Compact solver-based exact models become practical for industrial use where dynamic programming integration is cumbersome.

Where Pith is reading between the lines

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

  • These models could replace heuristic routing inside real-time warehouse management systems if solve times continue to scale.
  • The same structural restrictions on tours might extend to three-block or other common rectangular layouts.
  • Using the formulations inside layout-optimization loops could produce warehouse designs that minimize total travel distance under scattered storage.

Load-bearing premise

Structural properties of optimal tours in single-block and two-block rectangular warehouses allow connectivity modeling to be simplified without missing any truly optimal routes.

What would settle it

Solve a collection of small instances with the new models and with a known exact method such as dynamic programming; the new models produce a route whose length differs from the known optimum on any instance.

Figures

Figures reproduced from arXiv: 2604.27622 by George Dunn.

Figure 1
Figure 1. Figure 1: Rectangular warehouse layout with relevant features labelled. view at source ↗
Figure 2
Figure 2. Figure 2: Graph representation of the warehouse in Figure 1. view at source ↗
Figure 3
Figure 3. Figure 3: An example of a tour subgraph for the warehouse in Figure 1. view at source ↗
Figure 4
Figure 4. Figure 4: An example of a tour subgraph for a scattered-storage instance with SKUs A view at source ↗
Figure 5
Figure 5. Figure 5: Illustration of the vertical configuration variables in the GS formulation. view at source ↗
Figure 6
Figure 6. Figure 6: Vertical configuration variables in the EC formulation for general warehouse view at source ↗
Figure 7
Figure 7. Figure 7: Example of a necessary double traversal in a two-block SPRP (a), a two-block view at source ↗
Figure 8
Figure 8. Figure 8: Two ways for crosses aj and bj to be connected in aisle j. (a) Indirectly via the previous aisle. (b) Directly though a single traversal. Connection (upper bound). This constraint says that aj and bj can be con￾nected only if they are connected via a single edge or through the previous aisle. τj,a,b ≤ x | jb [ j>0 + ˘pj(a,b) ] j ∈ J (EC-21) 25 view at source ↗
Figure 9
Figure 9. Figure 9: Adjacent vertices aj and bj (left) can be connected as in single-block or via cj (symmetrically for bj and cj ). Boundary vertices aj and cj (right) can be connected through the previous aisle, directly, or via one of the two combinations including bj . Previous-aisle connections are drawn as a single line for simplicity; they may also involve double horizontal edges. In this section we will introduce the … view at source ↗
Figure 10
Figure 10. Figure 10: Comparison of formulation runtimes (log scale) for single-block warehouses view at source ↗
Figure 11
Figure 11. Figure 11: Comparison of formulation runtimes (log scale) for two-block warehouses with view at source ↗
Figure 5
Figure 5. Figure 5: Appendix A.1. Standard SPRP formulation Objective (Minimize tour length). minX j∈J c j x j +cjxj+cjxj+c j x j +c | jx | j+c || j x || j + X j∈J X i∈Ij  c ∧ji x ∧ ji + ∨ cji ∨ xji (A.1) Cross-aisle configurations. x j + xj + xj + x j = 1 j ∈ J \ {m − 1} (A.2) Visit all required positions. x | j + x || j + X i ′∈Ij :i ′≥i ∨ xji′ + X i ′∈Ij :i ′≤i x ∧ ji′ ≥ 1 j ∈ J , i ∈ Ij (A.3) Top and bottom connectivity… view at source ↗
read the original abstract

Order picking travel dominates much of warehouse effort, and exact routing is especially valuable when storage is scattered so pick locations are not fixed in advance. We address the single picker routing problem (SPRP) and its scattered-storage variant (SPRP-SS) in single-block and two-block rectangular warehouses. We propose two mixed-integer linear programming formulations that exploit structural properties of optimal tours to simplify connectivity modelling and remove redundant edge configurations: a Configuration Connectivity model tailored to single-block layouts and an Edge Connectivity model that extends to two-block layouts. In extensive computational experiments on large randomly generated benchmark sets for single-block and two-block rectangular layouts, we compare these formulations against established MILP and network-flow baselines for SPRP and SPRP-SS and report computational gains tied to the structural restrictions. The results support using compact, solver-based exact routing models in industrial settings where dynamic programming is cumbersome to integrate, particularly for SPRP-SS and for routing subproblems embedded in larger planning or warehouse-design optimizations.

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

3 major / 2 minor

Summary. The manuscript proposes two mixed-integer linear programming formulations for the single-picker routing problem (SPRP) and its scattered-storage variant (SPRP-SS) in single-block and two-block rectangular warehouse layouts. The formulations exploit structural properties of optimal tours to simplify connectivity modeling and remove redundant edge configurations: a Configuration Connectivity model for single-block layouts and an Edge Connectivity model for two-block layouts. Extensive experiments on large random benchmark sets compare these against established MILP and network-flow baselines, reporting computational gains tied to the structural restrictions.

Significance. If the structural properties of optimal tours are exhaustively derived and the models remain exact, the work supplies compact, solver-friendly exact formulations that are easier to embed in larger warehouse-design or planning optimizations than dynamic programming approaches. This is particularly useful for SPRP-SS instances where pick locations vary, and the reported gains on random instances suggest practical value in industrial settings.

major comments (3)
  1. [3.2] §3.2 (Configuration Connectivity model): The structural properties used to eliminate redundant edge configurations and simplify connectivity are motivated by case analysis of tours, but the manuscript provides no formal proof (e.g., via improvement argument or exhaustive enumeration of all possible optimal tour topologies) that every optimal solution satisfies them. If a counterexample optimal tour violates one of the assumed structures, the reduced model would be incomplete and could return suboptimal or infeasible solutions for SPRP-SS.
  2. [4.1] §4.1–4.3 (Edge Connectivity model): The extension of the single-block properties to two-block layouts, including the handling of cross-aisle and cross-block edges, is presented without a theorem or proof establishing that the retained edge set still contains at least one optimal tour for every instance. This is load-bearing for the exactness claim when the model is applied to SPRP-SS.
  3. [5.3] §5.3 (computational results): The tables report average run times and gaps but omit the fraction of instances solved to proven optimality within the time limit and the distribution of gaps on unsolved instances. Without these, it is impossible to determine whether the observed speed-ups come at the cost of missing optima on a non-negligible subset of the benchmark set.
minor comments (2)
  1. [2] Figure 1 (warehouse layouts): The single-block and two-block graphs are shown schematically but lack explicit labeling of the vertex and edge sets used in the mathematical formulation; adding these labels would improve readability of the subsequent models.
  2. [2.2] §2.2 (problem statement): The definition of the scattered-storage variant (SPRP-SS) could explicitly state whether multiple copies of the same SKU are allowed on the same aisle or only across aisles, as this affects the interpretation of the pick-location variables.

Simulated Author's Rebuttal

3 responses · 0 unresolved

Thank you for the constructive feedback on our manuscript. We address each of the major comments below and outline the revisions we will make to strengthen the paper.

read point-by-point responses

  1. Referee: §3.2 (Configuration Connectivity model): The structural properties used to eliminate redundant edge configurations and simplify connectivity are motivated by case analysis of tours, but the manuscript provides no formal proof (e.g., via improvement argument or exhaustive enumeration of all possible optimal tour topologies) that every optimal solution satisfies them. If a counterexample optimal tour violates one of the assumed structures, the reduced model would be incomplete and could return suboptimal or infeasible solutions for SPRP-SS.

    Authors: We thank the referee for highlighting this important point regarding the rigor of our claims. The structural properties in the Configuration Connectivity model are derived from an exhaustive case analysis of possible tour topologies in single-block layouts, ensuring that any optimal tour can be represented within the reduced edge set. However, to address the concern directly, in the revised manuscript we will include a formal theorem and proof. The proof will use an improvement argument: we show that if a tour violates one of the properties (e.g., by using a redundant edge configuration), it can be modified by replacing segments with shorter or equal alternatives that satisfy the property, without increasing the total travel distance. This guarantees that the model captures at least one optimal solution for every SPRP-SS instance. We believe this addition will resolve the potential incompleteness issue. revision: yes

  2. Referee: §4.1–4.3 (Edge Connectivity model): The extension of the single-block properties to two-block layouts, including the handling of cross-aisle and cross-block edges, is presented without a theorem or proof establishing that the retained edge set still contains at least one optimal tour for every instance. This is load-bearing for the exactness claim when the model is applied to SPRP-SS.

    Authors: We agree that extending the properties to two-block layouts requires careful justification. The Edge Connectivity model builds on the single-block case by additionally considering the possible crossings between blocks and aisles. In the revision, we will add a dedicated theorem proving that the retained edges include an optimal tour. The proof will involve case analysis of how optimal tours traverse the two blocks, showing that any deviation from the assumed connectivity can be improved by adjusting the cross-block paths. This will confirm the exactness for SPRP-SS in two-block layouts. revision: yes

  3. Referee: §5.3 (computational results): The tables report average run times and gaps but omit the fraction of instances solved to proven optimality within the time limit and the distribution of gaps on unsolved instances. Without these, it is impossible to determine whether the observed speed-ups come at the cost of missing optima on a non-negligible subset of the benchmark set.

    Authors: This is a valid criticism of our experimental reporting. To provide a more complete picture, we will revise the tables in Section 5.3 to include the number and percentage of instances solved to proven optimality within the time limit for each method and instance class. Additionally, for the unsolved instances, we will report the distribution of optimality gaps, including the average gap, maximum gap, and the number of instances with gaps below certain thresholds (e.g., 1%, 5%). These additions will demonstrate that our formulations achieve speed-ups while maintaining high solution quality across the benchmark set. revision: yes

Circularity Check

0 steps flagged

No circularity: independent MILP formulations from structural tour analysis

full rationale

The paper derives two new MILP formulations (Configuration Connectivity for single-block, Edge Connectivity for two-block) by exploiting structural properties of optimal tours to simplify connectivity constraints and eliminate redundant edges. The abstract and description present these properties as derived from analysis of the warehouse graph, with the resulting models positioned as exact and validated via computational experiments on large random benchmark instances against established MILP and network-flow baselines. No equations reduce claims to fitted parameters by construction, no load-bearing self-citations appear, and no ansatz or renaming of known results is invoked. The derivation chain remains self-contained and externally falsifiable through the reported benchmarks, yielding an independent modeling contribution.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard domain assumptions about rectangular warehouse layouts and the existence of exploitable structural properties in optimal picker tours. No free parameters or invented entities are indicated in the abstract.

axioms (2)
  • domain assumption Warehouse layouts are rectangular with single-block or two-block configurations.
    The problem definitions and model tailoring are based on these layout types.
  • domain assumption Optimal tours exhibit structural properties that allow simplification of connectivity modeling without loss of optimality.
    This is the key premise used to design the Configuration Connectivity and Edge Connectivity formulations.

pith-pipeline@v0.9.0 · 5463 in / 1418 out tokens · 47451 ms · 2026-05-07T07:55:05.354698+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

27 extracted references · 27 canonical work pages

  1. [1]

    50 years of warehousing research—an operations research perspective

    Boysen, N., De Koster, R., 2025. 50 years of warehousing research—an operations research perspective. European Journal of Operational Re- search 320, 449–464

    work page 2025

  2. [2]

    Warehousing in the e-commerce era: A survey

    Boysen, N., De Koster, R., Weidinger, F., 2019. Warehousing in the e-commerce era: A survey. European Journal of Operational Research 277, 396–411

    work page 2019

  3. [3]

    A model for warehouse order picking

    Daniels, R.L., Rummel, J.L., Schantz, R., 1998. A model for warehouse order picking. European Journal of Operational Research 105, 1–17

    work page 1998

  4. [4]

    Design and control of warehouse order picking: A literature review

    De Koster, R., Le-Duc, T., Roodbergen, K.J., 2007. Design and control of warehouse order picking: A literature review. European journal of operational research 182, 481–501. 39

    work page 2007

  5. [5]

    Double traversals in optimal picker routes for warehouses with multiple blocks

    Dunn, G., Charkhgard, H., Eshragh, A., Stojanovski, E., 2025a. Double traversals in optimal picker routes for warehouses with multiple blocks. Operations Research Letters , 107397

    work page

  6. [6]

    Deterministic structure of vertical configurations in minimal picker tours for rectangular warehouses

    Dunn, G., Stojanovski, E., Lamichhane, B., Charkhgard, H., Eshragh, A., 2025b. Deterministic structure of vertical configurations in minimal picker tours for rectangular warehouses. Manuscript under review

    work page

  7. [7]

    Modeling single-picker routing prob- lems in classical and modern warehouses: Informs journal on computing meritorious paper awardee

    Goeke, D., Schneider, M., 2021. Modeling single-picker routing prob- lems in classical and modern warehouses: Informs journal on computing meritorious paper awardee. INFORMS Journal on Computing 33, 436– 451

    work page 2021

  8. [8]

    Research on warehouse operation: A comprehensive review

    Gu, J., Goetschalckx, M., McGinnis, L.F., 2007. Research on warehouse operation: A comprehensive review. European journal of operational research 177, 1–21

    work page 2007

  9. [9]

    Gurobi optimizer reference manual

    Gurobi Optimization, LLC, 2024. Gurobi optimizer reference manual. URL:https://www.gurobi.com/documentation/

    work page 2024

  10. [10]

    Distance approximations for routing manual pickers in a warehouse

    Hall, R.W., 1993. Distance approximations for routing manual pickers in a warehouse. IIE transactions 25, 76–87

    work page 1993

  11. [11]

    A note on the linearity of ratliff and rosen- thal’s algorithm for optimal picker routing

    Heßler, K., Irnich, S., 2022. A note on the linearity of ratliff and rosen- thal’s algorithm for optimal picker routing. Operations Research Letters 50, 155–159

    work page 2022

  12. [12]

    Exact solution of the single-picker routing problem with scattered storage

    Heßler, K., Irnich, S., 2024. Exact solution of the single-picker routing problem with scattered storage. INFORMS Journal on Computing 36, 1417–1435

    work page 2024

  13. [13]

    The Single Picker Routing Problem with Scat- tered Storage in Parallel-Aisle Warehouse with Multiple Blocks

    Irnich, S., Lüke, L., 2025. The Single Picker Routing Problem with Scat- tered Storage in Parallel-Aisle Warehouse with Multiple Blocks. Tech- nical Report. Johannes Gutenberg-Universität Mainz

    work page 2025

  14. [14]

    A linear-size model for the single picker routing problem with scattered storage

    Lüke, L., Hessenius, A., Irnich, S., 2025. A linear-size model for the single picker routing problem with scattered storage. European Journal of Operational Research

    work page 2025

  15. [15]

    The single picker routing problem with scattered storage: modeling and evaluation of routing and storage policies

    Lüke, L., Heßler, K., Irnich, S., 2024. The single picker routing problem with scattered storage: modeling and evaluation of routing and storage policies. OR Spectrum 46, 909–951. 40

    work page 2024

  16. [16]

    Exact algorithms for the order picking problem

    Pansart, L., Catusse, N., Cambazard, H., 2018. Exact algorithms for the order picking problem. Computers & Operations Research 100, 117–127

    work page 2018

  17. [17]

    An evaluation of order picking routeing policies

    Petersen, C.G., 1997. An evaluation of order picking routeing policies. International Journal of Operations & Production Management

    work page 1997

  18. [18]

    A note on the complexity of the picker routing problem in multi-block warehouses and related problems

    Prunet, T., Absi, N., Cattaruzza, D., 2025. A note on the complexity of the picker routing problem in multi-block warehouses and related problems. Annals of Operations Research 347, 1595–1605

    work page 2025

  19. [19]

    Order-picking in a rectangular warehouse: a solvable case of the traveling salesman problem

    Ratliff, H.D., Rosenthal, A.S., 1983. Order-picking in a rectangular warehouse: a solvable case of the traveling salesman problem. Opera- tions research 31, 507–521

    work page 1983

  20. [20]

    Routing order pickers in a ware- house with a middle aisle

    Roodbergen, K.J., De Koster, R., 2001. Routing order pickers in a ware- house with a middle aisle. European Journal of Operational Research 133, 32–43

    work page 2001

  21. [21]

    Warehouse design and control: Framework and literature review

    Rouwenhorst, B., Reuter, B., Stockrahm, V., vanHoutum, G.J., Mantel, R., Zijm, W.H., 2000. Warehouse design and control: Framework and literature review. European journal of operational research 122, 515– 533

    work page 2000

  22. [22]

    Arc routing based compact formulations for picker routing in single and two block parallel aisle warehouses

    Saylam, S., Çelik, M., Süral, H., 2024. Arc routing based compact formulations for picker routing in single and two block parallel aisle warehouses. European Journal of Operational Research 313, 225–240

    work page 2024

  23. [23]

    Facilities planning

    Tompkins, J.A., White, J.A., Bozer, Y.A., Tanchoco, J.M.A., 2010. Facilities planning. John Wiley & Sons

    work page 2010

  24. [24]

    Optimally solving the joint order batching and picker routing problem

    Valle, C.A., Beasley, J.E., Da Cunha, A.S., 2017. Optimally solving the joint order batching and picker routing problem. European journal of operational research 262, 817–834

    work page 2017

  25. [25]

    Picker routing in rectangular mixed shelves ware- houses

    Weidinger, F., 2018. Picker routing in rectangular mixed shelves ware- houses. Computers & Operations Research 95, 139–150

    work page 2018

  26. [26]

    Picker routing in the mixed-shelves warehouses of e-commerce retailers

    Weidinger, F., Boysen, N., Schneider, M., 2019. Picker routing in the mixed-shelves warehouses of e-commerce retailers. European Journal of Operational Research 274, 501–515. 41

    work page 2019

  27. [27]

    Picker routing in scattered storage warehouses: an evaluation of solution methods based on tsp transformations

    Wildt, C., Weidinger, F., Boysen, N., 2025. Picker routing in scattered storage warehouses: an evaluation of solution methods based on tsp transformations. OR Spectrum 47, 35–66. Appendix A. Goeke–Schneider formulation (GS) This appendix records the complete GS formulation (as used as a baseline for CC in the thesis sources), kept complete for reference. ...

    work page 2025