Pith. sign in

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 →

arxiv 2508.07159 v4 pith:GYIF6PLE submitted 2025-08-10 math.OC

classification math.OC MSC 90B2090C0590C33
keywords dynamicuserequilibriumrouteanddeparturetimechoicequeuereplacementprinciplelinearprogrammingLagrangiancoordinatesystembottleneckmodelcomplementarityproblem
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

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.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 5 minor

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)
  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)
  1. [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.
  2. [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.
  3. [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.
  4. [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.
  5. [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

0 steps flagged · score 2.0 of 10

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 3 free parameters · 5 assumptions · 0 invented entities

The theoretical method rests on standard LP duality, a cited DUE existence result, and one unproved structural property of the dual solution (Eq. 84). The numerical results rely on hand-chosen test parameters and a capacity scaling factor that are not fitted to data for the central claim.

free parameters (3)
  • schedule delay slope parameters beta, gamma = beta=0.3, gamma=0.6 (gamma=1.2 in no-GQRP scenario)
    Hand-chosen test parameters in numerical examples; they determine whether the sufficient condition (65) and GQRP hold.
  • capacity scaling factor = 1/200
    Applied to Sioux Falls and Eastern Massachusetts capacities to create non-negligible congestion, since original demand produced almost no queues.
  • discretization interval dt = 0.1
    Numerical resolution for all experiments; exactness claims depend on this discretization.
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.
    Used to transform DUE-LCP to DUE-QP (Proposition 2.1) and to justify the FLOW-LP zero-objective test (Theorem 3.1). Requires the LCP to have a solution and the QP to be well-posed in function space; not proven here.
  • domain assumption In DUE, users arriving at the destination at the same time have the same departure times at all nodes on their routes.
    Section 2.2, paragraph before Eq. (1). This is cited to prior work (Friesz et al. 1993; Kuwahara and Akamatsu 1993; Akamatsu 2001), not re-derived for the RDTC case with multiple routes.
  • domain assumption Point queue model with FIFO and schedule delay function with s_dot > -1.
    Section 2.1. Standard in the literature; the assumption s_dot > -1 is used in Lemma 3.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.
    This is the load-bearing unproved property used to prove Lemma 3.1 and Lemma A.1. It is presented as 'By Figure 18' with no derivation from LP optimality.
  • domain assumption Assumption 4.1: In the DSO state, node-passing time is uniquely determined by destination arrival time.
    Used for policy theorems 4.1 and 4.2; not needed for the numerical method.

how reviews work

0 comments
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 reproduced from arXiv: 2508.07159 by the authors.

Figure 1
Figure 1. Framework of the proposed GQRP-based approach [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 3
Figure 3. Schedule delay cost function equilibrium travel cost pattern. This property is the essence of the GQRP. In the second step, we verify whether the GQRP holds (i.e., whether the candidate cost pattern obtained from [COST-LP-D] is an exact equilibrium travel cost pattern) and determine the equilibrium flow pattern. Specifically, we substitute the candidate cost pattern into the original DUE formulation. This substituti… view at source ↗
Figure 4
Figure 4. Definition of variables in the Lagrangian-like coordinate system [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
Figures from the paper (9 more)
Figure 5
Figure 5. Figure 5: Flowchart of the hierarchical numerical algorithm [PITH_FULL_IMAGE:figures/full_fig_p017_5.png]
Figure 8
Figure 8. Figure 8: 𝝅 C(𝑡) and 𝝆 C in Braess net￾work 0 10 20 30 40 50 60 Time 0 100 200 300 Cumulative vehicles Link (0,1) Arrival curve Departure curve 0 10 20 30 40 50 60 Time 0 100 200 300 400 500 600 Cumulative vehicles Link (1,2) Arrival curve Departure curve 0 10 20 30 40 50 60 Tim…
Figure 9
Figure 9. Figure 9: Cumulative equilibrium arrival and departure curves at each link (Braess network) [PITH_FULL_IMAGE:figures/full_fig_p019_9.png]
Figure 11
Figure 11. Figure 11: Equilibrium queueing delay pattern in Sioux [PITH_FULL_IMAGE:figures/full_fig_p020_11.png]
Figure 12
Figure 12. Figure 12: Equilibrium cost and demand flow in the Sioux Falls network for selected origins [PITH_FULL_IMAGE:figures/full_fig_p020_12.png]
Figure 13
Figure 13. Figure 13: Equilibrium queueing pattern in Eastern-Massachusetts network [PITH_FULL_IMAGE:figures/full_fig_p021_13.png]
Figure 14
Figure 14. Figure 14: Equilibrium cost and demand flow in Eastern-Massachusetts network for selected origins [PITH_FULL_IMAGE:figures/full_fig_p021_14.png]
Figure 15
Figure 15. Figure 15: Nguyen network with bot￾tleneck capacity pattern 0 1 2 3 4 7 5 8 6 9 10 11 12 [PITH_FULL_IMAGE:figures/full_fig_p023_15.png]
Figure 18
Figure 18. Figure 18: Graphical relationship between 𝑠(𝑡) and 𝜋 C 𝑖 (𝑡) [PITH_FULL_IMAGE:figures/full_fig_p024_18.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references

  1. [1]

    TransportationResearchPartB:Methodological , 34(6):515–531

    Akamatsu,T.(2000).Adynamictrafficequilibriumassignmentparadox. TransportationResearchPartB:Methodological , 34(6):515–531

  2. [2]

    Akamatsu, T. (2001). An efficient algorithm for dynamic traffic equilibrium assignment with queues.Transportation Science, 35(4):389–404

  3. [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

  4. [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

  5. [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

  6. [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...

  7. [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

  8. [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...

Show all 17 references
  1. [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

  2. [10]

    Computingdynamicuserequilibriaonlarge-scalenetworkswithsoftware implementation

    Han, K., Eve, G., andFriesz, T.L.(2019). Computingdynamicuserequilibriaonlarge-scalenetworkswithsoftware implementation. Networks and spatial economics, 19(3):869–902

  3. [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

  4. [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...

  5. [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,...

  6. [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

  7. [15]

    Sakai, T., Satsukawa, K., and Akamatsu, T. (2022). Non-existence of queues for system optimal departure patterns in tree networks.arXiv [math.OC]

  8. [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...

  9. [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...

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.