and incur the extra cost of looking at the upgraded edges only when absolutely necessary.
More formally, an edge e, residing in area a with border edges at level l of the road hierarchy, will be upgraded to level l if three conditions are met (i) the edge speed under driving conditions (d1, . . . , dn) for some time t is faster than the average edge speed of border edges in the area under the same conditions and time, (ii) edge e is at level l + 1, and (iii) the edge is frequent. For all such edges we will reg- ister a conditional road class tuple edge id, t, (d1, . . . , dn) : upgraded class.
Algorithm 2 Edge upgrading
Input: G(V, E): road network, T : area hierarchy, s: speed threshold Output: List of upgraded edges Method:
1: Precompute the average border speed for every area un-
der every valid driving condition and time 2: q ← push all leaf areas in T ; 3: while q not empty do
4: 5: 6: 7:
8: 9: 10:
A ← q.pop(); for each edge e in A do if e.level = A.level + 1 and e is frequent then for each driving condition c and time t for which e.speed > s× average border speed for c in A, make e.level = a.level and output e, t, c, e.level; end if end for q.push(A.parent);
11: end while
Analysis. Algorithm 2 presents the method used to up- grade internal area edges when they are faster than the bor- der. The algorithm starts by computing the average speed of border edges in an area for all valid conditions. This can be done efficiently in a single scan of the list of edges. We then traverse the area tree in a bottom up order, upgrading edges at the lowest areas, before upgrading edges at larger areas. Notice that an edge can be upgraded multiple times if it is consistently faster than the borders of several succes- sively larger areas. During the edge upgrade process each edge is touched O(l) times where l is the number of levels in the tree, so in total we touch at most O(|E| × l) edges.
FASTEST PATH COMPUTATION
In this section we will introduce an approximate fastest path algorithm for road networks, that computes fast paths between a source and destination node, such that the com- puted route has the following properties:
Fast routes should be well supported by the historical driver behavior, i.e., they should contain as many fre- quent driving patterns as possible.
Fast routes between a source and a destination will go through the largest possible roads connecting the two lo- cations as long as there are no smaller roads along the way that have a significant advantage over the large ones.
Fast routes will account for all relevant factors affecting driving speed expected to occur during the trip such as weather, time of day, and road construction status. Before running the algorithm we assume that the following
components have been computed:
The road network G has already been partitioned using algorithm 1, and we have an area hierarchy tree T that encodes the parent/child relationship between areas.
Speed patterns have been mined and we can use the function get edge speed (edge id,t,(d1, . . . , dk)) to get the speed of edge id when it is taken at time t, and for driv- ing conditions (d1, . . . , dk). This information is retrieved from our mined set of rules for driving conditions, by selecting most specific rule(s) applicable given the condi- tions.
Driving patterns have been mined and we can use the function is frequent(edge seq, t, (d1, . . . , dn)) to deter- mine if the edge sequence edge seq is frequent under con- ditions (d1, . . . , dn) at time t.
We have pre-computed a set of area-level fastest paths with high benefit value.
We have used algorithm 2 to upgrade internal roads to an area when they are faster than roads along the area bor- der for a given set of time and driving conditions. We can retrieve upgraded edges with the function get edge class (edge id, t, (d1, . . . , dk)) that returns the class of edge id for driving conditions (d1, . . . , dk) at time t.
At this point we are ready to state our fastest path algo- rithm, it is a variation of A∗, where we dynamically com- pute edge costs, take advantage of pre-computed paths, fol- low edges in ascending/descending order of their level in the road hierarchy, and give priority to frequent edges (or edge sequences).
The key technical contributions of the algorithm are three. First, it incorporates previously neglected factors such as speed and driving patterns into route finding. Second, we improve performance by utilizing a novel area level pre- computation scheme. And third, although hierarchical path finding has been used in the past, to the best of our knowl- edge this is the first study that uses the idea of small road upgrading to improve path quality with minor impact to efficiency.
The key concepts of the algorithm are summarized below:
We maintain a priority queue of expanded paths (repre- sented by the last node of the path), for each path we keep g(n) the current cost (travel time) spent to get from start to n, and h(n) the expected cost to reach the end node from n.
At each step of the search process we pick the node with lowest g(n) + h(n) value that is frequent3, if no frequent node is present in the queue we pick the best infrequent one. We prefer to travel through frequent roads, but sometimes it is necessary to pick a small number of in- frequent paths in order to reach the destination. This is especially true around the starting and ending nodes.
At the beginning of the search we determine, using the area hierarchy tree T , what is the lowest common ances- tors of both start and ending nodes. We use the lowest common ancestor to set the phase of the algorithm, which can be Ascending or Descending. We are in an Ascend- ing phase when the currently examined node is in an
3A more sophisticated strategy is possible, we can give pref- erence to paths that have longer frequent driving patterns, than shorter ones.