Congestion is a major problem in most metropolitan areas and given the increasing rate of urbanization it is likely to be an even more serious problem in the rapidly expanding mega cities. Some well know negative effects of congestion include: 1) the economic losses and quality of life degradation that result from the increased and unpredictable travel times, 2) the increased level of carbon footprint that vehicles idling in congestions leave behind, and 3) the increased number of traffic accidents that are direct results of the stress and fatigue of drivers that are stuck in congestion.

One possible method to combat congestion is provide intelligent traffic management systems that can in a timely manner inform drivers about current or predicted traffic congestion that is relevant to them on their journeys. This this extent, the present paper proposes a scalable, grid-based intelligent traffic information hub that facilitates the manual definition and/or automatic detection of abnormal traffic condition events, e.g., accidents or congestion, and in advance informs drivers about events that will likely be relevant to them on their journey, thereby allowing the divers or their onboard navigation units to alter their paths as needed.

The proposed system achieves the above described functionality through the following methodology. The system, without loss of generality, adopts a grid-based discretization of space, which by changing the resolution of the grid allows the system to scale in terms of it computation cost and the geographical level of detail of traffic information that it manages. The system derives traffic information from the continuous stream of grid-based position and speed reports that it receives from the vehicles. In particular, the system in an online fashion 1) summarizes Current (grid-based) Traffic Flow Statistics (CTFS), i.e., it records for each grid cell g from each neighboring grid cell n, the mean and standard deviation of the speeds of the vehicles that are currently located in g and have entered g from n; and 2) efficiently incorporates the CTFS into compressed Historical (grid-based) Traffic Flow Statistics (HTFS) using incremental statistics. Simultaneously, using a sliding window model, the system also 1) maintains the Recent (grid-based) Trajectories (RT) of the vehicles; 2) extracts Recent (gridbased) Mobility Statistics (RMS), i.e., it records for each destination grid cell d, for each neighboring grid cell n of g, and for each possible source grid cell s, the number of vehicles that (i) are currently in d, (ii) have entered d from n, and (iii) have a RT that has passed through s; and 3) efficiently incorporates the RMS into compressed Historical (grid-based) Mobility Statistics (HMS) using incremental statistics. To capture the temporal variability in traffic flow and mobility patterns at different scales, the system through temporal domain projections maintains day-of-week and hour-ofday based aggregations of HTFS and RMS. Then, the system classifies a grid cell g to be congested from the direction of a neighboring grid cell n if the current mean speed of vehicles that entered the grid cell g from the direction of n is below the normal according to the temporally relevant HFS. Finally, based on the temporally relevant HMS, the system sends out congestion notifications to vehicles that are likely to be effected in the future part of their journey by these congestions, i.e., the system sends out a congestion notification (g,n) to a vehicle v that is currently located in some grid cell s from which the likelihood of v moving to g through n within the prediction horizon is above a user-defined threshold.

Extensive empirical evaluations on large sets of realistically simulated trajectories of vehicles illustrate that the above described methodology and its simple SQL-based implementation in a relational database system is scalable and effective. In particular, the execution time of- and the space used by the system scales linearly with the input size (number of concurrently moving vehicles) and the method’s mutually dependent parameters (grid resolution r and RT length l) that jointly define a spatio-temporal resolution. Within the area of a large city (40km by 40km), assuming a 60km/h average vehicle speed, the system, running on a single personal computer, can manage the described congestion detection and one-minute-ahead notification tasks within real-time requirements for 15 thousand and 2.5 million concurrently moving vehicles for spatio-temporal resolutions (r=62.5m, l=17) and (r=4km,l=2), respectively. Finally, the proposed method, for all spatio-temporal resolutions and prediction horizons, significantly outperforms in terms of notification accuracy the grid-based baseline method, which sends non-directional congestion notifications based on the recent linear movement tendencies of vehicles.