Abstract
Recently, GPS car navigation became popular enough for a significant number of drivers in any large city to be able to potentially send their current GPS positions and velocities to a central traffic-managing server in real time. This data could be used to reconstruct a map of current traffic in the whole city and make predictions for the future, which would be valuable for traffic control, congestion analysis and prevention. The difficulty lying in the traffic reconstruction problem is that the number of cars equipped with a GPS transmitter is a small in comparison with the total number of cars in the road network. Information obtained from GPS transmitters is therefore rare and incomplete, raising the problem of approximating travel velocities from sparse information. In this context, the paper proposes approaches to solving two problems: (1) of reconstruction of routes of the individual cars in a street graph from a temporal stream of its coordinates and (2) of approximating the average velocity on a given street from irregular time series of instantaneous velocities of cars passing through that street. Determining the car's position in the road network is quite expensive computationally when done in a naive way, so we propose a method to speed up the car's localization based on the R-tree data structure [10]. Additionally, a resilient propagation neural network [13] is applied to approximate the average velocity on any edge of a street graph. Our methods were applied to one of the problems announced in the competition organized in June 2010 by Tom-Tom - a company producing automotive navigation systems [15]. The results of experiments show the capacity of our approach to make useful predictions.