X hits on this document





6 / 12

planning algorithms, and that cannot be derived by looking at just distance and edge speeds.

Driving patterns can be derived from the traffic database by using frequent pattern mining [1, 15, 23]. We can define a minimum support level, and go through the traffic database identifying frequent edges, and when we have access to in- dividual vehicle data, longer frequent path segments can be mined. The problem with this approach is that a uniform minimum support level is difficult to define, and it may fil- ter many important local roads, or may keep infrequently traveled high-level roads.

We propose a frequent pattern mining method guided by the area and road hierarchies: Frequent edges are mined at the area level, using a minimum support relative to the traffic volume of each edge class in the area. This will allow us, for example, to distinguish support for edges at different levels of the road hierarchy.

With driving pattern mining, each edge (or path segment) in the road network can be marked as frequent or infre- quent given a time interval and a set of driving conditions (d1, ..., dk). The path-finding algorithm will use this infor- mation to guide the search mostly through frequent edges, and only expand infrequent ones when absolutely necessary (e.g., usually at the start or end of a road when we may need to go into nearby neighborhoods).



In this section we will present two techniques aimed at improving the performance both in terms of run time and path accuracy of fastest path algorithms by the utilization of two techniques. The first is area level pre-computation of stable paths in order to improve efficiency. The second is to upgrade certain small but very fast roads to a higher level in the road hierarchy in order to improve the accuracy (path duration vs. best possible path duration) of the algorithm.


Area level pre-computation

Many fastest path algorithms rely on pre-computing a small set of fastest paths in order to improve performance [19, 5, 26]. At one end of the spectrum we can use algorithms such as Floyd Warshall [9] that pre-compute the shortest path between every pair of nodes. In this case fastest path queries can be answered in O(1) lookups, but we need O(n2) space for storing those pairs, and O(n3) time for the initial computation. At the other end of the spectrum we can per- form no pre-computation and dynamically find the shortest path using an algorithm such as A[16]. In between these two extremes we have several algorithms that do hierarchi- cal decomposition of the original graph, and pre-compute a subset of paths that are helpful in connecting different areas in the graph [19, 5].

Most methods that do fastest path pre-computation as- sume that there is a unique path (or several but equally attractive, and thus undistinguishable) between any two nodes. When edge speed is a function of factors such as time, weather, or road conditions, the fastest path between two nodes may be different for different times and condi- tions, e.g., it may differ when we leave at 8:00 am than at 10:00 am, or if we have to drive through icy roads or dry roads. In the presence of variable edge speeds, pre-computed fastest paths need to be annotated with the set of conditions under which they are valid.

Definition 6.1. We say that fastest path p between nodes


(s, e) is conditionally stable for starting time interval t1, t2given condition c = (d1, . . . , dn), where each di is a value for factor Di or the special value * to indicate any value for Di is valid, if duration(p) is minimal among all possible paths between (s, e), when the starting time is between t1 and t2, and when condition (d1, . . . , dn) is forecasted for all edges along paths connecting s and e.

The benefit of pre-computing a path between two nodes is proportional to the number of path queries for which the path can be used to speedup the fastest path algorithm. We can check two conditions to determine benefit. First, how many fastest path queries will go through nodes of the pre-computed path. For example, pre-computing the fastest path between two houses in an area has little value, as it will likely help a single query, while pre-computing a path be- tween two important intersections may benefit many queries. Second, how stable is the path, i.e., for how long, and for how many speed patterns is the path a fastest path. For example, pre-computing a path that is valid only between 10:07am and 10:11am has less value than pre-computing a path that applies for the entire rush hour interval, 8:00am

  • -

    10:00am. A sensible strategy is thus to pre-compute high

benefit value paths.

A naive method to determine what paths to pre-compute would be to list every fastest path in the road network, un- der every possible condition, and rank them according to benefit value. This strategy would yield optimal results but it is clearly unfeasible as the number of paths and condi- tions to consider is enormous. We propose an area level pre-computation strategy where we compute certain fastest paths only within the nodes inside the area. We first define a minimum level lm in the area hierarchy at which path pre- computation will be conducted. Within each area at level lm we choose the set of nodes Sp of class lm + 1 (one level smaller than the borders of the area), and class lm, and pre- compute fastest paths between nodes in Sp. For this step, we guide our pre-computation by the set of speed rules mined for the area, and limit the analysis paths involving edges with few speed rules. We can handle time intervals by using the algorithm presented in [20], which efficiently computes the set of fastest paths between two nodes for different time intervals.


Small road upgrades

The main assumption of hierarchical path finding algo- rithms is that drivers take the largest road available in or- der to reach their destination, and thus the search space for route finding can be significantly reduced. Our observation is that although this strategy is generally true, there is an important exception, if there is a small road that is faster than a large road, people will take it. For example, people driving to or from cities usually do it through highways, but during rush hour highways can become so congested that taking smaller roads yields shorter travel times. If we ig- nore such cases we may incur significant error.

Our strategy in dealing with this problem will be to up- grade certain edges inside an area if under some driving con- ditions they have a significantly higher speed than the edges at the area borders under the same driving conditions. For the above example, we would upgrade the internal edges in the area where the city resides, to the level of highways but only for the driving condition of rush hour. This way we can still compute most routes considering only highways,

Document info
Document views16
Page views16
Page last viewedSat Mar 12 14:46:47 UTC 2016