Traffic services for vehicles: the process from receiving raw probe data to space-time diagrams and the resulting traffic service

Abstract

Today, large quantities of vehicle data (FCD: floating car data) are widely used by traffic service providers to create and broadcast traffic states in road networks. As a first processing step, all raw position data received from Global Positioning Systems (GPS) have to be map matched in a digital road map. The technical aspects of such a matching process for GPS data are described in this report. After the matching process, space-time-diagrams are created of the probe data showing traffic situation details over space and time. Various examples illustrate how traffic service quality depends on the number of matched GPS raw data; it will be stated that when 2% of connected vehicles in the total traffic flow are sending their GPS data in shorter time intervals, a high quality and precise reconstruction of the current traffic phases is achieved. Traffic reconstruction is followed by a translation into traffic information messages, which can be sent and used in vehicle navigation systems for driver information and dynamic route guidance.

Keywords

floating car data / map matching / three phase traffic theory / traffic reconstruction / traffic service quality / navigation systems

Introduction

Dynamic traffic information is becoming more of a necessity for modern navigation systems in vehicles. Former static navigation with digital maps is becoming outdated, so dynamic traffic information sent to vehicles in short time intervals to cover the whole road network is important. With floating car data (FCD) from moving vehicles themselves, traffic information quality is becoming significantly better. From local roadside detectors, permanent growth of connected vehicles sending their position data to a central traffic center is seen in all markets.

This paper explains the major elements of an IP(Internet)-based traffic service to include the following: (1) vehicles record position data and send it cyclically to the server, (2) the server matches the GPS raw data in a digital road map, (3) the server analyzes space-time diagrams of the entire vehicle fleet data and reconstructs the congested traffic regions on all roads, (4) the server sends aggregated traffic service information back to each requesting vehicle and (5) each vehicle uses the information for dynamic route guidance or other purposes. The descriptions of the map matching (2) and the interpretation process on the server (3) are primarily discussed in this paper.

Map matching

Map matching of GPS raw data are the process of referencing GPS positions to roads and is an important step in the process chain leading to dynamic route guidance. The GPS raw data are generated in each individual vehicle, but the following data processing requires data fusion on a backend server. Therefore, map matching is possible either on-board or off-board. By on-board map matching, a dependency on the vehicle digital map is introduced and, thus, all vehicles must use the same map for further processing on the server. Otherwise, the on-board map matching will give inconsistent results for different vehicles. Despite the advantage of map matching on a large distributed system consisting of a connected vehicle fleet, the processing of GPS raw data are usually accomplished on servers to guarantee the consistency of data fusion. On the server, one version of the digital map is used for both the map matching and the generation of the traffic service in order to avoid inconsistencies.

While matching of trajectories onto the map is immediately obvious for humans, as illustrated in Fig. 1, distinct rules are required for map matching with computers. When trying to find the corresponding roads on the GPS trajectory in Fig. 1, such aspects as the geometry of the road and the topology of the road network should be taken into account. In past, map matching algorithms with varying performance and accuracy have been proposed (^{Quddus et al., 2007}). These algorithms are designed for in-vehicle navigation, and high accuracy is desired. Most of these algorithms are very sophisticated and take additional information into account such as the previous matched positions and the topology of the map. As in the past, the GPS signal quality was magnitudes worse than today, so these algorithms are also capable to address highly inaccurate GPS signals. In 2000, the artificial noise on the GPS signal was turned off, improving the accuracy from approximately 100 m down to 10 m. With the replacement of old satellites by new satellites, the accuracy was further improved. Navigation systems in vehicles additionally use dead reckoning (DR) with information from vehicle sensors.

Spatial index structure for digital maps

Independent from the specific map matching algorithm, only roads in the proximity of the trajectory have to be considered for matching, and all other roads can be excluded with high probability. Due to the accuracy of the GPS signal, it is very unlikely that a vehicle drives on a road that is more than 100 m away from the current GPS position. This makes it necessary to create a spatial index on the roads, as otherwise the distance between all roads and the GPS positions have to be computed. By the creation and usage of a spatial index, the computational complexity of the spatial search is reduced from \mathrm{O}(n) to \mathrm{O}({\log }_m(n)), where n is the number of roads and m is the maximal number of leafs.

There are some options for spatial indexing, such as quadtree, R-tree, and k-d-tree. Each spatial index has specific strengths and weaknesses regarding initial tree creation, tree traversal or insertion of further geometrical objects. As the digital map used for map matching is static, the insertion of new objects into the tree or the rebalancing of the tree is not of importance. While some of the spatial indexes are only suitable for point data, the indexing of the digital map is also applied on polylines. The R-tree developed by ^{Guttman (1984)} can index arbitrary spatial objects via their corresponding minimum bounding rectangle (MBR) as illustrated in Fig. 2. By the structure of the R-tree, it is always guaranteed that the MBR of leafs are within the MBR of the parent node. A Spatial search can be then conducted with a point or the MBR of an arbitrary object. If there is no intersection between the MBR of the search object and the MBR of the parent node, there will also be no intersection with the MBR of the leaf nodes. The efficiency of the spatial search depends on the coverage and the overlap of the MBR of the nodes. While with the initial R-tree coverage and overlap are suboptimal, there exist some R-tree variants with improved splitting heuristics, such as the R*-tree with topological split (^{Beckmann et al., 1990}) and a bulk-loaded R*-tree using Sort-Tile-Recursive (STR) (^{Leutenegger et al., 1997}). As changes in the digital map are not taken into account for map matching, the R*-tree with STR is the preferred spatial index leading to fastest spatial search.

Overview of map matching algorithms

The required properties of a map matching algorithm used for the processing of floating car data (FCD) are performance and accuracy. Furthermore, the algorithm is constrained by the available input data. The trajectory data from FCD systems usually is comprised of a session identifier (session id), timestamp and position. For systems with high sampling frequency (≤10 s), velocity and heading can be derived from position and timestamp. This is not possible for systems with low sampling frequency (≥30 s), and therefore, velocity and heading have to be transmitted. In the following, a selection of important map matching algorithms is presented.

Geometrical map matching algorithms

There exist some variants of the geometrical map matching results summarized by ^{Bernstein and Kornhauser (1996)}. In a very simple variant, each GPS position is matched to the closest node of the digital map (Point-to-Point matching). This simplification can be avoided with Point-to-Curve matching, where a GPS position can also be matched on an edge as shown in Fig. 3. By the application of a weighting scheme taking the heading also into account, the accuracy can be further improved (^{Greenfeld, 2002}; ^{Quddus et al., 2003}).

The shortest distance d between a GPS point and a line segment as shown in Fig. 3 can be either the distance from one endpoint of the line (in this case bp) or the perpendicular distance (pp'). The heading difference \varphi is for one way edges in the range of [−180°, 180°] and for all other edges in the range of [−90°, 90°].

Combining distance d in m, velocity v in km·h^-1 and the heading difference \varphi in deg of the obtained candidate edges to one metric gives the criterion c.

where v_{\min } is a threshold level for the velocity in km·h^-1. At velocities below v_{\min }, the vehicle heading cannot be derived correctly from two subsequent GPS positions due to the inaccuracy of the GPS signal. For FCD systems with a high sampling frequency, a threshold velocity of 10 km·h^-1 is appropriate and gives good matching results (^{Quddus et al., 2003}). The criterion c is similar to the weighting schemes proposed by ^{Greenfeld (2002)} and ^{Quddus et al. (2003)}.

Topological map matching algorithms

With geometrical map matching algorithms, each GPS position is matched independently of the matching results of previous or following GPS positions, whereas topological map matching algorithms take all available information into account. Due to the topology of the digital map, a vehicle can move only from one road to another road, if there is also a connection between the roads. Especially at on- and off-ramps as well as junctions, geometrical map matching cannot provide distinct map matching results.

The GPS position P_{\mathrm{2}} in Fig. 4 cannot be matched distinctly to one of the roads in proximity using geometrical analysis only. By considering the matching results of the GPS positions P_1 and P_{\mathrm{3}} together with the topology of the digital map, the matching of Point P_{\mathrm{2}} becomes distinct. The points P_{\mathrm{1}} and P_{\mathrm{3}} are matched on the roads ab and bc. Due to the topology, the road bd can be excluded as candidate and GPS point P_{\mathrm{2}} is matched correctly on road bc.

A basic map matching algorithm incorporating topological analysis is presented by ^{Bernstein and Kornhauser (1996)}. Bernstein and Kornhauser stated that topological map matching algorithms lead to more accurate results than with geometrical analysis only. ^{Greenfeld (2002)} and ^{Quddus et al. (2003)} apply a local look ahead in order to take advantage of map topology. ^{Brakatsoulas et al. (2005)} proposed a global map matching algorithm using the Fréchet distance. Newson and Krumm (2009) introduced the concept of Hidden Markov Models (HMM) into map matching algorithms. Implementations based on HMM are accurate, scalable and fast and are therefore widespread (barefoot, graphhopper, mapillary).

Space-time diagrams

With the map matched data presented in the previous section, traffic researcher and traffic service providers are able to derive information about the historical and real-time traffic condition. Essentially, the map matching of trajectories to the underlying street network enables the ability to reconstruct precisely the traffic states on observed sections of a road. This approach provides insights to improve traffic management, (highly) automated driving and reliable control and optimization of traffic and transportation networks. A common way to visually show the traffic state is space-time-diagrams. In this section, the process of turning map matched FCD (floating car data) into space-time-diagrams is presented and a brief interpretation of given examples is provided.

Treiterer et al. researched the first application of space-time diagrams (1974; 1975). They observed traffic from aerial photography and reconstructed the traffic by tracking vehicles with computer vision techniques. The results show the time-space diagram on a short highway section. Time-space diagrams show the trajectories (i.e., the position at any given time) of cars on the observed road. They reveal the physical nature, structure and characteristic parameters of a traffic jam. The low velocity wave propagating through the traffic can project the first patterns.

After the matching process, the vehicle probe data are spatial-temporally related to a specific road stretch. Therefore, each single vehicle trajectory can be plotted over space and time. The three-phase traffic theory (^{Kerner, 2004; 2009}) is followed and the following general abstract diagram is drawn: over time, each vehicle has an individual speed profile (top of Fig. 5). If the same vehicle trajectory over space and time (bottom of Fig. 5) is drawn, the vehicle has passed two congested traffic phases of Kerner’s theory: (1) wide moving jam and (2) synchronized flow region.

In general, the three-phase theory can be qualitatively defined as follows: (1) free flow is characterized by high vehicle velocities, higher flow rates and the free driving and overtaking of the vehicles, (2) synchronized flow regions have lower vehicle speeds between approximately 25 and 70 km·h^-1 on freeways without speed limits but higher traffic flow rates and (3) the wide moving jam phase shows in measurements almost no more vehicle speeds and very low flow rates. It is important to mention that a correct classification of the phases can be done only based on space and time analyses (Fig. 6).

After successful matching of the GPS data of vehicles, space-time diagrams for different road stretches and the related GPS raw data can be shown. In the next examples the GPS data are colored according to the following legend: (1) red: 0–25 km·h^-1, (2) yellow: 25–60 km·h^-1 and (3) green:>60 km·h^-1. The given color scheme is appropriate for freeways, and the values for other road classes, such as urban roads, have to be adapted to the usual driven velocities. Examples are shown from freeway segments in Germany and UK. In all cases, based on the qualitatively coloring, the regions of the three traffic phases can be identified. The congestion similarities in different countries based on GPS raw data diagrams show similar results as earlier investigations based on detector data (Rehborn et al., 2011).

The anonymized data are obtained from connected vehicles of a large fleet from real world customers driving on the public road network. These vehicles send GPS locations with a timestamp and session identifier to a secure backend for transfer to the traffic service provider (TSP). The TSP then delivers precise and latest traffic information such as traffic jams, dangerous end of jams and temporary road closures to the connected vehicles. The data comprises the raw GPS location that after map matching and represents a trajectory on the given road section. Depending on the vehicle model and variant coding, the data have a sampling rate of either 5 or 10 s.

Figure 7 shows the highway section A8 coming from Kirchheim, passing the city of Stuttgart going toward Pforzheim. Marked on the side are bottlenecks that heavily influence the traffic. The usual traffic patterns at peak hours from people coming (06:30 h to 10:00 h) to work and leaving for home (16:00 h to 20:00 h) can be seen at Kreuz Stuttgart, which is a major intersection on this highway. The bottleneck at Esslingen shows that two large mega jams evolved after an accident.

In Fig. 8, the map matched raw GPS data are shown for the M4 going toward the center of London. As with the A8 section in Germany, major jams occur during the peak hours coming and going to work, so similar traffic patterns are observed.

It is clear that with more data, the traffic reconstruction precision increases. The figures support a qualitative judgment that with approximately one GPS probe per minute (i.e., approximately 60 connected vehicles per hour or an approximate 1% penetration rate of the total traffic flow for a three lane freeway with 6000 veh·h^-1 in peak times) the average quality is sufficient for a traffic service.

Traffic service quality

A general goal of a traffic information service following requests from a customer perspective is to show all congestion (hit rate) and not show congestion that is not present (false alarms).

One approach is a microscopic Kerner-Klenov-traffic simulation (^{Kerner, 2004}) to simulate a traffic pattern with congestions based on vehicle data only. Figure 9 (taken from Kerner et al., 2011) shows a traffic state recognition based on Kerner’s three phase traffic theory based on different percentages of sending (“equipped”) vehicles.

The propagating wide moving jams are clearly visible based on 2% FCD probes. With 0.5% (Fig. 9(b)), the propagating structure is still detectable, but the regions of synchronized flow are less precise.

Based on 0.25% of the FCD percentage, even the propagating wide moving jams become relatively imprecise. As a consequence of this approach, detailed structure of traffic congestion can be reconstructed with 2%; at 0.5%, travel (and delay) time estimation is feasible. Below that, the traffic service quality decreases to a lower quality level and approaches random traffic message generation. Therefore, the number of FCD over space and time is one of the key issues for traffic service quality.

Several details of the traffic reconstruction using GPS data are described in ^{Kerner et al. (2013)}: the congested phase regions can be reconstructed based on sufficient GPS data. For the traffic service, the reconstructed congested regions are translated into the following traffic message protocols: TMC (Traffic Message Channel) or TPEG (Transport Protocol Expert Group), which are two technical options to transfer traffic information from a traffic center to a navigation system in a vehicle. Figure 10 shows the traffic messages in the TMC protocol using the raw GPS data shown in Fig. 7. The colored lines indicate the average vehicle speeds within the traffic congestions with lower speeds with more and darker red. The length of these lines corresponds to the length of each related TMC traffic message. The smaller bullets indicate the beginning and end of the upstream and downstream position of the related TMC event messages: (1) red indicates the stationary traffic, (2) yellow indicates the dense traffic message and (3) blue indicates queuing traffic events. From a customer perspective, the navigation system shows the traffic message with both event information (stationary, queuing or dense traffic) and each length of the congestion. This is in very good correlation to the GPS raw data (Fig. 7), and each user received precise traffic information in his system. The TMC traffic message averages the traffic phases to one length; therefore, for an individual driver on a specific lane, the speed might differ. Overall, based on the TMC message, the delay and arrival times can be calculated in the navigation systems.

Beyond the current traffic situation, predicted information is a next step to enhance customer quality. Algorithms and technologies are already known (^{Rehborn and Klenov, 2009}), and with the increase of GPS data and its archiving, the prediction capabilities will become more ready for market introduction such that a customer route is, in principle, a trip into the future and predicted traffic information is of very high usefulness for navigation systems.

Conclusions

This article reveals the process of obtaining raw GPS data from vehicles that have to be matched onto a digital map on a central server. The report describes features based on space-time diagrams and reveals how to distinguish between different traffic service qualities. Based on large fleet data in different European countries, the two congested phases of Kerner’s three phase traffic theory, i.e., synchronized flow and wide moving jams, can be qualitatively identified in space time diagrams as regions colored in yellow and red, respectively.

With the availability of larger connected vehicle fleets sending their GPS position data, a necessary high probe density of approximately 2% is possible that allows very high traffic information quality.

A traffic service using traffic message protocols, such as TMC and/or TPEG, makes it possible to transfer precise congestion information into vehicle navigation systems. The dynamic route guidance as well as the driver information is based on high quality information, if a sufficient number of FCD is available on all stretches of a road network.

References

[1] Beckmann N, Kriegel H P, Schneider R, Seeger B (1990). The R*-tree: An Efficient and Robust Access Method for Points and Rectangles. Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data

[2] Bernstein D, Kornhauser A (1996). An Introduction to Map Matching for Personal Navigation Assistants. Newark, New Jersey: New Jersey TIDE Center

[3] Brakatsoulas S, Pfoser D, Salas R, Wenk C (2005). On Map-Matching Vehicle Tracking Data. 31st International Conference on Very Large Data Bases (VLDB2005) Proceedings, 853–864

[4] Greenfeld J S (2002). Matching GPS observations to locations on a digital map. Proceedings of the 81th Annual Meeting of the Transportation Research Board, Washington D.C.

[5] Guttman A (1984). R-trees: a dynamic index structure for spatial searching. Proceedings of the 1984 ACM SIGMOD international conference on Management of Data, 47–57

[6] Kerner B S (2004). The Physics of Traffic. Berlin & New York, Springer

[7] Kerner B S (2009). Introduction to Modern Traffic Flow Theory and Control. Berlin & New York, Springer

[8] Kerner B S, Rehborn H, Palmer J, Klenov S L (2011). Using probe vehicle data to generate jam warning messages, Traffic Engineering and Control, 2011–3

[9] Kerner B S, Rehborn H, Schäfer R P, Klenov S L, Palmer J, Lorkowski S, Witte N (2013). Traffic dynamics in empirical probe vehicle data studied with three-phase theory: Spatiotemporal reconstruction of traffic phases and generation of jam warning messages. Physica A, 392(1): 221–251

[10] Leutenegger S T, Lopez M A, Edgington J (1997). STR: A simple and efficient algorithm for R-tree packing. Proceedings of the 13th International Conference on Data Engineering, IEEE, 497–506

[11] Newson P, Krumm J (2009). Hidden Markov map matching through noise and sparseness. In: Proceedings of the 17th ACM SIGSPATIAL international conference on advances in geographic information systems, ACM, 336–343

[12] Quddus M A, Ochieng W Y, Zhao L, Noland R B (2003). A general map matching algorithm for transport telematics applications. GPS Solutions, 7(3): 157–167

[13] Quddus M A, Ochieng W Y, Noland R B (2007). Current map-matching algorithms for transport applications: State-of-the art and future research directions. Transportation Research Part C, Emerging Technologies, 15(5): 312–328

[14] Rehborn H, Klenov S L (2009). Traffic Prediction of Congested Patterns. Encyclopedia of Complexity and System Science. Ed. R. A. Meyers, 9500–9536

[15] Rehborn H, Klenov S L, Palmer J (2011). An empirical study of common traffic congestion features based on traffic data measured in the USA, the UK, and Germany. Physica A, 390(23–24): 4466–4485

[16] Treiterer J, Myers J A (1974). in Procs. 6th International Symposium on Transportation and Traffic. Theory, Ed. D. J. Buckley. (A.H. & AW Reed, London), 13–38

[17] Treiterer J (1975). Investigation of Traffic Dynamics by Aerial Photogrammetry Techniques. Ohio State University Technical Report PB 246094, Columbus (Ohio)

RIGHTS & PERMISSIONS

The Author(s) 2017. Published by Higher Education Press. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0)