Pay Your Trip for Traffic Congestion: Dynamic Pricing in Traffic-Aware Road Networks

Lisi Chen, Shuo Shang, Bin Yao, Jing LiAAAI 2020 · OpenReview

Abstract

Pricing is essential in optimizing transportation resource allocation. Congestion pricing is widely used to reduce urban traffic congestion. We propose and investigate a novel Dynamic Pricing Strategy (DPS) to price travelers' trips in intelligent transportation platforms (e.g., DiDi, Lyft, Uber). The trips are charged according to their “congestion contributions” to global urban traffic systems. The dynamic pricing strategy retrieves a matching between n travelers' trips and the potential travel routes (each trip has k potential routes) to minimize the global traffic congestion. We believe that DPS holds the potential to benefit society and the environment, such as reducing traffic congestion and enabling smarter and greener transportation. The DPS problem is challenging due to its high computation complexity (there exist kn matching possibilities). We develop an efficient and effective approximate matching algorithm based on local search, as well as pruning techniques to further enhance the matching efficiency. The accuracy and efficiency of the dynamic pricing strategy are verified by extensive experiments on real datasets.

Introduction

Urban traffic congestion is a global crisis, leading to wasted time, increased fuel consumption, and higher emissions. Current solutions, like the congestion pricing zones in London or Singapore, are "static" or area-based. They charge a flat fee for entering a specific district during peak hours. However, these methods are blunt instruments: they focus on removing vehicles from "hot areas" but don't account for "balancing the global traffic load." Simply pushing cars out of downtown might just create a bottleneck in the surrounding neighborhoods.

Figure 1: Illustration of multiple users with different route candidates interacting with a congested area in a road network.

The challenge is to find a way to coordinate thousands of individual trips simultaneously to minimize congestion across the entire road network. Mathematically, this is an "NP-hard" nightmare; if $n$ travelers each have $k$ possible routes, there are $k^n$ possible combinations to evaluate—a number that quickly becomes astronomical.

Methodology

The researchers tackle this through a two-pronged approach: a new pricing model and an efficient matching algorithm.

The Pricing Model

Instead of a flat fee, the price of a route is determined by its "congestion contribution." This is calculated using two factors:

  • Congestion Ratio: The current vehicle count vs. the road's maximum capacity.
  • Upgrade Margin: How close a road segment is to "leveling up" its congestion status (e.g., moving from "Green" to "Orange" on a map).

Global Route Matching (GRM)

To avoid the $k^n$ complexity, the authors developed a local-search-based approximation:

  1. Initial Matching: They start by greedily assigning every traveler to their "cheapest" route based on the pricing model.
  2. Route Swapping: The algorithm then iteratively looks at each traveler and checks if swapping them to a different route would lower the global traffic congestion factor.

The "Pre-checking" Pruning Technique

To make this fast enough for real-world use, the authors proved a theorem showing that if two potential routes for a user share a common starting sub-route, the algorithm can skip re-calculating the congestion for that shared portion during a swap. This reduces the computational complexity from exponential to roughly linear ($O(k \cdot n)$).

Experimental Evaluation

The authors evaluated their strategy using two massive, real-world trajectory datasets: Beijing Taxi Trajectories (BT) and New York Taxi Trips (NT). These datasets allowed the researchers to simulate thousands of concurrent trips and test how their algorithm performed under realistic urban conditions.

Key Results

The approximation algorithm performed remarkably well. The global congestion factor produced by their fast algorithm was typically only 1.1x to 1.3x that of the theoretical absolute minimum.

Figure 6: Runtime comparison between the proposed GRM algorithms and the baseline DRM as the number of trips (n) increases.
  • Scalability: While the exact "Direct Route Matching" (DRM) algorithm exploded in runtime as the number of trips increased, the proposed GRM-PC (with pre-checking) handled 5,000 concurrent trips in New York in under a second.
  • Pruning Gains: The pre-checking technique consistently improved runtime performance by 5% to 21% across different scenarios, proving its value for real-time applications.

Conclusion and Future Work

This paper presents a novel approach to traffic management by treating congestion as a social cost. By optimizing for the "socially optimal" set of paths rather than "selfish" shortest paths, the system can keep the whole city moving more efficiently.

While promising, several hurdles remain. The system assumes a centralized coordinator, which is difficult in a market with fragmented ride-hailing platforms. Future work could involve dynamically generating new route candidates as traffic conditions shift and integrating more complex human behavior models into the user acceptance probability.

Summary updated

Abstract

Pricing is essential in optimizing transportation resource allocation. Congestion pricing is widely used to reduce urban traffic congestion. We propose and investigate a novel Dynamic Pricing Strategy (DPS) to price travelers' trips in intelligent transportation platforms (e.g., DiDi, Lyft, Uber). The trips are charged according to their “congestion contributions” to global urban traffic systems. The dynamic pricing strategy retrieves a matching between n travelers' trips and the potential travel routes (each trip has k potential routes) to minimize the global traffic congestion. We believe that DPS holds the potential to benefit society and the environment, such as reducing traffic congestion and enabling smarter and greener transportation. The DPS problem is challenging due to its high computation complexity (there exist kn matching possibilities). We develop an efficient and effective approximate matching algorithm based on local search, as well as pruning techniques to further enhance the matching efficiency. The accuracy and efficiency of the dynamic pricing strategy are verified by extensive experiments on real datasets.
BibTeX
@inproceedings{chen2020pay,
  author = {Lisi Chen and Shuo Shang and Bin Yao and Jing Li},
  title = {{Pay Your Trip for Traffic Congestion: Dynamic Pricing in Traffic-Aware Road Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=QADQBadUSJg},
}
Figure