Existence of simultaneous route and departure choice dynamic user equilibrium

Ke Han, Terry L. Friesz, Tao YaoTransportation 2013 · DOI · arXiv

Introduction

In transportation science, modeling the "morning commute" is a foundational challenge. The goal is to predict how commuters behave when they aim to minimize their individual travel costs—a combination of time spent in transit and penalties for arriving at their destination too early or too late. When no driver can reduce their cost by unilaterally changing their route or departure time, the system reaches a state known as Dynamic User Equilibrium (DUE).

While the concept of DUE is intuitive, providing a rigorous mathematical proof of its existence in a continuous-time framework has historically been difficult. This paper, published in Transportation Research Part B, provides the first formal proof for the existence of a Simultaneous Route-and-Departure Choice Dynamic User Equilibrium (SRDC-DUE) without relying on artificial constraints. By leveraging the Generalized Vickrey Model (GVM), the authors establish a solid theoretical foundation for the dynamic traffic assignment (DTA) models used in modern urban planning.

The Theoretical Challenge: The "Math Monster"

Proving equilibrium in continuous time—where traffic is treated as a fluid flow rather than discrete vehicles—presents a significant hurdle: the set of all possible traffic flows is "non-compact" in the functional spaces typically used by mathematicians. To circumvent this, previous research often relied on "a priori" bounds, essentially assuming an arbitrary maximum flow rate existed to make the math work.

This paper seeks to move beyond these artificial assumptions. The authors aim to prove that equilibrium exists based solely on the physical properties of the network and the behavioral logic of the drivers. The core challenge lies in proving that the mathematical operators describing traffic delay are well-behaved enough to guarantee a solution.

Methodology: The Generalized Vickrey Model

The authors utilize the Generalized Vickrey Model (GVM) as the primary framework for their proof. Unlike the classic Vickrey bottleneck model, which can be mathematically unstable due to discontinuous differential equations, the GVM employs a Hamilton-Jacobi reformulation. This approach provides a closed-form method for calculating delays that is continuous and more amenable to rigorous analysis.

To establish the existence of equilibrium, the authors employ several sophisticated mathematical strategies:

  • Infinite-Dimensional Variational Inequalities (VI): The equilibrium problem is framed as a VI, allowing the researchers to search for a specific "point" within a high-dimensional space of functions that represents a steady state where no driver desires to switch paths or times.
  • Topological Approximation: Because the full set of potential flows is too large to analyze directly, the authors construct a sequence of simpler, finite-dimensional approximations of the problem. They then use a limit argument—specifically, weak convergence in Hilbert space—to show that as these approximations become increasingly refined, they converge toward a true equilibrium.
  • Strong Continuity: A pivotal technical contribution of this work is the proof that the "path delay operator" is strongly continuous. This continuity is the essential requirement for applying classical existence theorems to the traffic flow problem.

Key Insights and Results

Natural Emergence of Bounds

One of the most significant findings of the paper is that traffic flow bounds do not need to be assumed; they emerge naturally from the model. The authors demonstrate that because physical bottlenecks have a finite capacity ($M$), the equilibrium behavior of rational drivers will inherently result in bounded flow rates. This bridges the gap between theoretical mathematical requirements and physical reality.

Theorem 5.7: The Existence Proof

The central result of the study is Theorem 5.7, which successfully proves that for any general network with fixed trip demands, at least one SRDC-DUE solution exists, provided the network adheres to the Generalized Vickrey Model. This confirms that the SRDC-DUE is a mathematically sound concept.

Proposition 5.9: The Informative Result

The authors further derive a specific formula for the upper bound of departure rates at equilibrium. They show that the maximum flow rate is a function of the bottleneck capacity, the slope of early/late arrival penalties, and the value of time. This proves that the physical limits of the infrastructure act as a natural regulator for the entire system.

Limitations and Future Research

While this paper provides a landmark proof, it is a purely theoretical contribution and does not include empirical datasets or numerical simulations. Several areas remain open for future exploration:

  • Model Generalization: The proof is specific to the Generalized Vickrey Model. Future work is needed to determine if these results hold for other popular traffic models, such as the Lighthill-Whitham-Richards (LWR) kinematic wave model.
  • Elastic Demand: The current proof assumes a fixed number of trips. In real-world scenarios, demand is often elastic; high congestion may lead some individuals to cancel their trips entirely.
  • Algorithmic Development: Proving that an equilibrium exists is a different challenge than finding it. The next step for researchers is to translate this continuous-time theory into efficient, discrete-time algorithms that can be implemented in urban planning software.

Conclusion

By proving the existence of SRDC-DUE without artificial flow constraints, this paper resolves a long-standing theoretical ambiguity in transportation science. It confirms that the physical constraints of a network and the cost-minimizing behavior of users are sufficient to produce a stable equilibrium, providing a more robust theoretical anchor for the future of dynamic traffic modeling.

Summary updated

BibTeX
@inproceedings{han2013existence,
  author = {Ke Han and Terry L. Friesz and Tao Yao},
  title = {{Existence of simultaneous route and departure choice dynamic user equilibrium}},
  booktitle = {Transportation},
  year = {2013},
  doi = {10.1016/j.trb.2013.01.009},
}

Loading related content...

Figure