Adaptive Fastest Path Computation on a Road Network: A Traffic Mining Approach
Adaptive Fastest Path Computation on a Road Network: A Traffic Mining Approach
复制标题
DOI：
--
复制
发表时间：
2007-09
期刊：
影响因子：
--
通讯作者：
Hector Gonzalez;Jiawei Han;Xiaolei Li;M. Myslinska;J. Sondag
中科院分区：
文献类型：
--
作者：
Hector Gonzalez;Jiawei Han;Xiaolei Li;M. Myslinska;J. Sondag
在大规模道路网络中，变速度条件下的快速路径计算是现代导航系统中的一个重要问题。为了选择符合当前驾驶条件的快速路线，需要考虑影响道路速度的因素，如天气、一天中的时间和车辆类型。大多数现有系统基于道路欧几里得距离和一小组预定义的道路速度来计算最快路径。然而，“历史往往是最好的老师”。历史交通数据或驾驶模式通常比简单的基于欧几里得距离的计算更有用，因为人们必须有充分的理由选择这些路线，例如，他们可能想要避免那些在夜间经过高犯罪率地区或可能遇到事故，道路施工或交通堵塞的路线。在本文中，我们提出了一种自适应最快路径算法，能够有效地考虑从大量交通数据中挖掘的重要驾驶和速度模式。该算法基于以下观察结果：(1)道路的层次可用于公路网络分割成区域,和不同的路径可以使用预先估计策略在区域层面上,(2)我们可以限制搜索策略路由到边缘和路径数据段实际经常旅行,和(3)驱动程序通常通过最大的道路穿越公路网络可考虑到旅行的距离,除非有小路以显著的速度优势大的。通过对真实道路网络的广泛实验评估，我们表明我们的算法提供了理想的（短且支持良好的）路线，并且比竞争方法要快得多。
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 algorithm capable of efficiently accounting for important driving and speed patterns mined from a large set of traffic data. The algorithm is based on the following observations: (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.