{"id":"02afe919-eed4-4260-bade-e2f5b60fbe44","arxiv_id":"2501.13819","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"A mixed-integer second-order cone reformulation with cut-and-column generation produces crowding-aware line plans for the full Beijing metro, cutting crowding at modest travel-time cost.","lead":"This paper presents a method for choosing metro lines and frequencies while penalizing crowded trains, using a mixed-integer second-order cone program solved by a cut-and-column generation algorithm. On the Beijing metro network with about 57,000 origin-destination pairs, the method produces plans that reduce crowding with only a small increase in travel time.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 'true optimality gaps' in §6.2 are gaps to a GUROBI benchmark restricted to 15 routes/OD, not to the full problem; the full-network results report no lower bounds, so 'near-system-optimal' is unproven.","rationale":"Good-faith reading: the paper's main contribution is a scalable method for a hard nonconvex-looking problem, with evidence that it finds high-quality solutions. The weakest point in that evidence is the definition of the optimality benchmark. The phrase 'true optimality gaps' is literally false: the benchmark is optimal for a restricted route set. Since Figure 4 shows the objective still improving at 15 routes, the restriction is active. This matters because the abstract and conclusion claim 'near-system-optimal solutions'; if the true gaps are several times larger, the algorithmic contribution is weakened, though not necessarily invalidated. The functional-form assumption flagged by the reader is a legitimate modeling limitation, but it is transparent, explicitly parameterized by γ, and the paper's insights are presented conditionally on that model. The optimality-gap issue is an internal misstatement of evidence, more directly testable. A simple re-benchmarking experiment on the same grid instances would settle it. If the gaps remain small, the paper's claims stand; if not, the authors need to soften the near-optimality claim or add lower bounds on the full network. Since the core reformulation and algorithm are not attacked by this concern, CONDITIONAL (i.e., UNCHANGED from the reader) remains the right verdict: accept subject to corrected benchmarking and reported solution quality on the full network.","tokens_in":22454,"tokens_out":23587,"duration_ms":207012,"concrete_test":"For the 16 grid instances in Table 2, run GUROBI on Formulation (2) with a route set expanded until the per-OD route count no longer improves the objective by more than 0.01%, or use the dual bound from the cut-and-column master problem. Compute the FCTP gap to this true lower bound. If the average gap stays below ~2%, the near-optimality claim survives; if it grows beyond the reported 1.77%, the 'true optimality gaps' claim must be revised. In addition, for the Beijing full-network rows of Table 3, report at least one valid lower bound (e.g., the LP relaxation value of the restricted master with all generated cuts) for each crowding factor, so that solution quality can be assessed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing evidence for the paper's central algorithmic claim — 'near-system-optimal solutions' (Abstract; Contribution 3) — is the statement in Section 6.2 that 'the relative gaps are true optimality gaps' because GUROBI is used as benchmark. This is not correct: the GUROBI benchmark solves Formulation (2) with at most 15 PTN routes per OD pair (Section 6.2, Table 2), i.e., a restricted version of the problem. The optimal value of a restricted minimization problem is an upper bound on the true optimum, so the gap between FCTP and this restricted optimum is not the gap to the true optimum. Figure 4 shows the objective still decreasing between 10 and 15 routes, so 15 routes is not demonstrated to be sufficient for optimality. The reported 1.77% average gap and the 1.8–3.5% range are therefore, at best, lower bounds on the true optimality gaps. For the full Beijing network (Section 6.4, Table 3), no objective values or lower bounds are reported at all; only computational times are given. Thus the claim that the algorithm 'effectively scales to large-scale instances' with near-optimal solutions is not supported by the evidence presented.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies line planning under passenger crowding. It models perceived travel cost as in-vehicle time plus a quadratic-over-linear crowding penalty γ_a x_a^2 / y_ℓ, reformulates the resulting mixed-integer nonlinear program as an MI-SOCP (Formulation 2), and solves it with a cut-and-column generation framework comprising three algorithmic variants and a diving heuristic. Experiments on a 5×5 grid network and on the Beijing metro network (central sub-network and full network) are used to claim near-optimal solutions within short computation times and to derive insights about crowding reduction, travel-time tradeoffs, and the closeness of system-optimal and user-equilibrium routings.","tokens_in":22729,"tokens_out":9743,"duration_ms":86794,"significance":"The mathematical core of the paper is sound: the rotated second-order cone reformulation is valid, Proposition 1's tangent cut follows from convexity of x^2/y on y > 0, and the user-equilibrium evaluation via the convex potential in Section 5 is standard. The Beijing case study is a substantial computational effort involving tens of thousands of OD pairs and hundreds of candidate lines, and the paper gives credit for a practical, scalable algorithmic framework if the optimality claims can be supported. However, the empirical evidence for the central 'near-system-optimal' claim is currently incomplete: the grid benchmarks are restricted to 15 routes per OD pair, and the full-network experiments report no objective values or lower bounds. With additional bounds or appropriately qualified claims, the contribution would be a useful practical method for nonlinear line planning.","major_comments":[{"comment":"The statement 'Since we use the optimal solutions obtained by GUROBI as the benchmark, the relative gaps are true optimality gaps' is not correct. The GUROBI benchmark solves Formulation (2) with at most 15 pre-specified PTN routes per OD pair. Because this is a restricted minimization, its optimal value is an upper bound on the true optimum, and the difference between the FCTP objective and this restricted optimum is only a lower bound on the true optimality gap. Figure 4 shows the objective still decreasing between 10 and 15 routes, so saturation at 15 routes is not established. The reported 1.77% average gap should be described as a gap to a restricted route set, or supplemented with a valid lower bound such as an LP/SOCP relaxation bound or an unrestricted column-generation bound.","section":"Section 6.2, Table 2 and Figure 4"},{"comment":"The full-network scalability experiments report only computational times, iteration counts, and average RMP/PP times; no objective values or lower bounds are given. Consequently, the claims that the algorithm 'effectively scales to large-scale instances' and produces near-system-optimal solutions for the entire Beijing network are not supported by the reported evidence. This is especially consequential because the text states that for crowding factors 0.005 and 0.008 the diving heuristic has difficulty finding good solutions, resulting in solutions with more crowding. Please report objective values and at least one bound, or clearly label the outputs as heuristic without optimality claims.","section":"Section 6.4, Table 3"},{"comment":"The benchmark definition for Insight 2 is ambiguous and should be clarified. As written, the text says the benchmark 'inputs the optimized line plan under crowding effects into Formulation (1) with γ_a set to zero' and then states that each point compares perceived travel costs 'with and without crowding effects under the same line plan.' These two descriptions are difficult to reconcile with the reported direction of the APTT reduction. If the comparison is between a plan optimized with crowding and one optimized without crowding, please state this explicitly and describe how passenger routing is recomputed in each case; if it is truly the same line plan with and without the crowding penalty, the reported APTT reduction needs a different explanation.","section":"Section 6.3, Insight 2 and Figure 8"}],"minor_comments":[{"comment":"Several figure cross-references are missing or appear as 'Figure ??' (e.g., in Section 3 for the CGN example and in Section 6.2 for the route-count experiment). Please fix all cross-references and verify the final PDF rendering.","section":"Throughout"},{"comment":"The abbreviations APTT and ATT are used before they are formally defined; please define them at first use and make the units (minutes or percentages) explicit.","section":"Section 6.3, Insight 2"},{"comment":"The crowding penalty γ_a x_a^2 / y_ℓ is an uncalibrated modeling assumption. The paper should acknowledge explicitly that the quantitative magnitudes of the insights depend on this functional form and on the chosen γ_a values.","section":"Section 3, Eq. (1a)"},{"comment":"The conclusion states an 'average optimality gap ranging from 1.8% to 3.5%', while Section 6.2 reports an average FCTP gap of 1.77% and individual gaps up to about 5%. These numbers should be made consistent and tied to the specific algorithm variants.","section":"Conclusion"},{"comment":"The algorithm parameters Δ1, Δ2, I, and ε are chosen based on preliminary experiments, but no sensitivity analysis or guidance on their selection is given. A brief discussion of robustness to these tuning parameters would strengthen the computational study.","section":"Section 4.4 and 6.1"},{"comment":"The notation R_a, R_p, R_p^a is introduced but is not always used consistently afterward. A compact notation table or a short explanation of the difference between PTN routes and CGN routes would improve readability.","section":"Section 3"}],"recommendation":"major_revision","confidential_remarks":"The main technical concern is the invalid interpretation of the GUROBI benchmark in Section 6.2; this is fixable by adding valid lower bounds or by re-solving small instances with full route sets. The practical algorithmic contribution and the Beijing case study are substantial, and I do not see a load-bearing error in the mathematical reformulation. I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, the modeling and algorithmic core is sound. The quadratic-over-linear crowding penalty is a reasonable convex choice, the MI-SOCP reformulation in Formulation (2) is correct, and Proposition 1's tangent cut is valid because x^2/y is convex for y>0. The cut-and-column integration—cone cuts plus route pricing—is a sensible combination that I have not seen in the line planning literature. The computational study is serious: grid networks and the entire Beijing metro with 534 candidate lines and ~57,000 OD pairs is a genuine stress test, and the diving heuristic yields feasible integral plans.\n\nThe main soft spot is the interpretation of the 'true optimality gaps' in Section 6.2. The GUROBI benchmark solves the same Formulation (2) but with at most 15 PTN routes per OD pair. That is a restricted problem, so its optimal value is an upper bound on the true optimum; the stated 1.77% average gap is therefore a lower bound on the true optimality gap. Figure 4 shows the objective still decreasing at 15 routes, so 15 is not demonstrably sufficient. For the full Beijing network (Section 6.4), no objective values or lower bounds are reported, only runtimes, so the 'near-system-optimal' claim there is not supported. None of this undermines the method itself, but it weakens Contribution 3 as written.\n\nTwo smaller points. The crowding penalty gamma_a x_a^2 / y_l(a) is an assumed functional form, not calibrated from passenger data, and it is used both to optimize and to evaluate line plans. That is acceptable for a methodological paper, but it means the managerial numbers (APTT reductions, UE vs SO gaps) are conditional on that form. Also, no code or data are provided, so replication is harder than it should be for a computational paper with this scale.\n\nOn citation pattern: nothing suspicious; the related work is fairly covered. The paper is for transit planning researchers, especially those working on line planning with passenger routing and large-scale instances. It deserves a serious referee: the issue is reporting, not mathematics. I would recommend a revision that either computes proper lower bounds on the full route set for the smaller instances, or rephrases the gap claims as relative to a restricted benchmark. The central contribution is real.","headline":"Sound MI-SOCP cut-and-column method for line planning with crowding, but the near-optimality claims in the computational study outrun the reported bounds.","tokens_in":23265,"tokens_out":2597,"would_cite":true,"duration_ms":22586,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C11","90B06","90B20","90C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"Crowding-aware line planning can cut metro crowding at modest travel-time cost.","keywords":["line planning","crowding effects","mixed-integer second-order cone programming","cut-and-column generation","column generation","change-and-go network","user equilibrium","Beijing metro"],"falsifier":"Collect stated-preference data on how much extra travel time passengers would accept to avoid a train that is 10% or 50% fuller, and fit a marginal crowding cost as a function of load factor. If that fitted function is not approximately linear in x_a divided by y_l(a) (for example, if discomfort saturates after seating is full), re-solving the Beijing sub-network instance with the fitted curve should change the chosen line frequencies; if it does, the reported crowding-reduction and travel-time trade-off is tied to the quadratic-over-linear assumption.","tokens_in":22217,"feed_emoji":"🚇","tokens_out":9925,"duration_ms":81364,"temperature":0.7,"pith_summary":"This paper seeks to establish that line planning for a metro network can explicitly price passenger crowding, treating discomfort as a penalty that grows with the square of passenger flow on an arc and shrinks with the frequency of the serving line, and that the resulting optimization problem can be solved at full network scale. The authors reformulate the nonlinear objective as a mixed-integer second-order cone program and solve it with a cut-and-column generation scheme that generates passenger routes on the fly and adds tangent cuts for the crowding cones. On the Beijing metro network, with 534 candidate lines and 56,916 origin-destination pairs, the resulting line plans reduce crowding and cut perceived travel time compared with the existing plan while increasing actual travel time by a modest margin. They also show that passenger self-routing under a user-equilibrium condition stays close to the system-optimal routing, so ignoring selfish route choice during optimization loses little.","feed_headline":"Crowding-aware metro plans cut crowding with only slight delay","feed_subtitle":"A cut-and-column algorithm solves crowding-aware line planning for 534 candidate lines and 56,916 OD pairs on Beijing's metro.","key_machinery":"The load-bearing object is the perceived crowding penalty gamma_a $x_a^{2}$ / y_l(a), combined with the rotated second-order cone constraint Theta_a y_l(a) >= gamma_a $x_a^{2}$. The quadratic-over-linear form makes passenger-flow interactions convex, which is what allows the nonlinear line planning model to be recast as a mixed-integer second-order cone program; the cone constraints are then approximated by linear tangent cuts, and passenger routes are priced dynamically as shortest paths in the change-and-go network. This combination lets the algorithm keep the master problem small while still searching the enormous space of possible routes and handling the crowding nonlinearity.","core_discovery":"The paper's central claim is that a quadratic-over-linear crowding term gamma_a $x_a^{2}$ / y_l(a) inserted into the objective of the line planning problem is enough to make crowd-avoiding line plans emerge from a tractable optimization model. On each arc, x_a is the number of passengers using the arc and y_l(a) is the frequency of the line that serves it, so the penalty rises steeply with passenger load and falls as trains arrive more often. The authors show that this term fits into a rotated second-order cone constraint Theta_a y_l(a) >= gamma_a $x_a^{2}$, giving a mixed-integer second-order cone program in which the nonlinearity can be handled by first-order tangent cuts. Their column generation prices passenger routes as shortest paths in the change-and-go network, so the route set does not need to be enumerated. On the 5x5 grid benchmark the best variant of the algorithm reaches an average optimality gap near 1.8% in far less time than a commercial solver, and on the Beijing metro it produces line plans whose perceived travel time beats the real-world plan by 4.6% to 7.5% on the central sub-network while shifting the distribution of crowding downward; the system-optimal and user-equilibrium objective values differ by at most 0.07% on the grid and 0.64% on the Beijing sub-network.","pith_inferences":["Beyond the paper: replacing the quadratic-over-linear penalty with a piecewise-linear crowding curve that saturates at standing capacity or distinguishes seated from standing passengers would directly test whether the reported crowding reductions depend on the exact shape of the penalty.","Beyond the paper: because the user-equilibrium evaluation uses the same crowding function that generated the line plan, the small system-optimal versus user-equilibrium gap may partly reflect self-consistency of the model; a stated-preference calibration of the crowding factor would be needed to confirm the gap in practice.","Beyond the paper: feeding time-sliced origin-destination matrices into the same cut-and-column machinery would extend the static analysis to peak-hour spreading, where holding line frequencies fixed across periods could change the best crowding-aware plan."],"forward_implications":["Operators can reduce the most crowded sections of a metro network without building new tracks, by rebalancing which lines run and at what frequencies within the existing budget.","A single system-optimal routing model is enough for planning purposes: the user-equilibrium routing is so close that a bi-level model with selfish passengers would add little.","Large real-world networks are within reach of this approach: the full Beijing experiment has hundreds of stations, 534 candidate lines, and 56,916 origin-destination pairs, and crowding-aware instances complete in hours to a few days of compute time.","The crowding factor is not just a modeling detail: raising it shifts the optimal plan toward fewer lines running at higher frequencies, so the model quantifies the frequency-versus-coverage trade-off."],"supporting_citations":[{"why":"Introduces the change-and-go network used to represent passenger routes and transfers explicitly.","marker":"Schöbel and Scholl (2005)"},{"why":"Provides the 5x5-grid benchmark and a capacity-aware cost-optimal line planning model that this paper extends to crowding.","marker":"Friedrich et al. (2017b)"},{"why":"Earlier change-and-go-network line planning with user-optimal route choice, the setting this paper revisits under crowding.","marker":"Goerigk and Schmidt (2017)"},{"why":"Defines the first principle of user equilibrium used to evaluate line plans ex post.","marker":"Wardrop (1952)"},{"why":"Supplies the potential-minimization result that turns the user-equilibrium evaluation into a convex quadratic program.","marker":"Roughgarden (2007)"},{"why":"Provides the column-generation approach for dynamically generating passenger routes in line planning.","marker":"Borndörfer, Grötschel, and Pfetsch (2007)"},{"why":"Supplies Farkas pricing to restore feasibility when the restricted master problem lacks routes.","marker":"Kowalczyk and Leus (2018)"},{"why":"Supports the assumption of a fixed line pool and the evaluation of alternative line plans.","marker":"Van Lieshout, Bouman, and Huisman (2020)"}],"fun_headline_variants":["Crowding-aware metro plans cut crowding with slight delay","Cut-and-column algorithm eases metro crowding efficiently","New method reduces metro crowding with minimal travel cost","Optimal transit lines under crowding via cut-and-column","Tractable line planning slashes crowding on Beijing metro"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that a passenger's discomfort on a train segment is exactly a fixed factor times the square of the number of passengers on that segment divided by the train frequency, and that passengers choose routes to minimize ride time plus that discomfort.","fun_headline_variants_meta":{"raw":{"variants":["Crowding-aware metro plans cut crowding with slight delay","Cut-and-column algorithm eases metro crowding efficiently","New method reduces metro crowding with minimal travel cost","Optimal transit lines under crowding via cut-and-column","Tractable line planning slashes crowding on Beijing metro"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000269,"raw_usage":{"total_tokens":1692,"prompt_tokens":1089,"completion_tokens":603,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":705,"completion_tokens_details":{"reasoning_tokens":528}},"tokens_in":705,"tokens_out":603,"duration_ms":6448,"temperature":1.0,"reasoning_tokens":528,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T15:34:22.517208+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Collect stated-preference data on how much extra travel time passengers would accept to avoid a train that is 10% or 50% fuller, and fit a marginal crowding cost as a function of load factor. If that fitted function is not approximately linear in x_a divided by y_l(a) (for example, if discomfort saturates after seating is full), re-solving the Beijing sub-network instance with the fitted curve should change the chosen line frequencies; if it does, the reported crowding-reduction and travel-time trade-off is tied to the quadratic-over-linear assumption.","supporting_citations":[{"cited_title":"Proceeding of 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (Germany)","cited_arxiv_id":null,"evidence_quote":"Introduces the change-and-go network used to represent passenger routes and transfers explicitly."},{"cited_title":"European Journal of Operational Research 259(2):424--436","cited_arxiv_id":null,"evidence_quote":"Earlier change-and-go-network line planning with user-optimal route choice, the setting this paper revisits under crowding."},{"cited_title":"Proceedings of the Institute of Civil Engineers Part II(1):325--378","cited_arxiv_id":null,"evidence_quote":"Defines the first principle of user equilibrium used to evaluate line plans ex post."},{"cited_title":"Nisan N, Roughgarden T, Tardos E, Vazirani VV, eds., Algorithmic game theory, chapter 18, 459--484 (Cambridge University Press)","cited_arxiv_id":null,"evidence_quote":"Supplies the potential-minimization result that turns the user-equilibrium evaluation into a convex quadratic program."},{"cited_title":"o rfer R, Gr\\","cited_arxiv_id":null,"evidence_quote":"Provides the column-generation approach for dynamically generating passenger routes in line planning."},{"cited_title":"INFORMS Journal on Computing 30(4):768--782","cited_arxiv_id":null,"evidence_quote":"Supplies Farkas pricing to restore feasibility when the restricted master problem lacks routes."},{"cited_title":"Transportation Science 54(3):740--761","cited_arxiv_id":null,"evidence_quote":"Supports the assumption of a fixed line pool and the evaluation of alternative line plans."}],"review_version":1}