« Back

Robust route-guidance algorithms using graph analytics on big traffic data

Problem Definition

Advanced Traveler Information Systems (ATIS) aim to provide real-time, traveller and personalized route guidance information to road users. In particular, by continuously monitoring traffic states and executing Dynamic Traffic Assignment (DTA) algorithms, ATIS systems aim to provide car-specific route updates to achieve a particular system traffic strategy. To date, the ability of ATIS systems to considerably reduce traffic congestion has been hindered by the occurrence of traffic disturbances, such as incidents or variations of traffic demand, and the stochastic behavior of travellers.


The growth of Connected Vehicles and the proliferation of smart phones, vehicle sensors, vehicular communication capabilities and participatory sensing, lead to an abundance of high quality data and real-time feedback, with considerable potential for enhancing the ability of ATIS systems to improve the convenience and efficiency of travel. The objective of this research is to investigate the traffic management methods that leverage these sources of rich state information to control the flow of vehicles and the availability of capacity in a road network, in order to achieve system-wide traffic strategies, taking into account the occurrence of traffic disturbances and the stochastic behavior of travellers. 

System Architecture

Approach and Impact

The feedback control loop, describing this objective, is shown above, and can be explained as follows: The proliferation of high quality traffic data and real-time feedback from various sources, provides ATIS systems with real-time information about current traffic conditions, including traffic speeds, congestion, hazards, weather conditions, and traveller route choices, etc. Moreover, it enables evaluating the robustness of the transportation network to traffic disturbances and traveller behavior, by analyzing real-time traffic variations and identifying temporal and spatial patterns, which can be used to recognize the potential bottlenecks in the network and predict the onset of congestion. ATIS systems can use this information and analysis to execute a global DTA algorithm to achieve a robust optimal transportation network performance. The resulting traffic assignment can be achieved by shifting traffic flow from saturated to emptier roads using individually-tailored real-time route guidance information provided to travellers. This should be accompanied with pricing schemes or incentives to influence traveller behavior and promise sustainability. In high congestion cases, where controlling the flow is not enough to satisfy the traffic requests in the network, additional measures, such as dynamically shifting traffic flow directions or limiting the usage of particular lanes/roads to certain classes of vehicles, e.g. High Occupancy Vehicles, might be required by ATIS systems. This analysis would also help provide suggestions to road operators for required road upgrades in the near future to reduce the bottlenecks in the network. The end results will allow travellers to make better decisions, leading to significant reductions of travel time due to the avoidance of congestion, fuel consumption, and greenhouse gases effecting the environment.

Notion of Robust Traffic Assignment

Optimal traffic assignment algorithms, such as System Optimal (SO), achieve optimal travel times under expected conditions, assuming full knowledge of where travellers are and exactly where they want to go. However, the resulting solutions are very sensitive to unexpected disturbances in traffic, such as incidents or variations in demand or in traveller route choices, leading to escalating travel times and deteriorating transportation system performance. In contrast, the goal of robust traffic assignment algorithms is to provide solutions that yield travel times that may be suboptimal under the ideal expected conditions, but that deliver high performance over a range of unexpected traffic disturbances, even achieving better travel times than the optimal algorithms under certain traffic disturbances. This is shown in the picture below where the Total Travel Time (TTT) increase of a robust assignment is far less than that of SO, even with only a 10% reduction in capacity due to an incident. Having a further reduction in capacity or an increase in the demand will make the robust traffic assignment provide the least travel time, compared to both UE and SO.


Traffic Assignment performance in the presence of incidents

Project objectives
  1. To develop metrics to quantify the robustness of transportation networks to traffic disturbances and traveller behavior..
  2. To develop global DTA algorithms that optimize robust transportation network performance, in the presence of traffic disturbances.
  3. To develop closed-loop DTA algorithms for route guidance, optimizing robust transportation network performance, while incorporating varying traveller choices using the feedback from vehicles equipped with communication capabilties.
  4. To develop schemes altering the allocation of road capacities, in order to satisfy the traffic demand 

Outcomes: Open-loop static robust traffic assignment using Network Criticality
  • Formulated a convex optimization problem for a transportation network & minimized network criticality (minNC), where weights are the inverse of travel time
  • Used the metropolitan Toronto highway network for the simulation
  • Compared the resulting Travel Time with that of the static System Optimal (SO) Assignment, which minimizes travel time (minTT)
  • The increase in average vehicle travel time is far lower for the minNC case for both increases in traffic demand and decreases in traffic supply due to incidents (for both minNC and minSO, the original assignment is used and the effect of disturbances with increasing demand and decreasing supply is measured for the whole networks
  • The proposed traffic assignment, minimizing network criticality (minNC), achieves robustness to traffic changes common in transportation networks 

The detailed system model, analysis and results of this work can be found here.




Traffic Assignment in Transportation Networks

Average (0 Votes)

Add Comment Add Comment