{"id":"12ed7c89-5db7-460d-a137-db4a61e0a8be","arxiv_id":"2611.16357","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"The paper introduces and solves the optimal seat movement problem for modular buses using a colored generalized sliding-tile puzzle formulation and a boundary-sequence dynamic programming algorithm.","lead":"This paper models the physical reconfiguration of movable seats inside coupled modular bus units as a colored generalized sliding-tile puzzle. It develops an exact dynamic programming algorithm (BSDP) that decomposes the problem at module boundaries and achieves substantial speedups over a standard MILP solver on small instances and better solution quality on larger ones.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek/deepseek-v4-flash","headline":"BSDP's exactness proof for fixed-T SoC minimization relies on the assumption that the boundary language B_i^T can be represented exactly via a DFA and weighted DAG, but the DFA pruning condition (66) uses a necessary condition (remaining steps ≥ remaining required transfers) that is not…","rationale":"The reader's weakest_assumption focuses on the decoupling of seat assignment from movement optimization, which is a limitation acknowledged by the authors and is not a threat to the internal correctness of the algorithm. The more load-bearing concern is about the exactness of the compressed boundary representation used in BSDP. The paper claims that the DFA and weighted-DAG compression preserve feasibility and optimal cost exactly (Theorem 2). However, the DFA pruning condition (66) is a necessary condition for cut balance, not a sufficient condition for local physical realizability. The weighted-DAG merging (80) merges nodes with identical continuation cost functions, but the continuation cost function is defined only over the set of suffixes that survive DFA pruning. If the DFA prunes a suffix that is actually realizable by the module, then two nodes that have identical continuation costs over the pruned set might have different costs over that suffix, and merging them could lose the optimal schedule. The paper does not address this gap. This is a concrete technical concern about the exactness proof, not a limitation acknowledged by the authors. The concrete test would settle whether this gap actually leads to suboptimality in practice. The verdict should remain CONDITIONAL because the authors should address this concern, but the paper's contributions are still valuable even if the compressed representation is not exact (it could still be a heuristic).","tokens_in":42200,"tokens_out":903,"duration_ms":10554,"concrete_test":"Construct a small counterexample (e.g., N=2, m=2, T=4) where the DFA pruning condition (66) is satisfied for a prefix but no local schedule exists for that prefix in one module. Then check whether the weighted-DAG merging (80) would merge two nodes that have identical continuation costs over the pruned suffix set but different costs over a suffix that is feasible in the full boundary language. If such a case exists, the compressed representation is not exact, contradicting Theorem 2. Alternatively, prove that the DFA pruning condition is sufficient for local realizability for the specific track graph and movement rules, or prove that the weighted-DAG merging is exact despite the pruned suffix set.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central exactness claim (Theorem 2) depends on the claim that the compressed boundary representation preserves feasibility and optimal cost. The DFA in Section 6.5 uses condition (66) to prune prefixes: a prefix with cumulative transfer vector z' is pruned if the remaining steps cannot satisfy the required net transfers. This condition is necessary but not sufficient for local physical realizability inside a module. The weighted-DAG merging (80) then merges nodes with identical continuation cost functions over all remaining suffixes. However, the DFA has already removed some suffixes from consideration (those that would violate the necessary condition). The continuation cost function is therefore defined only over the subset of suffixes that survive the DFA pruning. Two nodes that have identical continuation costs over this subset might have different continuation costs over a suffix that was pruned by the DFA but would be feasible in the full boundary language. If such a suffix is actually realizable by the module (i.e., there exists a local schedule consistent with that suffix), then the merged representation could incorrectly discard it, potentially losing the optimal schedule. The paper does not prove that the DFA pruning condition is sufficient for local realizability, nor that the weighted-DAG merging is exact given the pruned suffix set. This gap threatens the exactness proof for the compressed representation, and consequently the optimality guarantee of BSDP.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek/deepseek-v4-flash","summary":"The paper introduces and solves the optimal seat movement problem for modular bus units, where movable seats slide along tracks to reconfigure before decoupling. It models the problem as a colored generalized sliding-tile puzzle (CGSP) on the physical track graph, capturing simultaneous movements, seat indistinguishability within destination groups, and vertex, edge, and corner-following conflicts. The objective is lexicographic: minimize makespan first, then sum of costs (SoC). The authors develop an exact time-expanded MILP formulation and a Boundary-Sequence Dynamic Programming (BSDP) algorithm that decomposes the problem at single-edge module interfaces, using compressed boundary-crossing sequences. BSDP is proven exact for fixed makespan. Experiments on 2-7 module benchmarks show BSDP achieves speedups over Gurobi on small instances and better SoC improvement on larger instances within a time budget.","tokens_in":42621,"tokens_out":2156,"duration_ms":16406,"significance":"The paper addresses a novel and practically motivated problem at the intersection of modular transit operations and multi-agent path finding. The modeling as a CGSP with lexicographic objective is appropriate. The BSDP algorithm is a clever decomposition that exploits the chain topology of coupled modules. The experimental results demonstrate clear computational advantages over a generic MILP solver. The paper is well-structured and provides rigorous definitions and proofs. The work has potential to inform real modular bus operations by providing a method to compute optimal seat reconfiguration schedules.","major_comments":[{"comment":"The exactness proof of BSDP (Theorem 2) relies on the claim that the compressed boundary representation (DFA + weighted-DAG merging) preserves feasibility and optimal cost. The DFA pruning condition (66) is a necessary condition for cut balance, but the paper does not prove that it is sufficient for local physical realizability inside a module. The weighted-DAG merging (80) merges nodes with identical continuation cost functions over all remaining suffixes. However, the continuation cost function is defined only over suffixes that survive the DFA pruning. Two nodes that have identical continuation costs over this subset might have different continuation costs over a suffix that was pruned by the DFA but would be feasible in the full boundary language. If such a suffix is actually realizable by the module (i.e., there exists a local schedule consistent with that suffix), then the merged representation could incorrectly discard it, potentially losing the optimal schedule. The paper does not prove that the DFA pruning condition is sufficient for local realizability, nor that the weighted-DAG merging is exact given the pruned suffix set. This gap threatens the exactness proof for the compressed representation, and consequently the optimality guarantee of BSDP. The authors should either provide a proof that the pruning condition is sufficient for local realizability (or that any suffix satisfying the necessary condition can be extended to a full feasible schedule), or clarify that the compression is exact only under an additional assumption that is satisfied by the problem structure. Without this, the claim of exactness for BSDP is not fully justified.","section":"§6.5, Eq. (66) and surrounding text","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The weighted-DAG merging criterion (80) merges nodes with identical continuation cost functions over all remaining suffixes. However, the continuation cost function is defined only over suffixes that survive the DFA pruning. Two nodes that have identical continuation costs over this subset might have different continuation costs over a suffix that was pruned by the DFA but would be feasible in the full boundary language. If such a suffix is actually realizable by the module (i.e., there exists a local schedule consistent with that suffix), then the merged representation could incorrectly discard it, potentially losing the optimal schedule. The paper does not prove that the DFA pruning condition is sufficient for local realizability, nor that the weighted-DAG merging is exact given the pruned suffix set. This gap threatens the exactness proof for the compressed representation, and consequently the optimality guarantee of BSDP.","section":"§6.5, Eq. (80) and surrounding text","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The runtime comparison for 3-module instances shows that Gurobi times out on 6% of instances (3 out of 50). The mean runtime for Gurobi is reported as 300.503s, which includes the 1800s timeout runs. This inflates the mean and the speedup calculation. The authors should report the mean runtime excluding timeouts, or use a different aggregation (e.g., median) to give a fairer comparison. The speedup of 6.30x is based on the inflated mean; the actual speedup on instances solved by both methods may be lower. The authors should clarify this and provide statistics that are robust to timeouts.","section":"§7.2, Table 3 and Figure 9","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The fixed-horizon experiments for 4-7 modules use a 300s time limit and start from identical greedy schedules. The claim that BSDP 'obtains lower final SoC than Gurobi on 197 of 200 instances' is clear. However, the comparison is not a direct test of the lexicographic optimization (makespan + SoC) because the horizon is fixed and not necessarily optimal. The paper acknowledges this (line [b669]), but the title and abstract emphasize 'optimal seat movement strategies', which could be misinterpreted. The authors should be more explicit in the abstract and introduction that the larger-scale results are for fixed-horizon improvement, not full lexicographic optimality. The current phrasing 'BSDP obtains lower final SoC than Gurobi' is accurate but could be misleading without the context that the makespan is fixed and not necessarily optimal.","section":"§7.3, Table 4","authors_acknowledge":"These results establish an advantage in fixed-horizon improvement, rather than a claim that the larger instances have been solved to lexicographic optimality.","authors_acknowledge_p":0.84},{"comment":"The sensitivity analysis for module width m is informative, but the number of instances per setting is only 50, and the comparison is only for 2-3 modules. The authors should discuss whether the trends observed (e.g., larger speedup for narrower modules) are statistically significant. Additionally, the m=4 case for 2 modules shows a modest speedup of 1.52x, which is much smaller than the m=3 case. The authors should provide some intuition for why the advantage diminishes for wider modules.","section":"§7.4, Figure 11 and Table 5","authors_acknowledge":null,"authors_acknowledge_p":null}],"minor_comments":[{"comment":"The sentence 'This paper therefore introduces and solves the optimal MB seat movement problem among coupled modular bus units.' appears twice (once at the end of paragraph 2 and once at the beginning of paragraph 3). Please remove the duplicate.","section":"§1, paragraph 2","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The state matrix definition uses notation X[v] for vertex v, but later the matrix is indexed as X[r,j]. This is consistent, but it would be helpful to explicitly state that v = (r,j) to avoid confusion.","section":"§4.2, Definition 1","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The MILP formulation includes constraints (30) and (31) for flow conservation. It might be helpful to note that these constraints implicitly enforce that each seat selects exactly one action per time step, which is already stated in the text.","section":"§5, Eq. (27)-(33)","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The definition of d_i^c uses the prefix set P_i. It might be clearer to explicitly state that d_i^c is the net number of color-c seats that must cross boundary i from left to right.","section":"§6.2, Eq. (47)","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The pruning condition uses the L1 norm of the difference between required and current net transfer. The authors should note that this condition is necessary but not sufficient for local realizability, which is acknowledged in the text but could be emphasized more.","section":"§6.5, Eq. (66)","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The data generation procedure uses a target-aware color assignment to minimize the sum of assignment distances. This is a reasonable heuristic, but it may introduce a bias towards easier instances. The authors should discuss whether this affects the generality of the results.","section":"§7.1, Eq. (93)-(94)","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The table reports 'CV' (coefficient of variation) for runtime. It would be helpful to define CV in the caption or text.","section":"§7.2, Table 3","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The convergence plots for three selected instances are informative, but the selection criteria are not stated. The authors should explain why these particular instances were chosen (e.g., representative, best, worst case).","section":"§7.3, Figure 10","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The sentence 'The additional experiments clarify the sources and scope of these gains.' could be more specific about which experiments (ablation, sensitivity) are being referred to.","section":"§8, paragraph 3","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The detailed results tables are extensive and useful. However, the 95% confidence intervals for runtime are reported in brackets. It would be helpful to note that these are computed over 10 repeated runs.","section":"Appendix A","authors_acknowledge":null,"authors_acknowledge_p":null}],"recommendation":"major_revision"},"author_rebuttal":null,"desk_editor":{"model":"deepseek/deepseek-v4-flash","letter":"Colleague,\n\nThis paper does something genuinely new: it formulates the optimal seat movement problem for modular buses as a colored generalized sliding-tile puzzle and develops a dedicated dynamic programming algorithm (BSDP) that exploits the chain topology. The problem is real—existing modular transit models abstract away the physical reconfiguration—and the authors are the first to optimize it. The BSDP algorithm is clever: it decomposes the problem at single-edge module interfaces, uses a DFA to prune boundary schedules, and compresses the search space with weighted-DAG merging. The exactness proof for fixed makespan is sound, and the experimental results are credible: on 2-3 module instances BSDP matches Gurobi on optimality while being 3-6x faster; on 4-7 module instances with a 300s budget it consistently finds better feasible schedules than Gurobi starting from the same greedy initial solution. The ablation study convincingly shows that the DFA compression is the main driver of efficiency.\n\nThat said, the paper has real limitations. The most important is that the seat-to-module assignment is taken as given—the paper explicitly decouples assignment from movement optimization. In practice these are interdependent, and the paper acknowledges this as future work, but it means the current contribution is to a subproblem whose boundaries are set by an external decision. Second, the larger instances (4-7 modules) are not solved to optimality; the comparison is on improvement from a common greedy start within a fixed time budget. The authors are transparent about this, but it limits the strength of the claims for larger N. Third, no code or data is provided, which is a reproducibility concern for a paper that ships an algorithm. The stress-test note about the DFA pruning condition being necessary but not sufficient for local realizability is a genuine theoretical gap: the paper does not prove that the compressed boundary representation preserves all feasible schedules, only that it preserves feasibility and optimal cost under the pruning rule. The authors assert this in Theorem 2 but the proof relies on the DFA and weighted-DAG merging being exact, and the pruning condition (66) is indeed only necessary. This is a soft spot in the theoretical foundation, though in practice the algorithm works well.\n\nWho is this for? Researchers in modular transit operations and, more broadly, anyone working on multi-agent path finding on chain-like topologies with interchangeable agents. It deserves a serious referee—the work is technically competent and the problem is well-motivated. I would accept a peer review invitation for this paper.\n\nRecommendation: Accept with major revision. The authors should provide code and data, clarify the exactness claim for the compressed representation (address the DFA pruning gap), and discuss the practical implications of the fixed-assignment assumption more thoroughly.","headline":"A technically solid, niche contribution that formulates and optimally solves a previously unoptimized subproblem in modular transit. The BSDP algorithm is a genuine advance for this specific problem, but the impact is bounded by the narrow scope and the lack of open code/data.","tokens_in":43106,"tokens_out":678,"duration_ms":20353},"pith_extraction":null,"created_at":"2026-11-13T06:52:08.338012+00:00","model_set":{"reader":"deepseek/deepseek-v4-flash"},"pipeline_version":"pith-pipeline@v1.4.1-daily-deepseek-or-medium","input_kind":null,"input_chars":null,"input_total_chars":null,"passes_missing":null,"published_standing":null,"published_confidence":null,"objection_audit":null,"run_record":null,"basis":{"kind":"not_recorded","source":null,"chars_given":null,"chars_total":null},"receipt":null,"falsifier":null,"supporting_citations":[],"lane_accuracy":{"status":"not yet measured","lane":{"model":"deepseek/deepseek-v4-flash","input_kind":null},"url":"https://pith.science/accuracy"},"review_version":1}