TASR: A Novel Trust-Aware Stackelberg Routing Algorithm to Mitigate Traffic Congestion

Introduction

The paper presents a novel approach to Stackelberg routing called Trust-Aware Stackelberg Routing (TASR) which accounts for probabilistic compliance of travelers based on their trust in the system's route recommendations. Traditional Stackelberg routing assumes travelers are either fully compliant or fully non-compliant. However, in reality, travelers exhibit probabilistic compliance depending on their trust in the system.

Most prior work on Stackelberg routing focuses on theoretical guarantees and assumes non-compliant travelers can observe and respond to the path choices of compliant travelers, which is impractical in real-world settings. Some work also assumes all human travelers are non-compliant while autonomous vehicles are compliant, which prevents routing some human traffic flow optimally in cases where humans would accept the system's recommendations.

The key contributions of this paper include:

1. Modeling the interaction between the routing system and travelers as a novel probabilistic-compliance Stackelberg routing game where travelers probabilistically accept route recommendations based on their trust in the system.

2. Developing the novel TASR algorithm to compute trust-aware path recommendations to mitigate traffic congestion.

3. Validating the proposed method on realistic traffic network simulations and demonstrating its superiority over existing Stackelberg routing strategies.

The paper aims to redesign Stackelberg routing to account for stochastic traveler compliance based on known trust probabilities, allowing the system to more effectively route traffic to minimize overall network congestion.

System Model and Problem Formulation

The paper presents a transportation network model represented as a directed graph with nodes as locations and edges as roadways. There are multiple source-destination pairs called commodities, each with a finite demand. The Bureau of Public Roads (BPR) cost function estimates the travel time on each edge based on the edge flow volume.

The total network demand is comprised of N groups of homogeneous travelers with varying levels of trust in the system's path recommendations. The compliant demand group follows the system's recommendations, while the non-compliant group chooses paths based on their prior beliefs to minimize latency.

The system's objective is to provide path recommendations that minimize the total network travel time (congestion). The Stackelberg equilibrium of the game between the system and the network demand is defined as the pair of optimal path recommendations and the corresponding best response paths chosen by the demand groups.

Proposed Algorithm

The paper presents the TASR (Trust-Aware Stackelberg Routing) algorithm for computing approximate best response path recommendations in a network routing game. Key points:

• Computing the optimal Stackelberg routing strategy is NP-hard, so TASR focuses on finding an approximate solution efficiently.

• TASR prioritizes paths with smallest travel time and demand groups with greatest trust. It assigns paths to the most compliant demands first to maximize the probability of recommendations being followed.

• The algorithm first computes the optimal flow assuming all demand is compliant. It then predicts the flow of noncompliant demand acting selfishly.

• Paths are greedily assigned in order of increasing latency to partially-compliant demands, ordered by decreasing trust. Any remaining compliant demand is assigned to unsaturated paths.

• The multi-commodity version prioritizes commodities by largest fraction of noncompliant demand, allowing the system to mitigate selfish path choices.

• Properties of TASR's efficiency ratio compared to the optimal are analyzed. The ratio depends on whether the noncompliant flow is a subflow of the optimal compliant flow.

• Pseudocode is provided for both the single-commodity and multi-commodity versions of the TASR algorithm.

In summary, TASR is an efficient approximation algorithm for the NP-hard problem of optimizing path recommendations in a routing game with varying compliance levels among traffic demands.

V Trust Dynamics

The provided section focuses on how traffic demand groups update their trust in the system after traversing the network. The system is assumed to have previously interacted with each traffic demand group, observed their path choices, and approximated their trust (αi) and prior belief (qi). The optimal path (Pi*) minimizes the expected travel time based on the prior belief.

Given their trust level, the traffic demand group will either accept the system's recommended path (Pi,s) or reject it and choose the optimal path (Pi*). The chosen path is denoted as Pi⊛. After traversing the network, the demand group experiences regret (Bi) for interacting with the system, defined as the difference in travel time between the chosen path and the optimal path.

The trust dynamics are modeled using an equation that updates the trust level (α+) based on the regret. If the regret is non-positive, the trust is increased or remains at the maximum value of 1. Otherwise, the trust is decreased by a fixed step size (ε) or reaches a minimum of 0. The step size can be interpreted as a penalty or reward applied to the trust based on the favorability of the system's recommendations.

Evaluation Methodology and Datasets

The performance of the TASR strategy is evaluated based on network congestion and compared to four prominent Stackelberg routing algorithms (LLF, Scale, Aloof, and ASCALE) on various real-world networks, demand classes, and total demand amounts. Trust is also considered a performance metric.

The algorithms were implemented in Python, and networks simulated include Sioux Falls, Chicago Sketch, and Sydney. Five demand classes with corresponding trust parameters are considered. Modifications were made to the LLF, Scale, ASCALE, and Aloof algorithms for comparison with TASR.

Single-commodity subnetworks of Sioux Falls and Chicago Sketch were used for validating TASR's performance. Average congestion, standard deviation, and runtime were compared for different demand rates. Trust dynamics were also analyzed over repeated interactions.

Multi-commodity versions of Sioux Falls, Chicago Sketch, and Sydney networks were used to study TASR's scalability on more realistic networks with overlapping routes. Average congestion and standard deviation were compared for each algorithm on these networks.

Results and Discussions

The paper compares the performance of the TASR algorithm to LLF, Scale, ASCALE, Aloof, and a baseline CC in single-commodity Sioux Falls and Chicago Sketch networks. TASR results in improved network congestion compared to the alternative algorithms, as it better considers probabilistic compliance of demand groups. The improvement in TASR's performance becomes more apparent as the parameter Δ increases. Efficiency ratios show TASR's clear performance advantage.

In repeated interactions with homogenous demand, trust converges to full compliance faster for TASR than other algorithms. There is a slight trade-off between trust and lower network congestion for TASR. On average, TASR produces comparable updated trust values to LLF, Scale, and ASCALE, and greater trust values than Aloof in single iterations.

Results in the multi-commodity setting are similar to those in the single-commodity setting for networks with lower demand capacities. TASR outperforms comparable algorithms, and this is more pronounced as network size, capacity, and demand scale. The paper presents these findings in tables and figures to illustrate TASR's superior performance.

Conclusion

The paper proposes a novel greedy Stackelberg routing framework to reduce traffic network congestion when travelers probabilistically comply with the system based on their trust. The interaction between the system and diverse traveler demands is modeled as a Stackelberg game. A trust-aware, greedy Stackelberg routing strategy sends path recommendations to travel demands to mitigate network congestion.

The proposed solution's performance gain in reducing network congestion is demonstrated in comparison to LLF, Scale, ASCALE, and Aloof algorithms for networks with different demand capacities and topologies. The impact of each algorithm on the trust of various travel demands is presented in both single-interaction and repeated interaction settings.

Future research will investigate the performance of the trust-aware Stackelberg routing (TASR) algorithm on network congestion in dynamic, repeated interaction settings across various networks. Methods of maintaining traffic demand trust will also be considered to ensure the proposed algorithm can sustain its performance in repeated settings.