Fastest-Path Computation
- PDF / 194,702 Bytes
- 5 Pages / 547.087 x 737.008 pts Page_size
- 3 Downloads / 196 Views
Factor Screening Method Screening Method
Fastest-Path Computation D ONGHUI Z HANG College of Computer & Information Science, Northeastern University, Boston, MA, USA Synonyms Fastest route; Driving direction; Shortest paths; Dijktra’s shortest path algorithm; A* algorithm Definition In the United states, only 9.3% of the households do not have cars. Driving is part of people’s daily life. GIS systems like MapQuest and MapPoint are heavily relied on to provide driving directions. However, surprisingly enough, existing systems either ignore the driving speed on road networks or assume that the speed remains constant on the road segments. In both cases, the users’ preferred leaving time does not affect the query result. For instance, MapQuest does not ask the users to input the day and time of driving. However, during rush hour, inbound highways to big cities allow much lower speeds than usual. Therefore, a fastest path computed during non-rush hours, which may consist of some inbound highway segments, may not remain the fastest path during rush hour. Consider a road network modeled as a graph where each node is a road intersection and each edge is a road segment. Let each edge store a speed pattern, e. g., a piecewise-constant function. For instance, in a working day during rush hour (say from 7am to 9am), the speed is 0.3 miles per minute (mpm) and 1mpm at other times of the day. The Time Interval All Fastest Paths (allFP) Query is defined as follows. Given a source node s, an end node e, and a leaving time interval at s, the allFP query asks to
enumerate all fastest paths, each corresponding to a disjoint sub-interval of leaving time. The union of all subintervals should cover the entire query time interval. An allFP query example is: I may leave for work any time between 7am and 9am; please suggest all fastest paths, e. g., take route A if the leaving time is between 7 and 7:45 and take route B otherwise. It is also interesting to solve the allFP problem with an arrival time interval. For instance: I need to drive from my home to New York International Airport. Please suggest all fastest paths if the anticipated arrival time is between 5pm and 6pm. There are two characteristics that distinguish the allFP problem from other shortest/fastest path problems. • The query is associated with a leaving/arrival time INTERVAL, not a time instant. In fact, if the leaving time were fixed as a time instant, many existing algorithms could be applied, such as the Dijkstra’s shortest path computation and the A* algorithm. • Time is continuous. If time were distinct, e. g., one can only leave precisely at the top of the hour, one could run existing time-instant algorithms multiple times. Historical Background Most existing work on path computation has been focused on the shortest-path problem. Several extensions of the Dijkstra algorithm have been proposed, mainly focusing on the maintenance of the priority queue. The A* algorithm [8] finds a path from a given start node to a given end node by employing a heuristic estimate. E
Data Loading...
