pith. sign in

arxiv: 2508.07159 · v3 · submitted 2025-08-10 · 🧮 math.OC

Queue Replacement Approach to Dynamic User Equilibrium Assignment with Route and Departure Time Choice

Takara Sakai , Takashi Akamatsu , Koki Satsukawa This is my paper

Pith reviewed 2026-05-19 00:09 UTC · model grok-4.3

classification 🧮 math.OC
keywords dynamic user equilibriumroute and departure time choicequeue replacement principlelinear programmingtraffic assignmentequilibrium flowsnetwork optimization
0
0 comments X

The pith

The generalized queue replacement principle equates the equilibrium queueing-delay pattern to the solution of a relaxed linear program.

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

This paper presents a hybrid method for finding dynamic user equilibrium flows when users choose both routes and departure times. The central idea is the generalized queue replacement principle, which shows that the equilibrium delays match the output of a linear program created by relaxing parts of the original problem. The authors supply a test to check when this principle applies, then outline a two-step procedure that solves one linear program for the cost pattern and a second for the flow pattern. The result is an exact equilibrium solution for homogeneous users. The reduction matters because it replaces iterative simulation loops with standard linear-programming solvers that can be run on networks of practical size.

Core claim

The generalized queue replacement principle (GQRP) 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. Based on the GQRP, the paper develops 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. A preliminary method is given for determining whether the GQRP holds for any given network and demand pattern.

What carries the argument

The generalized queue replacement principle (GQRP), which relaxes selected conditions of the DUE-RDTC problem so that the equilibrium queueing-delay pattern becomes the optimum of a linear program.

If this is right

  • When the GQRP is verified, the equilibrium cost pattern (including queueing delays) is recovered directly as the solution of one linear program.
  • The equilibrium flow pattern is then recovered by solving a second linear program that uses the costs from the first step.
  • The two-step procedure yields an exact solution to the original DUE-RDTC problem for homogeneous users.
  • The approach remains computationally feasible on networks of increasing size, as confirmed by the reported numerical tests.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same replacement idea might be tested on networks that include signal controls or heterogeneous users if analogous relaxations can be defined.
  • Because the method produces both costs and flows from linear programs, it could be embedded inside larger optimization frameworks that treat equilibrium as a constraint.
  • Automated verification of the GQRP for arbitrary networks would further reduce the need for manual checks before applying the two-LP procedure.

Load-bearing premise

The generalized queue replacement principle must hold for the network and demand pattern being studied.

What would settle it

Solving the same DUE-RDTC instance by an independent iterative method and finding that the resulting queueing-delay pattern differs from the one produced by the first linear program would disprove the claimed equivalence.

Figures

Figures reproduced from arXiv: 2508.07159 by Koki Satsukawa, Takara Sakai, Takashi Akamatsu.

Figure 1
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. 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 … view at source ↗
Figure 4
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 ↗
Figure 5
Figure 5. Figure 5: Flowchart of the hierarchical numerical algorithm [PITH_FULL_IMAGE:figures/full_fig_p017_5.png] view at source ↗
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 Time 0 100 200 300 400 Cumulative vehicles Link (1,3) Arrival curve Departure curve 0 10 20 30 40 50 60 Time 0 100 200 300 400 500 Cumulative v… view at source ↗
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] view at source ↗
Figure 11
Figure 11. Figure 11: Equilibrium queueing delay pattern in Sioux [PITH_FULL_IMAGE:figures/full_fig_p020_11.png] view at source ↗
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] view at source ↗
Figure 13
Figure 13. Figure 13: Equilibrium queueing pattern in Eastern-Massachusetts network [PITH_FULL_IMAGE:figures/full_fig_p021_13.png] view at source ↗
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] view at source ↗
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] view at source ↗
Figure 18
Figure 18. Figure 18: Graphical relationship between 𝑠(𝑡) and 𝜋 C 𝑖 (𝑡) [PITH_FULL_IMAGE:figures/full_fig_p024_18.png] view at source ↗
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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript develops a hybrid analytical-numerical method for dynamic user equilibrium (DUE) with simultaneous route and departure time choice (RDTC) for homogeneous users. The central contribution is the generalized queue replacement principle (GQRP), which claims an equivalence between the equilibrium queueing-delay pattern and the optimal solution of a linear program obtained by relaxing selected conditions from the original DUE-RDTC formulation. The authors describe a procedure to test whether GQRP holds for a given instance and then solve two sequential LPs to recover the equilibrium cost pattern (including delays) and the corresponding flow pattern. Computational experiments on networks of varying scales are presented to illustrate effectiveness.

Significance. If the GQRP equivalence can be shown to hold rigorously without admitting delay patterns inconsistent with dynamic network loading, the approach would provide an exact, LP-based solution method for a class of DUE-RDTC problems that are otherwise solved iteratively or via simulation. This would be a notable advance in transportation network optimization, particularly for its potential to avoid heuristic convergence issues while scaling to moderate-sized networks.

major comments (2)
  1. [Section defining the GQRP and the LP relaxation] The core claim that relaxing conditions in the DUE-RDTC formulation yields an LP whose optimum is exactly the equilibrium queueing-delay pattern (via GQRP) is load-bearing for the entire solution procedure. The manuscript should supply an explicit proof or independent verification that the relaxation preserves time-dependent flow conservation and the complementarity between queue lengths and delays, especially on networks containing multiple interacting bottlenecks; without this, the equivalence risks being an approximation rather than an identity.
  2. [Section describing the GQRP validity check] The method presented for determining whether GQRP holds for a given network and demand pattern appears to rely on the same relaxed LP structure used in the solution procedure. This creates a potential circularity that undermines the check; an independent test (e.g., comparison against an analytical benchmark or a small-scale simulation with known interacting bottlenecks) is needed to confirm validity before claiming exact DUE solutions.
minor comments (2)
  1. [Computational results section] The abstract states that results confirm effectiveness on networks of varying scales, but the main text should include a table or figure summarizing network sizes, number of bottlenecks, and run times to allow readers to assess scalability.
  2. [Formulation sections] Notation for the relaxed LP objective and constraints should be cross-referenced explicitly to the original DUE-RDTC formulation to improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their detailed and constructive comments on our manuscript. We have reviewed the major comments and provide point-by-point responses below, indicating where revisions will be made to address the concerns.

read point-by-point responses

  1. Referee: [Section defining the GQRP and the LP relaxation] The core claim that relaxing conditions in the DUE-RDTC formulation yields an LP whose optimum is exactly the equilibrium queueing-delay pattern (via GQRP) is load-bearing for the entire solution procedure. The manuscript should supply an explicit proof or independent verification that the relaxation preserves time-dependent flow conservation and the complementarity between queue lengths and delays, especially on networks containing multiple interacting bottlenecks; without this, the equivalence risks being an approximation rather than an identity.

    Authors: We agree that a rigorous proof is essential to establish the GQRP as an exact equivalence rather than an approximation. In the current manuscript, the GQRP is motivated and illustrated through the relaxation of the DUE-RDTC formulation, with supporting arguments based on queue replacement properties. However, to fully address this, we will add an explicit proof in the revised manuscript. This proof will demonstrate that the LP relaxation preserves time-dependent flow conservation and the complementarity conditions for queue lengths and delays. We will extend the analysis to networks with multiple interacting bottlenecks by considering the sequential nature of the queue replacement and showing consistency with dynamic network loading. revision: yes

  2. Referee: [Section describing the GQRP validity check] The method presented for determining whether GQRP holds for a given network and demand pattern appears to rely on the same relaxed LP structure used in the solution procedure. This creates a potential circularity that undermines the check; an independent test (e.g., comparison against an analytical benchmark or a small-scale simulation with known interacting bottlenecks) is needed to confirm validity before claiming exact DUE solutions.

    Authors: We recognize the concern regarding potential circularity in the validity check procedure. The check in the manuscript involves solving the relaxed LP and then verifying the resulting delay pattern against the original DUE conditions through a separate evaluation step. To eliminate any ambiguity, we will revise the description to emphasize the independence of the verification process. Additionally, we will include numerical validations on small-scale networks with known analytical solutions or simulation benchmarks to confirm that the GQRP holds in cases with interacting bottlenecks. revision: partial

Circularity Check

0 steps flagged

No significant circularity; GQRP equivalence derived independently via relaxation and verification method

full rationale

The paper introduces the generalized queue replacement principle (GQRP) as an equivalence between equilibrium queueing-delay patterns and the solution to an LP obtained by relaxing selected conditions from the original DUE-RDTC formulation. It then supplies an explicit method to determine whether GQRP holds for a given network and demand, followed by a two-LP procedure to recover the exact equilibrium cost and flow patterns. No step reduces a claimed prediction or result to a fitted input, self-citation chain, or definitional identity by construction; the verification method and LP relaxations constitute independent mathematical content that can be checked against the original complementarity and conservation conditions. This satisfies the default expectation that most papers are non-circular, with the central claim retaining external falsifiability through the GQRP check.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claim rests on the validity of the GQRP equivalence and the homogeneity of users; no free parameters are explicitly fitted in the abstract description.

axioms (2)
  • domain assumption Users are homogeneous
    Explicitly stated for the DUE-RDTC problem under consideration.
  • ad hoc to paper GQRP holds for the instance
    The method requires determining whether this principle applies before solving the LPs.
invented entities (1)
  • Generalized Queue Replacement Principle (GQRP) no independent evidence
    purpose: Establishes equivalence between equilibrium queueing delays and an LP relaxation
    Introduced as the core new concept enabling the two-stage LP solution procedure.

pith-pipeline@v0.9.0 · 5668 in / 1157 out tokens · 45823 ms · 2026-05-19T00:09:29.810689+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

  1. [1]

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

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

    work page 2000

  2. [2]

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

    work page 2001

  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

    work page 2017

  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

    work page 2015

  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

    work page 2021

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

    work page 1990

  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

    work page 1993

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

    work page 2011

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

    work page 2022

  10. [10]

    Computingdynamicuserequilibriaonlarge-scalenetworkswithsoftware implementation

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

    work page 2019

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

    work page 1981

  12. [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). Equivalentoptimizationproblemforfindingequilibriuminthebottleneckmodelwith departure time choices. In4th IMA Intern...

    work page 2002

  13. [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,M.andNewell,G.F.(1987). Queueevolutiononfreewaysleadingtoasinglecorecityduringth...

    work page 1993

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

    work page 2004

  15. [15]

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

    work page 2022

  16. [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 Research Core Team (Accessed: September 22, 2024). Transportation networks for resea...

    work page 2004

  17. [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 control.Transportation Research Part E: Logistics and Transportation Review, 60:94–112

    work page 1969