A Day-to-Day Dynamical Approach to the Most Likely User Equilibrium Problem

Jiayang Li, Qianni Wang, Liyang Feng, Jun Xie, Yu NieTransp. sci 2024

TL;DR

This paper introduces a novel day-to-day (DTD) dynamical model, CULO, that provides a behavioral foundation for the "most likely" user equilibrium (MEUE) traffic assignment solution. CULO converges to MEUE under specific initial conditions, offering a practical algorithm for finding this unique and stable traffic flow state, which has been a long-standing challenge in transportation research.

What Problem Does This Paper Address?

Traffic assignment aims to predict how drivers choose routes in a network. A key concept is User Equilibrium (UE), where no driver can improve their travel time by unilaterally changing routes. However, a significant problem is that UE is often not unique; multiple route flow patterns can satisfy the UE condition. This ambiguity makes it difficult to justify specific traffic assignments and can lead to unstable predictions. To address this, the "maximum entropy principle" is often used to select the "most likely" UE flow (MEUE), which maximizes entropy among all possible UE flows. While this principle is well-established in statistical mechanics, it has lacked a solid micro-behavioral explanation – meaning, what driver behaviors naturally lead to this MEUE state? This paper seeks to bridge this gap by proposing a DTD model that can generate MEUE flows from realistic driver learning and adaptation processes.

Methods

The core of this paper is the Cumulative Logit (CULO) model, a day-to-day dynamical system. CULO models how travelers learn and adapt their route choices over time. It consists of two main modules:

  1. Learning Module: Travelers update their route valuations based on past experiences, specifically using a cumulative cost rather than just the current cost. This is modeled by the equation $s^t = s^{t-1} + \eta_t \cdot c(p^{t-1})$, where $s^t$ is the route valuation on day $t$, $\eta_t$ is the proactivity parameter (how quickly travelers update their valuations), and $c(p^{t-1})$ is the route cost from the previous day.
  2. Choice Module: Travelers choose routes based on their current valuations using a logit model, $p^t = q_r(s^t)$, where $r$ is the exploration parameter.

The paper then proves that CULO, under certain initial conditions, converges to the MEUE solution. It also proposes an iterative route discovery scheme to overcome the computational burden of enumerating all possible routes, making CULO a practical algorithm. The authors also analyze and compare CULO with other DTD models (best-response, projection, Smith, and replicator dynamics) by discretizing them and evaluating their properties.

Datasets

The paper uses two networks for numerical experiments:

  • 3N4L Network: A small, illustrative network (three nodes, four links) used for initial analysis and demonstrating specific properties.
  • Sioux-Falls Network: A larger, more realistic network (24 nodes, 76 links, 528 OD pairs) used for testing the performance of CULO with route discovery and comparing it with other dynamical models.

Key Insights and Ideas

  • Behavioral Foundation for MEUE: The most significant insight is that the MEUE route flow can emerge naturally from a day-to-day learning process where travelers are not perfectly rational. This provides a behavioral justification for the maximum entropy principle in traffic assignment.
  • CULO's Convergence to MEUE: CULO can converge to the MEUE solution if travelers start with either zero prior information about routes (leading to an equal-distribution strategy) or if their initial route valuations are consistently derived from link-level valuations.
  • KL Projection Equivalence: Running CULO until convergence is mathematically equivalent to performing a Kullback-Leibler (KL) projection of the initial route choice onto the set of UE solutions. This is a powerful theoretical link.
  • Route Discovery as a Practical Solution: The proposed iterative route discovery scheme makes CULO a viable algorithm for finding MEUE solutions in large networks, bypassing the need to enumerate all routes beforehand.
  • Comparison of DTD Models: The study highlights that among several DTD models, only CULO and, to some extent, the replicator dynamic, consistently exhibit properties conducive to MEUE, such as route conservation and proportionality conservation.

Key Results

  • MEUE Affirmation Conditions: Two conditions are identified under which CULO guarantees convergence to the MEUE strategy:
  • Condition (A): Starting with an equal-distribution initial strategy (zero prior information).
  • Condition (B): Starting with initial route valuations derived from link-level valuations (satisfying the general proportionality condition).
  • Algorithm 2 Performance: The revised CULO model with link-level cumulative valuations and route discovery (Algorithm 2) successfully converges to a UE strategy. With added random noise for exploration, it can discover all UE routes and achieve a high-quality approximation of the MEUE strategy, as demonstrated on the Sioux-Falls network.
  • Model Comparison: Numerical experiments show that CULO and the projection dynamic are the most robust in terms of trajectory stability (TS) and proportionality conservation (PC). CULO consistently converges to the MEUE strategy regardless of its step size, unlike other models where performance is highly sensitive to step size.

Limitations and Future Work

  • Strict Monotonicity: Proposition 3.9, which provides a general condition for MEUE convergence, relies on the strict monotonicity of the link cost function. This condition is often violated in real-world applications (e.g., constant link costs), limiting the applicability of this specific proposition.
  • Route Discovery Guarantee: While the route discovery scheme in Algorithm 2 is effective, there's no theoretical guarantee that it will discover all UE routes in every scenario. Future work could focus on designing schemes that guarantee finding all UE routes.
  • General Games: The current MEUE affirmation conditions are for standard routing games. Extending these to more general games (e.g., with heterogeneous users or non-separable cost functions) is a significant area for future research.
  • Continuous-Time Models: A deeper theoretical investigation into the discrete versions of continuous-time models (like the replicator dynamic) and their adherence to MEUE properties is warranted.
  • Network Design Connection: The paper suggests exploring the connection between MEUE and network design problems, particularly entropy-based O-D matrix estimation, as a future research direction.

Summary updated

Abstract

The lack of a unique user equilibrium (UE) route flow in traffic assignment has posed a significant challenge to many transportation applications. The maximum-entropy principle, which advocates for the consistent selection of the most likely solution as a representative, is often used to address the challenge. Built on a recently proposed day-to-day (DTD) discrete-time dynamical model called cumulative logit (CULO), this study provides a new behavioral underpinning for the maximum-entropy UE (MEUE) route flow. It has been proven that CULO can reach a UE state without presuming travelers are perfectly rational. Here, we further establish that CULO always converges to the MEUE route flow if (i) travelers have zero prior information about routes and thus are forced to give all routes an equal choice probability, or (ii) all travelers gather information from the same source such that the so-called general proportionality condition is satisfied. Thus, CULO may be used as a practical solution algorithm for the MEUE problem. To put this idea into practice, we propose to eliminate the route enumeration requirement of the original CULO model through an iterative route discovery scheme. We also examine the discrete-time versions of four popular continuous-time dynamical models and compare them to CULO. The analysis shows that the replicator dynamic is the only one that has the potential to reach the MEUE solution with some regularity. The analytical results are confirmed through numerical experiments.
BibTeX
@article{li2024day,
  author = {Jiayang Li and Qianni Wang and Liyang Feng and Jun Xie and Yu Nie},
  title = {{A Day-to-Day Dynamical Approach to the Most Likely User Equilibrium Problem}},
  journal = {Transp. sci},
  year = {2024},
}
Figure