{"id":"283a6c8e-dbcb-4a89-a3e2-8e8efbc37148","arxiv_id":"2501.14123","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Optimal picker routes in rectangular warehouses never require double traversal of a subaisle to connect horizontal travel, for any number of cross-aisles.","lead":"This paper proves that in rectangular warehouses with any number of cross-aisles, an optimal picking route never needs to traverse an entire subaisle twice just to connect two cross-aisles. This simplifies the structure of optimal routes and could make the dynamic-programming algorithms used for order picking faster.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The reduction step in Section 3 is not rigorously justified: no well-defined potential is given, and Case 0.2's claim that the transformation 'immediately reduces' the count of connecting double edges is unsupported when the adjacent aisle has partial vertical configurations.","rationale":"The reader's verdict of CONDITIONAL is reasonable: the central claim is plausible and the proof strategy is natural, but the written reduction argument has genuine gaps. However, the specific mechanism identified by the reader — that adding a single vertical edge to an empty subaisle creates odd-degree intermediate vertices — does not appear to land. Adding a vertical path through intermediate cross-aisle vertices adds exactly two incident edges at each intermediate vertex, preserving even degree; at the endpoints the horizontal edge removals and additions compensate. The more serious gap is the unsupported assertion in Case 0.2 about 'immediately reduces the number of double edges.' If the adjacent aisle has a partial single-edge configuration, the transformation can create a shorter connecting double edge rather than eliminating connecting double edges entirely. The paper's potential function, 'total number of subaisles involved in connecting double edges,' is never formally defined, and the proof does not verify that this quantity strictly decreases in every case, including the shift case and the boundary case at the first aisle. A concrete enumeration of local configurations would settle whether the reduction step is valid; if it is, the theorem is likely true and the proof only needs more detail. If not, the theorem may be false. Therefore the verdict stays CONDITIONAL, with the condition being a rigorous demonstration of the reduction invariant.","tokens_in":51,"tokens_out":22899,"duration_ms":250353,"concrete_test":"Enumerate all possible local configurations of a tour subgraph around a connecting double edge (a_i, b_i)_2 in a small warehouse (e.g., m = 2 aisles, n = 3 cross-aisles): all six vertical configurations in each subaisle of aisle i-1 over the span, and all horizontal configurations at the cross-aisle vertices in that span. For each configuration, apply the Section 3 transformation exactly as written and compute (a) the degree parity of every affected vertex and (b) the measure 'total number of subaisles involved in connecting double edges' before and after. If any configuration yields an odd-degree vertex, or yields a new connecting double edge with equal or larger measure that does not move strictly left, the reduction step fails as stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 1 is proved by a local transformation T -> T' that is asserted to reduce 'the total number of subaisles involved in connecting double edges,' but this measure is never formally defined and no invariant is stated. The only support for the reduction in Case 0.2 is 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.' This is not evident. Suppose aisle i-1 contains a single edge over a proper subrange of (a_{i-1}, b_{i-1}) and a different configuration over the remainder. Adding the full single edge (a_{i-1}, b_{i-1}) then produces a double edge on that subrange. If horizontal edges are incident at both ends of that subrange, the new double edge is connecting, so the number of connecting double edges does not immediately drop; only the span length may shrink. The later case analysis assumes that when (a_{i-1}, b_{i-1})_1 is absent, no new full connecting double edge appears, but partial configurations are not handled explicitly. The termination argument also relies on an unstated mirroring step for the first aisle. Without a precise potential and a proof that the transformation strictly decreases it in every branch (including the shift case), the iterative elimination is not fully established. This is the load-bearing step for the central claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":4917,"tokens_out":11954,"duration_ms":96015,"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":[{"comment":"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":"Section 3, transformation definition and condition (iii)"},{"comment":"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":"Section 3, Case 0.2"},{"comment":"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.","section":"Section 3, termination argument"}],"minor_comments":[{"comment":"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":"Introduction"},{"comment":"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.","section":"Section 2, definitions"},{"comment":"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":"Figure 6"},{"comment":"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.","section":"Section 1"}],"recommendation":"major_revision","confidential_remarks":"The central claim is plausible and relevant to the picker-routing literature, but the proof of Theorem 1 is not yet convincing. The parity-preservation gap is concrete: a simple degree count at the endpoints of the double edge shows that the stated transformation can change degree parity when right-incident horizontal edges are present. This is not a matter of exposition; it is a load-bearing error in the proof. The authors should be asked to provide a complete, formal proof with an explicit potential function and a full case analysis that includes right-incident edges. I would not recommend rejection, because the structural result may well be true and worth publishing, but the current manuscript does not establish it."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The claimed result—that a minimum tour subgraph in a parallel-aisle warehouse never needs a 'connecting double edge'—is a clean refinement of the Ratliff–Rosenthal and Revenant results, and if it holds it would simplify the state space for multi-block picker routing DP. The paper is honest about prior work and the case analysis is organized, and the idea of shifting double edges leftward is natural.\n\nThe problem is the proof. The transformation T→T' as defined does not preserve even degrees at the endpoints. Take state (0,1): at vertex b_i you remove the two edges of the double edge plus one horizontal edge, and you add nothing; at a_i you remove two and add one. That is a net odd change at both endpoints, so T' is not Eulerian. The paper's condition (iii) claims each altered vertex gets 'removes two, adds two, or unchanged,' but that isn't true for the endpoints in the states where only one horizontal edge is incident. The stress-test note is right that Case 0.2 is under-specified: 'immediately reduces' is doing a lot of work, and the termination argument never gives a well-defined measure that strictly decreases.\n\nThe theorem might still be true—I don't see a counterexample, and the shifting idea is natural—but the written proof does not establish it. This needs a careful rewrite: a potential function that counts something like the leftmost connecting double edge and its span, and a degree-parity check that accounts for all remaining incident edges at each endpoint, possibly by shifting auxiliary edges as well.\n\nWho is this for? Researchers in warehouse logistics and the small community working on exact picker-routing algorithms. They would care about the result if it is real, but they should not cite it yet.\n\nMy recommendation: send it to peer review rather than desk-reject—the result is important enough and the gap is likely repairable—but the referee should demand a rigorous rewrite of Section 3 before acceptance.","headline":"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.","tokens_in":5459,"tokens_out":5833,"would_cite":false,"duration_ms":47375,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90B06","90C27","90C39"],"pacs":[],"model":"deepseek-v4-flash","headline":"In rectangular warehouses with any number of cross-aisles, some shortest picker tour never uses a double traversal of a subaisle as a connector.","keywords":["order picking","picker routing","tour subgraph","Eulerian graph","connecting double edge","warehouse","dynamic programming","rectilinear traveling salesman problem"],"falsifier":"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.","tokens_in":4468,"feed_emoji":"🏭","tokens_out":7994,"duration_ms":63497,"temperature":0.7,"pith_summary":"The paper asks whether optimal picker routes in rectangular parallel-aisle warehouses ever need to traverse a subaisle twice merely to connect horizontal cross-aisle travel. It answers no: even when double traversals are required to collect items inside a subaisle, a shortest tour can always be chosen that avoids them as connectors, regardless of how many cross-aisles the warehouse has. This narrows the route structures that exact algorithms must consider, since the dynamic-programming methods for this problem currently allow double-edge configurations that connect horizontal travel. The simplification carries over to a related rectilinear TSP algorithm that solves the traveling salesman problem with axis-aligned movement on the same kind of graph.","feed_headline":"No optimal route uses a double aisle traversal as connector","feed_subtitle":"In warehouses of any size, a shortest picking tour never walks a subaisle twice just to link cross-aisles.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"It establishes the Eulerian tour-subgraph characterization (Theorem A) that all later arguments use as the definition of a valid route.","marker":"[1]"},{"why":"It extends the dynamic programming approach to three cross-aisles, one of the algorithms whose configuration space the result simplifies.","marker":"[3]"},{"why":"It generalizes exact picker-routing algorithms to any number of cross-aisles and supplies the algorithmic context that the simplified structure improves.","marker":"[4]"},{"why":"It provides the examples showing double traversals are required for optimal routes when there are more than two cross-aisles, motivating the distinction between connecting and non-connecting double edges.","marker":"[5]"},{"why":"It supplies the graph-theoretic foundation for Eulerian tours that underlies Theorem A.","marker":"[6]"},{"why":"It is the related rectilinear TSP algorithm whose horizontal and vertical edge cases the paper's result directly simplifies.","marker":"[7]"}],"fun_headline_variants":["No optimal route needs a double aisle traversal connector","Double aisle traversals never needed to connect cross-aisles","Shortest picking tours avoid double-traversal connectors","Optimal routes omit double subaisle traversals for connections","Connector double-traversals eliminated in optimal picker routes"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["No optimal route needs a double aisle traversal connector","Double aisle traversals never needed to connect cross-aisles","Shortest picking tours avoid double-traversal connectors","Optimal routes omit double subaisle traversals for connections","Connector double-traversals eliminated in optimal picker routes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001203,"raw_usage":{"total_tokens":4892,"prompt_tokens":814,"completion_tokens":4078,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":430,"completion_tokens_details":{"reasoning_tokens":3998}},"tokens_in":430,"tokens_out":4078,"duration_ms":25444,"temperature":1.0,"reasoning_tokens":3998,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T15:22:08.501610+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It establishes the Eulerian tour-subgraph characterization (Theorem A) that all later arguments use as the definition of a valid route."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It extends the dynamic programming approach to three cross-aisles, one of the algorithms whose configuration space the result simplifies."},{"cited_title":"Pansart, N","cited_arxiv_id":null,"evidence_quote":"It generalizes exact picker-routing algorithms to any number of cross-aisles and supplies the algorithmic context that the simplified structure improves."},{"cited_title":"Revenant, H","cited_arxiv_id":null,"evidence_quote":"It provides the examples showing double traversals are required for optimal routes when there are more than two cross-aisles, motivating the distinction between connecting and non-connecting double edges."},{"cited_title":"Christofides, Graph theory: An algorithmic approach (Computer sci- ence and applied mathematics), Academic Press, Inc., 1975","cited_arxiv_id":null,"evidence_quote":"It supplies the graph-theoretic foundation for Eulerian tours that underlies Theorem A."},{"cited_title":"Cambazard, N","cited_arxiv_id":null,"evidence_quote":"It is the related rectilinear TSP algorithm whose horizontal and vertical edge cases the paper's result directly simplifies."}],"review_version":1}