24-08-2012, 10:26 AM
TRAVEL TIME ESTIMATION BASED ON INCOMPLETE PROBE CAR INFORMATION
1TRAVEL TIME ESTIMATION.doc (Size: 161.5 KB / Downloads: 27)
ABSTRACT
Different technologies and methods can be used for the generation of real-time traffic information based on Floating Car Data (FCD) technology. In many cases the probe car information consist a more or less time gap between the available position data of the vehicle. However, if the distance between the available positions is too large then the route between these positions is not unique and has to be estimated.
In this paper we propose a method of a “smart OD router” who improves spatial precision and travel time estimation significantly for incomplete probe car information.
INTRODUCTION
Real-time traffic information based on Floating Car Data (FCD) technology can be generated by different technologies and methods [1, 2]. During the past decade an increasing number of commercial and private vehicles have been equipped with Global Positioning System (GPS) devices. Many research projects have been implemented using these vehicles as probe-cars, to determine traffic status and to provide traffic information. This concept is called Floating Car Data (FCD) supplying valuable basis data on actual traffic conditions. Good results for incident detection and travel time estimation require a vehicle tracking interval of 15-60 seconds in urban areas [3].
However, in many cases probe car information is incomplete because the probe car information consist a more or less time gap between the available position data of the vehicle (e.g. the communication links between traffic centre and probe cars lack bandwidth). If the distance between the available positions is too large then the route between these positions is not unique and has to be estimated. Frequently only location and time stamp of trip origin and destination (i.e. O-D matrix) are available.
Furthermore, calculating mean speed for a longer section could lead to imprecise speed information on the individual road elements. This is particularly the case when the estimated path contains different types of streets, with both low and high free (or normal) speeds. In this case the speed of the street with low free speed can be overestimated and at the same time, the speed on a highway can be underestimated by the average speed.
Consequently, it is important to use a method to correctly estimate the whole route and to estimate travel times on smaller sections in case of incomplete probe car information. The method of estimation is the subject of this paper: it explains the application of a “smart OD router” and shows examples that this method improves spatial precision and travel time estimation significantly.
METHOD
The road network is represented by a digital map, a graph consisting of nodes and edges. The positions of the probe cars are assigned to an edge of the graph by a map-matching algorithm [4]. The graph can have several attributes assigned to its edges. If the route of the probe car between two subsequent position data is not unique then a shortest path algorithm based on the length attribute of an edge can be used (e.g. that of Dijkstra [5]). Several other edge attributes can be also used for the route estimation, like e.g. type of street (e.g. main or minor street) and historical travel frequency. Furthermore, the curves can be also represented; the left curve could have a higher resistance, for example. In transport modelling literature, using certain labels assigned to roads for estimation of route choice is referred to as labelling approach.
NUMERICAL RESULTS
First, the quality of the shortest path OD router is evaluated based on taxi reference routes in Vienna from the FLEET [3] project. The probe cars deliver exact GPS position information in a time interval of 15 seconds. The performance of the algorithms is illustrated analysing 3600 taxi trips on two days (Sunday and Monday) in June 2005.
Table 1 presents the results how the proposed methods improve the quality of the routing: preferring main streets (v85), resisting curves, assigning dynamic meta-length, applying length-filter. Seven configurations have been considered. Using a shortest path routing algorithm (configuration 1) based on the origin and the destination of a taxi trip the route overlap is about 52% and the average route deviation is about 294 meters.
Applying the first 3 improvements (configuration 5), the average overlap (Av.Overlap) increases to 60,49%. By setting the length filter to 2000 metres (see Table 1, configuration 7), the overlap increases to almost 80% percent; however, the sample rate decreases to 10.5% since most routes are filtered out in this case. The average (Av. Dev) and the variance (Var. Dev.) spatial deviation also decrease to a fraction compared to the original router.
CONCLUSION
In this paper the following results have been presented:
(1) The necessity of improving route estimation between two position data (O-D) in case of incomplete probe car information has been defined.
(2) 3 quality parameters to measure quality of the estimated path have been defined (if a reference path is available).
(3) An improved routing algorithm has been proposed, which estimates driver behaviour better than the often used shortest path algorithm adapting itself to the behaviour of the reference trips.
(4) This smart OD router ensures an improvement of routing quality: route overlap is increased to about 80% instead of 52%, while route deviation is reduced to about 17 meters.