Adaptive Fastest Path Computation on a Road Network: A Traffic Mining Approach∗
Hector Gonzalez, Jiawei Han, Xiaolei Li, Margaret Myslinska, John Paul Sondag Department of Computer Science University of Illinois at Urbana-Champaign
Efficient fastest path computation in the presence of varying speed conditions on a large scale road network is an essential problem in modern navigation systems. Factors affecting road speed, such as weather, time of day, and vehicle type, need to be considered in order to select fast routes that match current driving conditions. Most existing systems compute fastest paths based on road Euclidean distance and a small set of predefined road speeds. However, “History is often the best teacher”. Historical traffic data or driving patterns are often more useful than the simple Euclidean distance-based computation because people must have good reasons to choose these routes, e.g., they may want to avoid those that pass through high crime areas at night or that likely encounter accidents, road construction, or traffic jams.
In this paper, we present an adaptive fastest path algo- rithm capable of efficiently accounting for important driv- ing and speed patterns mined from a large set of traffic data. The algorithm is based on the following observa- tions: (1) The hierarchy of roads can be used to partition the road network into areas, and different path pre-computation strategies can be used at the area level, (2) we can limit our route search strategy to edges and path segments that are actually frequently traveled in the data, and (3) drivers usually traverse the road network through the largest roads available given the distance of the trip, except if there are small roads with a significant speed advantage over the large ones. Through an extensive experimental evaluation on real road networks we show that our algorithm provides desirable (short and well-supported) routes, and that it is significantly faster than competing methods.
∗The work was supported in part by the U.S. National Sci- ence Foundation (NSF) IIS-05-13678/06-42771 and BDI-05- 15813. Any opinions, findings, and conclusions or recom- mendations expressed here are those of the authors and do not necessarily reflect the views of the funding agencies.
Permission to copy without fee all or part of this material is granted pro- vided that the copies are not made or distributed for direct commercial ad- vantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, to post on servers or to redistribute to lists, requires a fee and/or special permission from the publisher, ACM. VLDB ‘07, September 23-28, 2007, Vienna, Austria. Copyright 2007 VLDB Endowment, ACM 978-1-59593-649-3/07/09.
Route planning systems such as MapQuest, MapPoint, or Google Maps have become essential tools for obtaining driv- ing directions. In 2006 MapQuest alone reported that it had computed more than 10 billion routes since the online ser- vice launched in 1996. If we combine routes served by other websites and routes computed by car navigation systems, the number is much larger. It is only expected to grow as GPS and GIS systems become commonplace on ubiquitous devices such as cell phones. However, it is surprising to find that most route planning services have a very simple model for road speeds: for the most part roads are assumed to have constant speeds determined by their road class (e.g., high- way, interstate, city road, etc.); more recently these systems have started to track average road speeds for certain areas of the country, and when available this information is used to provide faster routes. But even with the use of current speed conditions at some edges, the model does not con- sider a multitude of other factors that are very important in the computation of desirable routes. Let us examine these factors with some illustrative examples.
Example 1 (Importance of driving patterns). Sup- pose you are new to an area and need to drive to a nearby town to catch a flight at the airport. You would like to get to the airport safely and as quickly as possible. If you have the opportunity to ask a local driver on how to drive there, s/he will likely give you a nice and quick route, although it may not be necessarily the quickest. The suggested route, for example, will not send you through a high crime area, or if there is a snow storm, it will avoid the roads that are more likely to become icy and dangerous. Local experts will consider a multitude of important factors that are difficult to explicitly incorporate into a path finding algorithm. We propose that instead of trying to model all such factors ex- plicitly, we mine historic traffic data and learn from the past driving behavior. In our algorithm we give preference to fast routes that have high support, i.e., that are frequently trav- eled, over those, though fast, rarely taken by drivers.
Example 2 (Importance of speed patterns). Suppose as a new comer, you would like to go downtown to work, your experienced locals will suggest to you the best routes by taking into the consideration many factors that influence your driving speed, e.g., the time of departure, weather con- ditions, whether you are qualified to drive on a car pool lane, etc.. These important factors are also neglected by the cur- rent route planning software. Clearly, it is essential to have a new system that can learn from historic traffic data, con- struct a multi-condition-based road speed model, and plan the fastest route adaptively and dynamically.