Dynamic User Equilibrium with Elastic Demand and Bounded Rationality: Formulation, Qualitative Analysis and Computation

Han Ke, Terry L. Friesz, Tao YaoarXiv 2013 · arXiv

Introduction

In the field of transportation science, the Simultaneous Route-and-Departure Choice (SRDC) Dynamic User Equilibrium (DUE) is a cornerstone for understanding urban mobility. Traditionally, these models assumed a fixed trip table—a static number of travelers for each origin-destination (O-D) pair. However, real-world travel demand is inherently elastic; congestion levels influence whether a trip is made at all. This paper, originally published in Transportation Research Part B, extends the SRDC DUE framework to incorporate both elastic travel demand (E-DUE) and bounded rationality (BR-DUE), where travelers may not always seek the absolute least costly route-and-departure-time choice.

Mathematical Framework: VI and DVI

The researchers formulate these equilibrium problems using the emerging mathematical paradigm of Differential Variational Inequalities (DVI). By treating the problem in continuous time, the authors avoid the discretization errors common in earlier models and provide a more rigorous foundation for dynamic network loading.

The Extended Hilbert Space

To handle the dual nature of the problem—continuous traffic flow over time and discrete total trip volumes—the authors define an "extended Hilbert space." This mathematical construct allows path departure rates (infinite-dimensional) and elastic demand variables (finite-dimensional) to be treated within a single unified vector. This unification is critical for establishing a canonical variational inequality (VI) form, which allows existence results to be established via Brouwer's fixed-point theorem.

Existence Without Artificial Constraints

A significant contribution of this work is the proof of existence for the E-DUE and BR-DUE solutions. Unlike previous studies that relied on artificial mathematical "cheats"—such as assuming an a priori upper bound on departure rates—the authors utilize finite-dimensional approximations to overcome the lack of compactness in continuous-time flow sets. They demonstrate that an equilibrium exists naturally within the flow set, reflecting more realistic traffic behavior where departure rates are governed by the system's internal dynamics rather than arbitrary caps.

Computational Algorithms

The paper introduces three iterative algorithms designed to solve the DVI in continuous time. Each offers a different trade-off between computational speed and mathematical robustness:

  1. Projection Method: This is the most computationally efficient approach. However, its convergence relies on "Mixed Strongly-Weakly Monotonicity," a relatively strict condition requiring certain paths to exhibit highly stable cost-flow relationships.
  2. Self-Adaptive Projection Method: This method improves flexibility by adjusting step sizes dynamically. It relaxes the requirements for convergence to "pseudomonotonicity," making it applicable to a broader range of network conditions.
  3. Proximal Point Method (PPM): The most robust of the three, the PPM can handle "quasimonotone" operators. It works by solving a sequence of regularized, easier-to-solve sub-problems, ensuring convergence even when the underlying traffic physics are less predictable.

Numerical Results and Analysis

The algorithms were tested on the Sioux Falls network, a standard benchmark featuring 24 nodes and 76 links. For the study, the authors utilized 6 O-D pairs and 119 paths.

  • Efficiency vs. Robustness: On the Sioux Falls network, the Projection Method was the most efficient, reaching equilibrium in 469 iterations (approximately 382 seconds). The Proximal Point Method required the fewest iterations (109) to converge, though each iteration was more computationally intensive, leading to a total time of 2,425 seconds.
  • Stability: The Self-Adaptive method, while the slowest (3,810 seconds), provided the most stable and monotonic convergence curve, which is often preferred in complex simulation environments.
  • Solution Quality: The results confirmed that at equilibrium, the perceived travel costs across all utilized routes and departure times were equalized, aligning perfectly with the theoretical inverse demand functions.

Insights and Future Directions

A key theoretical insight in the paper is the link between the dual variables of arrival time and the "adjoint" (co-state) variables in optimal control theory. This connection allows transportation researchers to leverage powerful tools from control theory to solve complex traffic assignment problems.

Despite these advancements, the authors note a persistent challenge: verifying monotonicity in complex, simulation-based traffic models. While they have provided the most general convergence conditions to date, many real-world traffic delay operators may still violate these conditions. Future research is directed toward discovering a new class of operators that can handle non-monotonicity entirely, moving beyond the current "heuristic" applications in general networks where monotonicity cannot be strictly guaranteed.

Summary updated

Abstract

This paper is concerned with two extensions of the simultaneous route-and-departure choice (SRDC) dynamic user equilibrium (DUE) originally proposed by Friesz et al. (1993). The first extension is an SRDC DUE with elastic travel demand, denoted by E-DUE, in which the trip matrix is determined endogenously. The second extension is a bounded rationality SRDC DUE, denoted by BR-DUE, in which travelers do not always seek the least costly route-and-departure-time choice. We propose to analyze and compute these two types of equilibrium models using the emerging mathematical paradigm of differential variational inequality (Pang and Stewart, 2008). As we shall explain, both extensions can be expressed in continuous time as a variational inequality (VI) and a differential variational inequality (DVI). The VI is a canonical mathematical form which allows existence results to be established by means of Brouwer's fixed point theorem (Han et al., 2013c,d). The DVI formulation enables us to reformulate both E-DUE and BR-DUE as fixed-point problems in proper Hilbert spaces, by employing the optimal control theory. We devise two fixed-point iterative algorithms for computing E-DUE and BR-DUE in continuous time followed by some qualitative analysis on the convergence issue. Both algorithms can accommodate a wide range of analytical or simulation-based dynamic network loading submodels. We demonstrate the efficiency and convergence of these algorithms with numerical studies on the Sioux Falls network.
BibTeX
@misc{ke2013dynamic,
  author = {Han Ke and Terry L. Friesz and Tao Yao},
  title = {{Dynamic User Equilibrium with Elastic Demand and Bounded Rationality: Formulation, Qualitative Analysis and Computation}},
  year = {2013},
  eprint = {1304.5286},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1304.5286},
}

Loading related content...

Figure