{"id":"f4c77ea5-3099-4867-a761-ecd5b3ac036e","arxiv_id":"2508.07159","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"If the generalized queue replacement principle holds, dynamic user equilibrium with route and departure time choice can be obtained by solving two linear programs in sequence.","lead":"This paper proposes a two-step linear-programming method for computing dynamic user equilibrium with simultaneous route and departure time choice on road networks. The method relies on a new condition, the generalized queue replacement principle, and is demonstrated on networks with up to 74 nodes.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.1's derivative claim is not derived from the LP; Theorem 3.1's exactness certificate rests on an unproven property of πC.","rationale":"After reading the full paper, the central claim is that solving [COST-LP-D] and then checking zero optimality of [FLOW-LP] exactly solves [DUE-LCP]. For this to hold, the candidate cost pattern must satisfy the original queueing and consistency conditions. The queueing condition is encoded in [FLOW-LP] via θ(t), but consistency is dropped entirely, relying on Lemma 3.1. The proof of Lemma 3.1 is a reference to a figure rather than a derivation from LP optimality: on σ>0 intervals, qC_i=0, so πC_i is not pinned by complementarity and the LP imposes no derivative constraint. This is not a mere presentation issue; the derivative of πC is also needed to define θ(t) and to prove Lemma A.1 and Theorem 3.2. Additionally, the substitution argument asserts πUE=πC without proof. The numerical experiments do not resolve this because they verify objective gaps on a discretized grid, not the continuous-time consistency condition. I therefore agree with the reader's weakest assumption and see no reason to change the CONDITIONAL verdict: the proof must be repaired, and a concrete check of Eq. (84) would settle whether the gap is formal or substantive.","tokens_in":26912,"tokens_out":15873,"duration_ms":168956,"concrete_test":"Independently re-derive Eq. (84) from the KKT conditions (38)–(42) of [COST-LP-P]/[COST-LP-D] without invoking Figure 18; if the identity cannot be derived, Lemma 3.1 is unproven. To test the claim computationally, solve [COST-LP-D] on a minimal two-origin network sharing a downstream bottleneck, with an intermediate origin whose departure support is disjoint in time from the bottleneck queue, and compute the finite-difference slope of πC_i on intervals where σ_i>0. If the slope is nonzero or exceeds 1 for the solver-returned optimal solution, Lemma 3.1 is false and Theorem 3.1's certification test can fail.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Lemma 3.1 (Appendix A.1) asserts a pointwise derivative identity for the dual variable πC: πC_i_dot(t)=−s_dot(t) when σ_i(t)=0 and 0 when σ_i(t)>0, justified only by 'By Figure 18'. The LP optimality conditions (38)–(42) do not determine πC on intervals where qC_i(t)=0; [COST-LP-D] is an infinite-dimensional LP with no differentiability or slope constraints on π. Hence πC need not be differentiable, and even a differentiable selection need not be flat on the support of σ. Lemma 3.1 is the only justification for deleting the consistency condition (5) from [FLOW-LP]; if it fails, a zero objective in [FLOW-LP] certifies only the relaxed problem, not the original DUE. The same gap affects the assertion πUE=πC after substitution (Section 3.3.1) and Lemma A.1, on which the sufficient condition of Theorem 3.2 depends. Without a rigorous derivation of Eq. (84), the iff statement of Theorem 3.1 and Corollary 3.1 are not proven.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a two-stage linear-programming procedure for computing dynamic user equilibrium (DUE) with route and departure time choice (RDTC) in many-to-one networks. In the first stage, a relaxed problem ([COST-LP-P]/[COST-LP-D]) is solved to obtain a candidate queueing-delay/cost pattern. In the second stage, this candidate is substituted into the original equilibrium conditions, yielding a flow-determination LP ([FLOW-LP]). The central claim (Theorem 3.1 and Corollary 3.1) is that the GQRP holds—i.e., the candidate queueing delays equal the true equilibrium queueing delays—if and only if [FLOW-LP] is feasible with zero objective value; when this holds, the flow solution is an exact DUE. A sufficient condition on the slope of the schedule-delay cost function (Theorem 3.2) is also given, along with numerical experiments on Braess, Nguyen, Sioux Falls, and Eastern Massachusetts networks.","tokens_in":27268,"tokens_out":9070,"duration_ms":97972,"significance":"If the central theorem is valid, the paper provides a genuinely useful computational shortcut: exact DUE-RDTC solutions are obtained by solving two ordinary LPs, with no iterative fixed-point updates. The numerical demonstrations on large benchmark networks and the explicit connection to first-best pricing are valuable strengths. The manuscript is also transparent about the boundary between exact and approximate results in the no-GQRP case. However, the advertised exactness certificate currently rests on an unproved derivative property of the dual LP solution and on a flawed step in the proof of Lemma 3.3. These gaps are load-bearing: without them, Theorem 3.1 and Corollary 3.1 are not established.","major_comments":[{"comment":"The derivation of the sufficient condition (65) uses the inequality -s_dot(t)Σ μ ≤ Σ wC_dot(t)μ as a lower bound. Lemma A.1 allows wC_dot to be either -s_dot(t) or 0. When s_dot(t)<0 (early arrivals), -s_dot(t)>0, so the value 0 is smaller than -s_dot(t) and the stated inequality can fail. This invalidates the derivation of the non-negativity of qF and hence the proof of Lemma 3.2/Theorem 3.2 for early-arrival periods. A correct case analysis distinguishing early and late arrival is needed.","section":"A.2, Eq. (100)"}],"minor_comments":[{"comment":"The figure captions and text do not match: the text refers to selected origins (21,26,54,32,38,62) for Figure 12 and (2,4,6,9,12,13) for Figure 14, while the captions list different origin sets. The captions should be corrected.","section":"5.2"},{"comment":"The route-choice condition in Eq. (6) is written as w(t)-Aπ(t)+c≥0, whereas the element-wise form in Eq. (6a) and later equations use A^Tπ. The notation should be made consistent.","section":"Eq. (6)"},{"comment":"The proof refers to '[DC-LP]' but no problem with that name is defined; it should presumably be [COST-LP] or [DSO-LP]. Please clarify.","section":"4.1.1, Theorem 4.1 proof"},{"comment":"The proof is circular: it states that if a scaling factor κ exists then the GQRP holds, but it does not construct such a κ or prove its existence. The proposition may be true, but the argument as written is not a proof.","section":"A.4, Proposition 4.1"},{"comment":"The procedure list skips from Step 2-1 to Step 2-3 (no Step 2-2 is shown). This appears to be a numbering error.","section":"3.4"}],"recommendation":"major_revision","confidential_remarks":"The main obstacle is the unproved derivative property of πC in Lemma 3.1, which is load-bearing for the central exactness certificate. The flawed substitution in Lemma 3.3 is also a clear proof gap. If the authors can supply a rigorous proof of Eq. (84) under explicit assumptions and repair the proof of Lemma 3.3, the paper could become acceptable. I do not see a fundamental circularity in the GQRP formulation itself, only missing mathematical support for key steps."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis paper genuinely extends the queue replacement principle from departure-time-choice corridors to simultaneous route and departure-time choice on many-to-one networks. The two-LP decomposition—cost LP first, then a zero-objective flow LP to certify exactness—is a real idea, and the numerical results on Sioux Falls and Eastern Massachusetts are impressive in scale for this literature. It deserves a serious referee.\n\nWhat is new and good: the GQRP definition, the FLOW-LP verification (Theorem 3.1), and the sufficient condition (65) on the schedule delay slope for a closed-form flow construction. These are not in the prior DTC corridor work. The experiments are credible, though no code/data are provided and exactness is only up to a 0.1 time step.\n\nThe soft spots are in the proof of exactness, not in the overall strategy.\n\nFirst, Lemma 3.1 (Appendix A.1) asserts that the dual variable πC satisfies πC_dot = −s_dot when the slack σ is 0 and πC_dot = 0 when σ > 0, justified by “By Figure 18.” The LP optimality conditions (38)–(42) do not determine the derivative of πC; πC is just a dual variable, and nothing in the dual LP forces differentiability or that specific slope. This lemma is load-bearing: it is the only reason the consistency condition (5) is dropped from the FLOW-LP. If the identity fails, a zero objective in the FLOW-LP certifies only a relaxation of the original DUE problem, and Theorem 3.1’s “if” direction is not proven.\n\nSecond, Lemma 3.3 (Appendix A.3) claims the objective of the FLOW-LP with the constructed flow is zero, but the final step (Eq. (122) to (123)) is left as an assertion. The paper does not show that σ·qF = 0 for the constructed flow, and the substitution in Eq. (122) does not follow from the definition of yF. This affects the sufficient condition Theorem 3.2.\n\nThird, the continuous-time claims are checked with a discrete-time LP at Δt = 0.1. The residuals are small, but there is no discussion of whether the zero-objective test is robust to discretization.\n\nScope is limited to many-to-one networks with homogeneous users and a single destination; the paper is transparent about this.\n\nBottom line: the idea is promising, the paper is readable, and the proof gaps are local and possibly repairable—say, by imposing regularity assumptions on πC or deriving the derivative identity from a more careful duality argument. The numerical evidence suggests the method is more than a conjecture. I would send it to peer review with a request for substantial revision focused on Lemma 3.1 and Lemma 3.3, and for reproducible artifacts. Desk rejection would be too harsh.","headline":"A promising two-LP extension of the queue replacement principle to route and departure time choice, but the exactness proof rests on two unproven lemmas (3.1 and 3.3) that a referee should push hard on.","tokens_in":27703,"tokens_out":7142,"would_cite":true,"duration_ms":69591,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90B20","90C05","90C33"],"pacs":[],"model":"deepseek-v4-flash","headline":"Two linear programs pin down an exact dynamic traffic equilibrium","keywords":["dynamic user equilibrium","route and departure time choice","queue replacement principle","linear programming","Lagrangian coordinate system","bottleneck model","complementarity problem"],"falsifier":"On a small network (e.g., two serial bottlenecks), solve [COST-LP-D] for a convex schedule-delay function with a steep late-arrival penalty; compute $\\dot{\\pi}^C_i(t)$ over the set where the slack $\\sigma_i(t)>0$. If any point has $\\dot{\\pi}^C_i(t)\\neq 0$, then solve [FLOW-LP] and check whether its optimal value is zero while the reconstructed cumulative departure curve at a bottleneck exceeds capacity; that combination breaks Lemma 3.1's implication.","tokens_in":26820,"feed_emoji":"🚦","tokens_out":7268,"duration_ms":61849,"temperature":0.7,"pith_summary":"This paper tries to establish that the dynamic user equilibrium with simultaneous route and departure time choice—a problem normally posed as a hard mixed complementarity problem with non-convex structure—can be decomposed into two linear programs, with a simple LP optimality check certifying exactness. The core concept is the generalized queue replacement principle (GQRP): under it, the equilibrium queueing-delay pattern equals the solution of a relaxed 'cost determination' LP. The paper proves that if the subsequent 'flow determination' LP is feasible and has zero optimal value, then the candidate cost pattern is exactly the equilibrium cost pattern, and the LP's solution gives the exact equilibrium flow pattern. If true, this gives a tractable, certificate-producing alternative to iterative variational-inequality solvers, which often fail to converge on large networks. The paper also shows that whether the principle holds depends on the slope of the schedule-delay cost function, which policy can influence.","feed_headline":"Two linear programs pin down an exact dynamic traffic equilibrium","feed_subtitle":"When the flow LP is feasible with zero objective, the candidate delay pattern is provably the equilibrium one.","key_machinery":"The generalized queue replacement principle (GQRP) — an equivalence between the equilibrium queueing-delay pattern and the solution of a cost-determination LP obtained by relaxing the queueing and consistency conditions. The load-bearing lever is Theorem 3.1, which ties GQRP to a zero-objective feasibility test on a second flow-determination LP. The decomposition works because the relaxed cost problem has a skew-symmetric structure that splits into primal and dual LPs, and the Lagrangian-coordinate formulation makes route and departure-time costs linear complements rather than nested nonlinear functions.","core_discovery":"Using a Lagrangian-like coordinate system where variables are indexed by destination arrival time, the authors re-express the DUE-RDTC problem as a mixed linear complementarity problem, then relax the queueing condition to get a symmetric problem that splits into two LPs; the dual supplies a candidate delay pattern. The generalized queue replacement principle (GQRP) holds exactly when that candidate equals the true equilibrium delay pattern. The central claim (Theorem 3.1): the GQRP holds iff the flow-determination LP formed by substituting the candidate cost pattern into the original formulation is feasible with optimal value zero; then (Corollary 3.1) its flow solution with the candidate c","pith_inferences":["If the 'By Figure 18' step in Lemma 3.1 is replaced by a derivation, the same two-LP decomposition may extend to equilibrium problems beyond traffic, wherever the equilibrium condition splits into a cost-side and a flow-side LCP with skew-symmetric coupling.","Condition (65) is testable a priori from the cost-determination solution; mapping where the GQRP holds in (schedule-slope, demand, capacity) space could turn the principle into a design tool for pricing and subsidies.","The Lagrangian coordinate system is the enabler: it linearizes route and departure-time choice; the same trick may help other dynamic equilibrium models with path-dependent costs.","The failure mode of the GQRP—delays dissipating too fast—suggests that a regularization of the relaxed queueing condition could make the LP test almost always pass, at the price of a small approximation error."],"forward_implications":["Exact DUE-RDTC solutions on large many-to-one networks can be certified by solving two LPs; the numerical experiments report objective values below $10^{-6}$ on Sioux Falls and Eastern Massachusetts networks.","The zero-objective test is a certificate: no post-hoc verification of equilibrium conditions is needed, and the method avoids the non-convergence of fixed-point-based VI/DVI algorithms.","When the schedule-delay cost function satisfies condition (65), the equilibrium flow pattern can be constructed analytically from the cost-determination solution, skipping the second LP entirely.","The GQRP implies the dynamic system optimal and user equilibrium cost patterns coincide under Assumption 4.1, so queue-eliminating tolls equal to the equilibrium delay yield a Pareto improvement.","When the principle fails, the flow-determination LP still produces a near-equilibrium solution with violations localized in time and space, suitable as a warm start for refinement."],"supporting_citations":[{"why":"Supplies the Lagrangian-like coordinate system and the DUE-LCP formulation with queueing and consistency conditions that the paper builds on.","marker":"Akamatsu et al., 2015"},{"why":"Introduced the queue replacement principle for departure-time choice in corridors, the concept this paper generalizes to route choice.","marker":"Fu et al., 2022"},{"why":"Extended the queue replacement approach to heterogeneous commuters and helped define the candidate-cost/flow split used here.","marker":"Sakai et al., 2024a,b"},{"why":"Provides the LCP-to-QP equivalence lemma used to transform [DUE-LCP] and to read off the zero-objective certificate.","marker":"Cottle et al. (2009)"},{"why":"Establishes the single-bottleneck pricing-equals-delay insight that underlies the queue replacement idea.","marker":"Vickrey (1969)"},{"why":"Documents the convergence failures of iterative DUE algorithms on large networks, the computational motivation the method answers.","marker":"Han et al., 2019"}],"fun_headline_variants":["Two LPs yield exact dynamic user equilibrium","Exact DUE via two linear programs","Queue replacement: dual LPs solve route-time choice","GQRP theorem: two LPs guarantee exact DUE","Dynamic equilibrium via two sequential LPs"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"The proof of Lemma 3.1 assumes from a figure that the candidate shadow travel cost is flat whenever the departure-time slack is positive, and this flatness is not derived from the LP optimality conditions; if it fails, the zero-objective test may certify flows that violate the original queueing and consistency conditions.","fun_headline_variants_meta":{"raw":{"variants":["Two LPs yield exact dynamic user equilibrium","Exact DUE via two linear programs","Queue replacement: dual LPs solve route-time choice","GQRP theorem: two LPs guarantee exact DUE","Dynamic equilibrium via two sequential LPs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.0005,"raw_usage":{"total_tokens":2242,"prompt_tokens":661,"completion_tokens":1581,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":405,"completion_tokens_details":{"reasoning_tokens":1524}},"tokens_in":405,"tokens_out":1581,"duration_ms":10613,"temperature":1.0,"reasoning_tokens":1524,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T22:19:25.744955+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a small network (e.g., two serial bottlenecks), solve [COST-LP-D] for a convex schedule-delay function with a steep late-arrival penalty; compute $\\dot{\\pi}^C_i(t)$ over the set where the slack $\\sigma_i(t)>0$. If any point has $\\dot{\\pi}^C_i(t)\\neq 0$, then solve [FLOW-LP] and check whether its optimal value is zero while the reconstructed cumulative departure curve at a bottleneck exceeds capacity; that combination breaks Lemma 3.1's implication.","supporting_citations":[],"review_version":2}