{"id":"d63e90c7-9f5e-4616-9d12-92848257fd5d","arxiv_id":"2505.07776","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Two heuristic accelerations, data-driven clique filtering and shareability-graph partitioning, speed up the Alonso-Mora 2017 high-capacity ridepooling algorithm on Manhattan data.","lead":"This paper proposes two speed-up tricks for an existing high-capacity ridepooling algorithm: one uses machine learning to skip unlikely trips, the other splits the problem into smaller parts. The authors test them on one morning of New York taxi data and report faster decisions without hurting service quality.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Claimed speed-up may be an artifact of training/selecting the feasibility predictor on the evaluation day; no held-out split or threshold procedure is reported.","rationale":"I agree with the reader's weakest_assumption: the absence of a stated train/test split and threshold-selection procedure is the most load-bearing concern. The data-driven feasibility predictor is the novel learned component, and the central claim depends on its ability to skip cliques on unseen decision windows. Without a held-out split, the reported improvement—especially the reduction in empty travel time—could reflect memorization or tuning on the evaluation data rather than a generalizable acceleration. The partition method has a separate potential issue: partitioning the shareability graph into disjoint subgraphs may exclude feasible trips whose requests or vehicles straddle subgraphs, so the unified ILP optimizes over a restricted trip set. However, that issue is less central here because the paper's headline claim covers both methods, and the data-driven method is the one with a tunable learned component and the one identified by the reader. The proposed temporal-holdout test directly settles whether the learned predictor generalizes; if it does not, the 'proven' improvement in Section IV is unsupported for at least one of the two accelerations. Thus the conditional verdict is appropriate, and no change is needed.","tokens_in":4508,"tokens_out":5836,"duration_ms":65107,"concrete_test":"Run a strict temporal holdout on TLC data: train the Structure2Vec feasibility predictor and select its threshold using only decision windows before May 15 (or, at minimum, the first 30 minutes of the test morning), and evaluate only on the remaining May 15 windows that were not used for any model or threshold selection. Report passengers served, average occupancy, and empty travel time against the same 30-second-timeout baseline, with standard errors, and also report predictor precision/recall with a threshold sweep on the validation window. If the empty-travel reduction does not persist out-of-sample or is not statistically significant, the claimed data-driven acceleration is not established.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim in Section IV that both accelerations 'substantially improve baseline performance' depends most heavily on the data-driven feasibility predictor generalizing to decision windows it has not been tuned on. Section II (Data-driven ILP construction) states that the predictor is learned 'using prior data' and that the full VRP is solved only when the predicted feasibility exceeds 'a given threshold,' but it does not specify which time windows supplied the training data, how the threshold was selected, whether a validation split was used, or the predictor's precision/recall. Section III evaluates on a single morning peak (7:00-9:00 AM, May 15, 2024) and reports only figures, not numerical results or train/test separation. If the Structure2Vec model and the threshold were fit on the same May 15 data that produces Fig. 2, then the reported match in passengers served and occupancy, together with reduced empty travel time, is exactly what would be expected from a model that has memorized the evaluation day's feasible cliques. The partition-based acceleration may be unaffected, but the two-method claim weakens substantially if the learned component does not generalize out-of-sample.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two accelerations for the high-capacity ridepooling assignment algorithm of Alonso-Mora et al. (2017): (i) a data-driven feasibility predictor based on Structure2Vec that skips VRP evaluations for predicted-infeasible cliques, and (ii) a shareability-graph partitioning scheme using multilevel k-way graph partition with parallel trip generation. The methods are evaluated against the original algorithm on a one-day NYC TLC morning peak (7:00–9:00, May 15, 2024) under a 30-second decision-window timeout. The paper claims both accelerations substantially improve baseline performance, reducing empty travel time while maintaining passengers served and occupancy.","tokens_in":4730,"tokens_out":4719,"duration_ms":47227,"significance":"If the performance claims are substantiated, the paper addresses a real bottleneck: the VRP-per-clique enumeration in the Alonso-Mora pipeline is the main computational barrier to real-time high-capacity ridepooling. The two proposed mechanisms—learned feasibility screening and partitioning-with-parallelism—are sensible and complementary, and the paper correctly identifies that learned screening should be compared against random clique dropping. The manuscript is short and the ideas are plausible; the central weakness is that the evaluation, as reported, is insufficient to support the headline claim. No machine-checked proofs, code, or dataset splits are supplied, and the word 'prove' in the abstract overstates what the single-day empirical study can establish.","major_comments":[{"comment":"The learned feasibility predictor is load-bearing for the first claimed acceleration, but the manuscript does not specify which time windows supplied training data, how clique feasibility labels were generated, how the prediction threshold was selected, whether a validation split was used, or the predictor’s precision/recall. Since Section III evaluates only on the morning peak of May 15, 2024, nothing rules out the possibility that the predictor and threshold were tuned on the same day’s data; in that case the reported speed-up would reflect memorization rather than out-of-sample generalization. The authors should report a clear train/validation/test protocol (e.g., train on preceding days, validate on another day, test on May 15) and give quantitative predictor quality on held-out windows.","section":"II (Data-driven ILP construction) and III"},{"comment":"No numerical values are reported in the text: there are no means, standard deviations, numbers of runs, or statistical tests, and Figures 2 and 3 are referenced without any numbers or axis descriptions. The single evaluation window (7:00–9:00 on one day) is also the only scenario, as the authors acknowledge in Section IV where broader demand scenarios are left to future work. The word 'prove' in the abstract is therefore unsupported; the paper should either supply a rigorous proof for the acceleration claims or replace 'prove' with 'demonstrate' and back it with numerical tables, confidence intervals, and additional days/seeds.","section":"III (Numerical case study)"},{"comment":"Partitioning the shareability graph into disjoint subgraphs and enumerating cliques within each subgraph omits candidate trips whose cliques span multiple subgraphs, so the set of ILP columns is changed relative to the original algorithm. The paper does not analyze the effect on the global ILP’s feasible set or solution optimality, nor does it report the multilevel k-way parameters (number of partitions, balance tolerance, edge-cut) or the modularity-partition baseline's settings. Because the claimed improvement in Fig. 3 could partly come from changing the optimization problem rather than from acceleration per se, the experimental setup needs to report these settings and ideally bound the loss from omitted columns.","section":"II (Shareability graph partition)"},{"comment":"For the learned screening comparison to be meaningful, the random-drop baseline must be matched in computational cost or expected skipped cliques; the manuscript does not state how the drop rate in Fig. 2 is chosen or how the accrued VRP-solving time compares between methods. Without such matching, a lower empty-travel-time result could simply reflect a different number of cliques evaluated rather than an improvement in prediction quality.","section":"III (Data-driven ILP construction)"}],"minor_comments":[{"comment":"The phrase 'using prior data' is vague; specify the exact dates and preprocessing used for training the Structure2Vec model.","section":"II"},{"comment":"'ca. 26,000 trips' should be an exact count with the filtering criteria (e.g., trip distance, time windows) stated.","section":"III"},{"comment":"Define 'drop rate' and 'occupancy' precisely; state whether occupancy is averaged over vehicles or over trips.","section":"III"},{"comment":"The statement in Section IV that both methods 'substantially improve baseline performance' is not directly supported by Fig. 3, which appears to compare partitioning variants rather than the baseline; add the baseline curve to the figure.","section":"III"},{"comment":"There is a typo in Section II: 'vehicless' should be 'vehicles'.","section":"II"},{"comment":"The paper would benefit from a reproducibility statement or from making the code and the trained predictor available.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is currently a very short paper with the core results hidden in figures; a detailed experimental appendix is necessary for the claims to be assessable. In my view the central ideas are not flawed in principle, but the evaluation needs a proper hold-out protocol, numerical results, and an explicit comparison of computational budgets. If the authors cannot provide these, the paper should not be accepted. I would not reject at this stage because the issues are fixable within the scope of a revision, but the revision must be substantial."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two accelerations for the Alonso-Mora high-capacity ridepooling algorithm: a data-driven feasibility filter using Structure2Vec, and multilevel k-way partitioning of the shareability graph. The combination is new in this application; the building blocks are known. The partition idea is clean and likely helps independent of the learning module. That part of the paper reads well. The feasibility filter is a reasonable direction, but its evaluation is not.\n\nThe experimental section is the soft spot, and it is load-bearing. No numerical results appear anywhere—only Figures 2 and 3, which are absent from the arXiv text. No error bars, no standard deviations, no number of runs. The abstract says the improvement is 'proven' by a Manhattan case study, but the case study is one morning peak (May 15, 2024, 7–9am). You cannot prove an algorithmic improvement with a single day's data and no statistics. The reader's stress-test concern is on point: Section II says the predictor is learned 'using prior data' and skips VRPs when predicted feasibility is below 'a given threshold,' but does not say what prior data, how the threshold was set, or whether the evaluation day was held out. If the Structure2Vec model and threshold were tuned on the same day that generates Fig. 2, the reported match to baseline occupancy while reducing empty travel is exactly what memorization would look like. The partition-based acceleration arguably does not depend on this, but the paper presents the two methods as a bundled claim. I'd want a held-out validation, precision/recall for the predictor, and the threshold selection procedure.\n\nCitation pattern is fine; the Alonso-Mora lineage is clear. Self-citation is not an issue here. The writing is compact, possibly too compact—Section III is three paragraphs.\n\nBottom line: this is a plausible engineering contribution from a group that knows the area. The correct verdict is conditional: ask for the missing artifacts—numerical tables, error bars, train/test split, threshold details, and ideally code or a public dataset link. That is a serious referee's job, so I would not desk-reject. Send it to a knowledgeable reviewer with instructions to ask for those specifics. I would not cite it yet.","headline":"Useful engineering accelerations for Alonso-Mora ridepooling, but the paper hides the evidence: no numbers, no train/test split, and the 'proven' claim is unsupported.","tokens_in":5221,"tokens_out":1508,"would_cite":false,"duration_ms":14993,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90B06","90C11"],"pacs":[],"model":"deepseek-v4-flash","headline":"A learned feasibility filter and shareability-graph partitioning make high-capacity robo-taxi ridepooling fast enough for 30-second real-time decisions, cutting empty travel time in a Manhattan test.","keywords":["autonomous mobility-on-demand","ridepooling","fleet coordination","mixed-integer linear programming","shareability graph","graph partitioning","data-driven feasibility prediction","real-time optimization"],"falsifier":"On a held-out evaluation day never seen during training or threshold selection, freeze the predictor's threshold and compare its 30-second-budget empty-travel-time against random clique dropping; if the advantage collapses or vanishes, the acceleration is day-specific rather than general.","tokens_in":4338,"feed_emoji":"🚕","tokens_out":4983,"duration_ms":48440,"temperature":0.7,"pith_summary":"This paper tries to establish that two algorithmic accelerations make high-capacity ridepooling--where vehicles carry several passengers per trip--fast enough for real-time robo-taxi operations. The first acceleration learns to predict which candidate trip groupings are feasible and skips expensive route-check computations for unlikely ones. The second splits the graph of possible trips into balanced subgraphs that can be explored in parallel. Tested on roughly 26,000 Manhattan morning-peak trips with a 30-second computation budget, both changes cut empty travel time without reducing passengers served or average occupancy. The result matters because it suggests city-scale pooling can stay centralized and exact enough to be practical.","feed_headline":"Robo-taxi pooling accelerations cut empty travel time in Manhattan test","feed_subtitle":"A learned feasibility filter and graph partitioning fit high-capacity pooling into 30-second decision windows.","key_machinery":"The central object is the shareability graph, whose cliques are candidate trips; each clique triggers a vehicle-routing feasibility and cost check, and the assignment integer program is built from those checks. The paper accelerates that machinery in two ways: a Structure2Vec graph embedding predicts the feasibility of each clique so full vehicle-routing problems run only on likely-feasible candidates, and a multilevel k-way partition splits the shareability graph into balanced, edge-minimal subgraphs whose trip generation runs in parallel. Together they shrink the number of expensive route checks and the size of each subproblem while preserving the original formulation and its optimality guarantees within each window.","core_discovery":"On the paper's own account, the discovery is that the computational bottleneck of the high-capacity ridepooling algorithm of [1] is not the final assignment solve but the construction of the assignment integer program, and that this construction can be accelerated safely. By predicting clique feasibility with a graph embedding and partitioning the shareability graph, the algorithm spends its fixed 30-second budget on the most promising candidate trips and parallelizes trip generation across subgraphs. Measured on Manhattan morning-peak data, the accelerated pipeline improves empty travel time relative to the original algorithm while matching its passengers served and occupancy. The paper calls this a proof, via a real-world case study, of improved real-time performance.","pith_inferences":["Because the paper tests only a two-hour morning peak, an obvious next check is whether the accelerations hold across off-peak hours, weekends, and surge events; the graph-partition benefit would likely persist, while the learned feasibility predictor would be more sensitive to distribution shift.","The data-driven skip layer is a template for any combinatorial pipeline whose bottleneck is repeated feasibility checks inside an optimization loop; parcel delivery and demand-responsive transit have the same trip-clique structure.","The unstated threshold in the feasibility predictor could become an adaptive control knob: lowering it early in a decision window and raising it as the deadline approaches would trade solution quality for speed in a principled way.","The 30-second budget with 1-minute decisions leaves 30 seconds for dispatch, so the reported gains could translate into either better solutions within the same budget or a shorter required budget in denser fleets."],"forward_implications":["The two accelerations make the Alonso-Mora-style assignment pipeline viable inside 1-minute decision cycles, so robo-taxi fleets can pool high-occupancy rides at city scale rather than falling back to single-passenger dispatch.","Operators get a direct lever on sustainability: lower empty travel time at equal service levels implies less deadhead mileage and emissions in dense networks.","Graph partitioning can be reused as a parallelization layer for any shareability-graph-based algorithm, because it splits trip generation into independent subproblems.","The data-driven skip layer can be retrained on different cities or demand patterns, so the portability of the acceleration depends on the embedding's transfer rather than on hand-crafted heuristics.","Within a fixed time budget, the pipeline spends computation on larger, more impactful candidate trips, which suggests the gains will grow as the shareability graph grows."],"supporting_citations":[{"why":"Baseline high-capacity ridepooling algorithm whose ILP-construction bottleneck the paper accelerates.","marker":"[1]"},{"why":"NYC TLC dataset supplying the 26,000-trip Manhattan morning-peak case study.","marker":"[8]"},{"why":"Multilevel k-way graph partitioning used to split the shareability graph into balanced subgraphs.","marker":"[11]"},{"why":"Structure2Vec graph embedding used for the data-driven clique-feasibility predictor.","marker":"[12]"},{"why":"Shareability-network concept that the baseline algorithm uses to prune candidate trips.","marker":"[17]"},{"why":"Modularity-based partitioning compared against multilevel k-way in the partition experiment.","marker":"[5]"}],"fun_headline_variants":["Accelerated ridepooling: Manhattan test cuts empty travel time","Robo-taxi pooling acceleration cuts empty travel in Manhattan","Manhattan ridepooling: acceleration trims empty travel time","30-second ridepooling: accelerated high-capacity in Manhattan","Faster ridepooling: real-world Manhattan test cuts empty miles"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the data-driven feasibility predictor learned from historical trip data generalizes to the evaluation day, including how that day's requests and vehicle positions form shareability cliques; if the predictor was trained or threshold-tuned on the same day's data, the reported speed-up could reflect memorization rather than a reusable acceleration.","fun_headline_variants_meta":{"raw":{"variants":["Accelerated ridepooling: Manhattan test cuts empty travel time","Robo-taxi pooling acceleration cuts empty travel in Manhattan","Manhattan ridepooling: acceleration trims empty travel time","30-second ridepooling: accelerated high-capacity in Manhattan","Faster ridepooling: real-world Manhattan test cuts empty miles"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00066,"raw_usage":{"total_tokens":2942,"prompt_tokens":790,"completion_tokens":2152,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":406,"completion_tokens_details":{"reasoning_tokens":2065}},"tokens_in":406,"tokens_out":2152,"duration_ms":13972,"temperature":1.0,"reasoning_tokens":2065,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:07:37.835609+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a held-out evaluation day never seen during training or threshold selection, freeze the predictor's threshold and compare its 30-second-budget empty-travel-time against random clique dropping; if the advantage collapses or vanishes, the acceleration is day-specific rather than general.","supporting_citations":[{"cited_title":"Tlc trip record data, 2025","cited_arxiv_id":null,"evidence_quote":"NYC TLC dataset supplying the 26,000-trip Manhattan morning-peak case study."},{"cited_title":"Multilevelk-way partitioning scheme for irregular graphs","cited_arxiv_id":null,"evidence_quote":"Multilevel k-way graph partitioning used to split the shareability graph into balanced subgraphs."},{"cited_title":"Learning combinatorial optimization al- gorithms over graphs","cited_arxiv_id":null,"evidence_quote":"Structure2Vec graph embedding used for the data-driven clique-feasibility predictor."},{"cited_title":"Quanti- fying the benefits of vehicle pooling with shareability networks","cited_arxiv_id":null,"evidence_quote":"Shareability-network concept that the baseline algorithm uses to prune candidate trips."},{"cited_title":"Finding community structure in very large networks","cited_arxiv_id":null,"evidence_quote":"Modularity-based partitioning compared against multilevel k-way in the partition experiment."}],"review_version":1}