REVIEW 3 major objections 4 minor 8 references
Double Traversals in Optimal Picker Routes for Warehouses with Multiple Blocks
T0 review · 3 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read In rectangular warehouses with any number of cross-aisles, some shortest picker tour never uses a double traversal of a subaisle as a connector.
desk verdict The claimed result is a clean refinement and would be useful, but the proof in Section 3 has a real gap in the degree-parity argument, so the result is unproven as written. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The argument rests on a local transformation $T \to T'$ in which the two edges $\{(a_i, b_i), (b_{i-1}, b_i)\}$ are replaced by $\{(a_{i-1}, b_{i-1}), (a_{i-1}, a_i)\}$, together with a state $s = (m(a_{i-1}, a_i), m(b_{i-1}, b_i))$ that tracks horizontal incidence at the endpoints. By symmetry only five states need checking; each is shown reducible, except that the $(0,1)$ state may shift the double edge one aisle left. Because the leftmost aisle cannot support a connecting double edge, the shifting process terminates, proving that some optimal tour subgraph avoids connecting double edges entirely.
What would settle it
Enumerate all minimum-length tour subgraphs for a small rectangular warehouse with, say, 3 cross-aisles and 4 aisles, and check whether every optimal tour contains a connecting double edge; if there is an instance where no optimal tour avoids one, the theorem fails. Since double traversals are known to occur in some such instances, the search can be restricted to those cases.
Extended reading notes
Core claim
The central claim, Theorem 1, is that there exists a minimum-length tour subgraph $T \subseteq G$ that contains no connecting double edge, where a connecting double edge is a subaisle traversed twice with horizontal edges incident at both ends. The proof represents each connecting double edge by the number of horizontal edges entering the two endpoints from the left, reduces five possible states to two preliminary cases, and applies a local edge swap that either removes the double edge, shifts it one aisle to the left, or shows it is redundant. Because a double edge in the first aisle can only belong to reducible states, iterating the swap eliminates all connecting double edges. The result does not say that double traversals are never needed; it says they are never needed to connect horizontal travel.
Load-bearing premise
The proof depends on the assertion that its local swap always yields a valid tour subgraph, in particular that every vertex degree stays even; for one configuration the paper asserts the reduction without spelling out the alternative operation that would keep the intermediate vertices even.
Editorial extensions
If this is right
- Any exact algorithm for picker routing with $n \geq 2$ cross-aisles can restrict its vertical edge configurations to those that do not connect horizontal travel at both ends without losing optimality.
- When a double traversal does appear in an optimal route, its purpose is to visit items stored inside that subaisle, not to connect the surrounding cross-aisle components.
- The elimination argument applies unchanged to both horizontal and vertical edges in the related rectilinear TSP algorithm, so its state space can be similarly simplified.
- The structure of feasible tour subgraphs becomes simpler, which supports more efficient dynamic programs for order picking in warehouses with several blocks.
Reading between the lines
- This suggests that existing dynamic-programming implementations can be pruned by deleting the connecting double-edge transition entirely, a change that would shrink constant factors without changing the reported optimum on published benchmarks.
- A natural testable extension is whether the same reduction survives when subaisle lengths are non-uniform or when pickup points lie at cross-aisle intersections; the proof's swap does not explicitly rely on equal subaisle lengths, but the state analysis would need rechecking.
- The left-shift termination argument hints at a stronger canonical form for optimal routes: every double traversal occupies a subaisle whose endpoints have no horizontal incident edges, which could simplify route enumeration heuristics.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the order-picking problem in a rectangular parallel-aisle warehouse with multiple cross-aisles. It claims a structural result (Theorem 1): there exists a minimum-length tour subgraph that contains no 'connecting double edge,' i.e., no subaisle traversed twice whose endpoints both have incident horizontal edges. The proof models the problem as an Eulerian tour subgraph, defines five states for a connecting double edge based on left-incident horizontal edge multiplicities, and proposes a local transformation T → T′ that moves or eliminates the double edge. The authors argue that iterating this transformation reduces and eventually removes all connecting double edges, thereby simplifying the set of configurations needed in dynamic programming algorithms.
Significance. If the main theorem is correct, it is a valuable structural insight: it shows that, although double aisle traversals are sometimes necessary for optimal picker routes when there are more than two cross-aisles, they are never needed for the purpose of connecting horizontal travel. This could reduce the state space of existing dynamic programming algorithms (Ratliff–Rosenthal, Roodbergen–de Koster, Pansart et al.) and extend the earlier two-cross-aisle result. The paper is concise and builds on the standard Eulerian characterization of tour subgraphs, and the claim is falsifiable. However, the proof as written has several gaps that are load-bearing for the theorem, so the significance can only be realized after a complete and correct proof is supplied.
major comments (3)
- [Section 3, transformation definition and condition (iii)] The claim that T′ preserves even vertex degrees is not correct in general. For state (0,1), the connecting double edge (a_i,b_i)2 requires, by definition of 'connecting,' a horizontal edge incident to a_i from the right (since m(a_{i-1},a_i)=0). To make the degree of a_i even in T, that right edge must have even multiplicity (e.g., a double horizontal edge). In the transformation, a_i loses the two edges of the removed double edge and gains one left horizontal edge, a net odd change of degree parity; similarly b_i loses three incident edges and gains none. Thus T′ need not satisfy condition (iii) of Theorem A, and the example in Figure 6(a) cannot represent a valid transformation unless other edge modifications are made. The proof must either add further operations (e.g., rerouting right-incident edges) or justify that the right-hand multiplicities are such that parity is preserved.
- [Section 3, Case 0.2] The sentence 'if any subaisles between these two vertices contain a configuration other than a single edge, the transformation immediately reduces the number of double edges for any state' is not followed by a construction. If (a_{i-1},b_{i-1})1 is not a full single edge, the transformation as defined cannot simply add the complete double edge (a_{i-1},b_{i-1})2 without potentially creating a new connecting double edge on a subrange. For instance, suppose aisle i-1 contains a single edge on a proper subrange of (a_{i-1},b_{i-1}) and a different configuration on the remainder, with horizontal edges incident at both ends of that subrange; adding a double edge over the whole interval creates a connecting double edge on that subrange, so the number of connecting double edges does not immediately decrease. The proof needs an explicit alternative operation or a rigorous argument that such configurations are covered by other cases.
- [Section 3, termination argument] No well-defined potential function is given to support the claimed reduction. The phrase 'the total number of subaisles involved in connecting double edges' is not formalized, and it is not shown that the transformation strictly decreases this quantity in every branch, particularly in Case 3(iii) where the double edge is 'shifted one aisle to the left.' The termination argument also refers to a 'flipping' or mirroring step at the first aisle that is not described. A rigorous proof needs a precise measure that decreases lexicographically (or by another well-founded order) with each transformation, and a complete treatment of the boundary case at the first/last aisle.
minor comments (4)
- [Introduction] There is a typo in the sentence 'there are cases where it is required for warehouses with more that two aisles' — it should be 'more than two aisles.'
- [Section 2, definitions] The notation '( a_i,b_i )' is used both for a single edge and, with subscript 2, for a double edge. The transformation in Section 3 writes (a_i,b_i) without the subscript 2, which is ambiguous; it should be stated explicitly which multiplicity is being removed.
- [Figure 6] The shaded regions representing 'unknown configurations in the previous aisle' are not explained in the caption or text; the reader cannot determine what configurations are being abstracted away, which is important because the parity argument depends on them.
- [Section 1] The references to previous algorithms are accurate, but the relation of Theorem 1 to the fixed-parameter algorithms of Cambazard and Catusse is mentioned only briefly in the conclusion; a sentence elaborating on why the result applies there would improve readability.
Circularity Check
No circular derivation: Theorem 1 is proved from an external Eulerian characterization with no fitted inputs and no load-bearing self-citations.
full rationale
Theorem 1 is established by starting from any minimum tour subgraph, characterized by the external Eulerian conditions of Ratliff and Rosenthal, then applying a local edge-exchange transformation of equal total length and using a finite case analysis over the possible incident horizontal edge counts. No parameter is fitted, no quantity is defined in terms of the target conclusion, and the paper contains no self-citations that carry the argument: references [1] and [6] supply the tour-subgraph characterization as independent external foundations, while [3], [4], [5], and [7] are background or application references by other author groups. The state set S is a case distinction over horizontal edge multiplicities, not a restatement of the theorem. The proof does contain a rigor gap in Case 0.2, where the claim that the transformation 'immediately reduces the number of double edges' is not fully demonstrated for partial vertical configurations, and the mirroring argument for the first aisle is terse. That is a correctness or termination concern, not circularity, because nothing in that step assumes the truth of the theorem being proved. The derivation therefore does not reduce to its own inputs by construction, and there is no circular dependency on the authors' prior work.
Assumptions & free parameters
assumptions (3)
- standard math Eulerian tour subgraph characterization: a subgraph is a tour subgraph iff it contains all P, is connected, and every vertex has even degree (Theorem A from Ratliff and Rosenthal).
- domain assumption Optimal routes can be restricted to six vertical and three horizontal subaisle configurations from prior work [1,3,4].
- domain assumption Rectangular warehouse with uniform subaisle and cross-aisle lengths, allowing reflection symmetry.
Cite this review
Pith. "Pith review of Double Traversals in Optimal Picker Routes for Warehouses with Multiple Blocks." pith.science (2026). https://pith.science/paper/M4HKDADH
@misc{pith2026250114123,
author = {Pith},
title = {Pith review of: Double Traversals in Optimal Picker Routes for Warehouses with Multiple Blocks},
year = {2026},
howpublished = {\url{https://pith.science/paper/M4HKDADH}},
note = {Machine review of arXiv:2501.14123}
}
read the original abstract
Order picking is a process that involves collecting items from their respective locations within a warehouse. There exist dynamic programming algorithms for finding the minimal picker route by considering only a limited number of options for possible travel within a subaisle. Although one such action, traversing an aisle twice, has been shown to never be required for a rectangular warehouse with two cross-aisles, this is not the case when there are more than two cross-aisles. In this work, we demonstrate that double traversals within a subaisle are not required to connect cross-aisle travel regardless of the number of cross-aisles. This result simplifies the structure of feasible tours, enabling more efficient algorithms.
Figures
Figures from the paper (1 more)
Reference graph
Works this paper leans on
-
[1]
H. D. Ratliff, A. S. Rosenthal, Order-picking in a rectangular warehouse: a solvable case of the traveling salesman problem, Operations research 31 (1983) 507–521
work page 1983
-
[2]
K. Heßler, S. Irnich, A note on the linearity of ratliff and rosenthal’s algorithm for optimal picker routing, Operations Research Letters 50 (2022) 155–159. doi:https://doi.org/10.1016/j.orl.2022.01.014
-
[3]
K. J. Roodbergen, R. de Koster, Routing order pickers in a warehouse with a middle aisle, European Journal of Operational Research 133 (2001) 32–43. doi:https://doi.org/10.1016/S0377-2217(00)00177-6
-
[4]
L. Pansart, N. Catusse, H. Cambazard, Exact algorithms for the order picking problem, Computers & Operations Research 100 (2018) 117–127. doi:https://doi.org/10.1016/j.cor.2018.07.002
-
[5]
P. Revenant, H. Cambazard, N. Catusse, A note about a transition of ratliff and rosenthal’s order picking algorithm for rectangular warehouses,
-
[6]
N. Christofides, Graph theory: An algorithmic approach (Computer sci- ence and applied mathematics), Academic Press, Inc., 1975
work page 1975
-
[7]
H. Cambazard, N. Catusse, Fixed-parameter algorithms for recti- linear steiner tree and rectilinear traveling salesman problem in the plane, European Journal of Operational Research 270 (2018) 419–429. doi:https://doi.org/10.1016/j.ejor.2018.03.042. 8
-
[2024]
URL: https://arxiv.org/abs/2405.15464. arXiv:2405.15464
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.