REVIEW 1 major objections 5 minor 17 references
Queue Replacement Approach to Dynamic User Equilibrium Assignment with Route and Departure Time Choice
T0 review · 1 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read Two linear programs pin down an exact dynamic traffic equilibrium
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (1)
- [A.2, Eq. (100)] 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.
minor comments (5)
- [5.2] 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.
- [Eq. (6)] 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.
- [4.1.1, Theorem 4.1 proof] 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.
- [A.4, Proposition 4.1] 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.
- [3.4] 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.
Circularity Check
No significant circularity: GQRP is a reformulation/equivalence result, not a tautology; self-citations are background and not load-bearing.
full rationale
The GQRP is defined as the equality between the equilibrium queueing delay pattern and the COST-LP-D solution (Definition 3.1, Eq. 43). Theorem 3.1 does not assume this equality; it constructs [FLOW-LP] using the candidate cost pattern as fixed coefficients and, via Lemma 2.1 (a standard LCP-QP equivalence), proves that a feasible zero-objective solution of [FLOW-LP] satisfies the complementarity conditions of the original [DUE-LCP]. Thus the assertion that GQRP holds is the conclusion of an equivalence proof, not an input to the derivation. The flow-determination step is not a fitted parameter passed off as a prediction: wC, piC, and rhoC are solved from the cost-determination LP, and the flow variables are then checked against the original equilibrium conditions. The main technical weakness is Lemma 3.1 (Appendix A.1, Eq. 84), where the derivative claim piC_i_dot(t) = -s_dot(t) or 0 is justified only 'By Figure 18' and is not derived from the LP optimality conditions. If this property fails, the consistency condition (5) cannot be dropped and Theorem 3.1's certificate would be unsound; however, that is an unproven lemma / correctness gap, not a circular reduction of an output to an input. The self-citations to the authors' prior QRP and Lagrangian-coordinate work are used as background and for the corridor case, but the RDTC extension and the GQRP verification are argued within this paper. No step reduces by definition to its own input, so the paper is not circular in the sense relevant to this pass.
Assumptions & free parameters
free parameters (3)
- schedule delay slope parameters beta, gamma =
beta=0.3, gamma=0.6 (gamma=1.2 in no-GQRP scenario)
- capacity scaling factor =
1/200
- discretization interval dt =
0.1
assumptions (5)
- standard math Lemma 2.1 (LCP-QP equivalence) applies to the continuous-time DUE-LCP and the DUE-QP, with zero optimal value.
- domain assumption In DUE, users arriving at the destination at the same time have the same departure times at all nodes on their routes.
- domain assumption Point queue model with FIFO and schedule delay function with s_dot > -1.
- ad hoc to paper Equation (84) in A.1: piC_i_dot(t) is either -s_dot(t) or 0 depending on whether sigma_i(t)=0 or >0.
- domain assumption Assumption 4.1: In the DSO state, node-passing time is uniquely determined by destination arrival time.
Cite this review
Pith. "Pith review of Queue Replacement Approach to Dynamic User Equilibrium Assignment with Route and Departure Time Choice." pith.science (2026). https://pith.science/paper/GYIF6PLE
@misc{pith2026250807159,
author = {Pith},
title = {Pith review of: Queue Replacement Approach to Dynamic User Equilibrium Assignment with Route and Departure Time Choice},
year = {2026},
howpublished = {\url{https://pith.science/paper/GYIF6PLE}},
note = {Machine review of arXiv:2508.07159}
}
read the original abstract
This study develops a hybrid analytical and numerical approach for dynamic user equilibrium (DUE) assignment with simultaneous route and departure time choice (RDTC) for homogeneous users. The core concept of the proposed approach is the generalized queue replacement principle (GQRP), which establishes an equivalence between the equilibrium queueing-delay pattern and the solution to a linear programming (LP) problem obtained by relaxing some conditions in the original DUE-RDTC problem. We first present a method for determining whether the GQRP holds. Based on the GQRP, we then develop a systematic procedure to obtain an exact DUE solution by sequentially solving two LPs: one for the equilibrium cost pattern, including queueing delays, and the other for the corresponding equilibrium flow pattern. Computational results on networks of varying scales confirm the effectiveness of the proposed method.
Figures
Figures from the paper (9 more)
Reference graph
Works this paper leans on
-
[1]
TransportationResearchPartB:Methodological , 34(6):515–531
Akamatsu,T.(2000).Adynamictrafficequilibriumassignmentparadox. TransportationResearchPartB:Methodological , 34(6):515–531
2000
-
[2]
Akamatsu, T. (2001). An efficient algorithm for dynamic traffic equilibrium assignment with queues.Transportation Science, 35(4):389–404
2001
-
[3]
and Wada, K
Akamatsu, T. and Wada, K. (2017). Tradable network permits: A new scheme for the most efficient use of network capacity. Transportation Research Part C: Emerging Technologies, 79:178–195
2017
-
[4]
Akamatsu, T., Wada, K., and Hayashi, S. (2015). The corridor problem with discrete multiple bottlenecks.Trans- portation Research Part B: Methodological, 81(3):808–829
2015
-
[5]
Akamatsu, T., Wada, K., Iryo, T., and Hayashi, S. (2021). A new look at departure time choice equilibrium models with heterogeneous users.Transportation Research Part B: Methodological, 148:152–182
2021
-
[6]
Arnott, R., de Palma, A., and Lindsey, R. (1990). Departure time and route choice for the morning commute. Transportation Research Part B: Methodological, 24(3):209–228. Cottle,R.W.,Pang,J.S.,andStone,R.E.(2009). Thelinearcomplementarityproblem . SocietyforIndustrialandApplied Mathematics. Sakai et al.– Queue Replacement Approach to DUE Assignment 29 Daga...
1990
-
[7]
L., Bernstein, D., Smith, T
Friesz, T. L., Bernstein, D., Smith, T. E., Tobin, R. L., and Wie, B. W. (1993). A variational inequality formulation of the dynamic network user equilibrium problem.Operations research, 41(1):179–191. Friesz,T.L.andHan,K.(2019). Themathematicalfoundationsofdynamicuserequilibrium. TransportationResearch Part B: Methodological, 126:309–328
1993
-
[8]
L., Kim, T., Kwon, C., and Rigdon, M
Friesz, T. L., Kim, T., Kwon, C., and Rigdon, M. A. (2011). Approximate network loading and dual-time-scale dynamic user equilibrium.Transportation Research Part B: Methodological, 45(1):176–207. Friesz,T.L.andMookherjee,R.(2006).Solvingthedynamicnetworkuserequilibriumproblemwithstate-dependent time shifts.Transportation Research Part B: Methodological, 4...
2011
Show all 17 references
-
[9]
Fu, H., Akamatsu, T., Satsukawa, K., and Wada, K. (2022). Dynamic traffic assignment in a corridor network: Optimum versus equilibrium.Transportation Research Part B: Methodological, 161:218–246
2022
-
[10]
Computingdynamicuserequilibriaonlarge-scalenetworkswithsoftware implementation
Han, K., Eve, G., andFriesz, T.L.(2019). Computingdynamicuserequilibriaonlarge-scalenetworkswithsoftware implementation. Networks and spatial economics, 19(3):869–902
2019
-
[11]
and Kocur, G
Hendrickson, C. and Kocur, G. (1981). Schedule delay and departure time decisions in a deterministic model. Transportation Science, 15(1):62–77
1981
-
[12]
and Lam, W
Huang, H.-J. and Lam, W. H. K. (2002). Modeling and solving the dynamic user equilibrium route and departure time choice problem in network with queues.Transportation Research Part B: Methodological, 36(3):253–273. Iryo,T.andYoshii,T.(2007). Equivalentoptimizationproblemforfin...
2002
-
[13]
and Akamatsu, T
Kuwahara, M. and Akamatsu, T. (1993). Dynamic equilibrium assignment with queues for a one-to-many OD pattern. volume 12, pages 185–204. In: Daganzo, C.F. (Ed.), Proceedings of the 12th International Symposium on Transportation and Traffic Theory. Elsevior, Berkeley. Kuwahara,...
1993
-
[14]
Lindsey, R. (2004). Existence, uniqueness, and trip cost function properties of user equilibrium in the bottleneck model with multiple user classes.Transportation Science, 38(3):293–314
2004
-
[15]
Sakai, T., Satsukawa, K., and Akamatsu, T. (2022). Non-existence of queues for system optimal departure patterns in tree networks.arXiv [math.OC]
2022
-
[16]
Szeto, W. Y. and Lo, H. K. (2004). A cell-based simultaneous route and departure time choice model with elastic demand. Transportation Research Part B: Methodological, 38(7):593–612. Sakai et al.– Queue Replacement Approach to DUE Assignment 30 Transportation Networks for Rese...
2004
-
[17]
Vickrey, W. S. (1969). Congestion theory and transport investment.American Economic Review, 59(2):251–260. Wada,K.andAkamatsu,T.(2013). Ahybridimplementationmechanismoftradablenetworkpermitssystemwhich obviates path enumeration: An auction mechanism with day-to-day capacity co...
1969
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.