Solving the step-tolled bottleneck model with general user heterogeneity

Hongyu Chen, Yang Liu, Yu NieTransportation 2015 · DOI

TL;DR

This paper introduces two novel numerical methods, a semi-analytical approach and an exact method, to solve the complex step-tolled bottleneck model with general user heterogeneity. These methods provide a more accurate way to analyze traffic congestion and design optimal tolling strategies by accounting for diverse commuter behaviors, which previous models often simplified.

What Problem Does This Paper Address?

Commuting behavior, particularly during rush hour, is often modeled using the bottleneck model, where commuters aim to minimize their total cost (travel time, waiting, and schedule delays). A key policy tool to manage congestion is congestion pricing, with step tolls (constant tolls over discrete time intervals) being more practical than continuously varying tolls. However, a significant challenge in this field is accurately modeling "user heterogeneity" – the fact that commuters differ in their desired arrival times, their value of time, and their sensitivity to early or late arrivals. Previous studies often simplified these differences, leading to potentially suboptimal policy designs. This paper addresses the need for methods that can handle general user heterogeneity in the context of step-tolled bottleneck models, aiming to provide more realistic analyses and inform better toll design.

Methods

The paper proposes two main methods:

  • Semi-Analytical Method: This approach transforms the step-tolled user equilibrium problem into an equivalent static, asymmetric traffic assignment problem. This is then formulated and solved as a variational inequality problem (VIP). The method leverages the properties of VIPs to establish existence and uniqueness results and employs a specialized algorithm with nested loops to solve it efficiently. The key innovation here is adapting existing VIP formulations to handle the discrete nature of step tolls and general user heterogeneity.
  • Exact Method: This method aims to find the precise equilibrium solution by enumerating all possible combinations of user departure orders. To make this computationally feasible, a heuristic version is developed. This heuristic guides the search by identifying and addressing violations of equilibrium conditions. While the brute-force enumeration is theoretically sound, the heuristic is the practical implementation, offering a way to navigate the vast solution space.

Datasets

Not discussed in the paper. The paper focuses on developing and testing methodologies using simulated scenarios rather than real-world datasets.

Key Insights and Ideas

  • Ignoring Heterogeneity is Costly: The study strongly suggests that assuming homogeneous users can lead to significantly suboptimal toll designs and overestimation of system costs. This highlights the critical importance of accounting for diverse commuter behaviors.
  • Semi-Analytical Method's Efficiency: The semi-analytical method is found to be remarkably efficient, outperforming the heuristic exact method by an order of magnitude, while still producing nearly identical results. This suggests it's a strong candidate for practical applications.
  • Heuristic Exact Method's Practicality: Despite the theoretical complexity of enumerating all possibilities, the heuristic version of the exact method proves to be a robust and practical approach for finding the correct equilibrium solution, even for large-scale problems.
  • Step Tolls and Heterogeneity Interaction: The paper demonstrates that the effectiveness of step tolls is significantly influenced by user heterogeneity, and a toll designed for homogeneous users may perform poorly for heterogeneous ones.

Key Results

  • The semi-analytical method is consistently more efficient than the heuristic exact method, by roughly an order of magnitude, across various scenarios.
  • Both methods produce nearly identical equilibrium solutions, validating their accuracy.
  • Numerical experiments with up to 1000 classes show that the computational effort for both methods increases super-linearly with the number of classes.
  • The performance of the semi-analytical method is more sensitive to the specific step toll scheme compared to the heuristic method.
  • In a two-class example, a system optimal toll designed for an aggregated (homogeneous) population reduced total cost by 25% in theory, but only by 12.6% when applied to heterogeneous users, and even made some users worse off.

Limitations and Future Work

  • Computational Complexity: While the heuristic exact method is practical, the brute-force enumeration is computationally prohibitive for larger problems. The semi-analytical method's performance is sensitive to the toll scheme.
  • Future Work: The authors suggest extending the work to develop methods for optimal step toll design under general heterogeneity, which is an ongoing effort. Other potential extensions include incorporating more dimensions of heterogeneity (like discrete desired arrival times) and simultaneous route and departure time choices.

Summary updated

BibTeX
@inproceedings{chen2015solving,
  author = {Hongyu Chen and Yang Liu and Yu Nie},
  title = {{Solving the step-tolled bottleneck model with general user heterogeneity}},
  booktitle = {Transportation},
  year = {2015},
  doi = {10.1016/j.trb.2015.09.005},
}
Figure