Method for computing fastest route on road networks with dynamic traffic information
A method and system that utilizes an admissible heuristic to determine the fastest-path between two points on a road map is disclosed. The method and system are based in part on a set of separators disposed on the map and represented by line segments, either independent or organized into hierarchical tree structures and based on recursive spatial subdivision. A preprocessing step computes a vector of values per road junction based on the separators that is then stored with the map and used to efficiently compute a high-quality heuristic to be used at a query stage. The heuristic scales well to any map size, resulting in a very efficient determination of fastest-path queries between points at all distances. The implementation is economically feasible and the resulting query speeds are significantly faster than other known heuristics and other state-of-the-art systems used for computing fastest-paths on maps.
1. A method for determining a scalable heuristic for fastest path determination on a map, comprising:
constructing in a preprocess step a separator tree and storing the separator tree with a network, wherein the separator tree includes at least one node or a road junction of a roadmap;
determining in the preprocess step at least one minimal cost value, and associating the value to the at least one node or the road junction for later use during an online query to compute a local separator heuristic (LSH) function; and
responding to the online query by a user through utilization of both the stored separator tree and the heuristic function that is computed after the preprocess step to determine a fast path on the roadmap; and
wherein, response to the online query is improved over a similar query utilizing a classical A* algorithm without the heuristic function when computing fastest paths.
2. The method of claim 1 , wherein response to the online query further includes comparing binary codes of a pair of query vertices by using the local separator heuristic (LSH).
3. The method of claim 1 , wherein response to the online query further includes compare binary codes of a pair of query vertices by using a quad tree heuristic.
4. The method of claim 1 , further comprising:
establishing a system of global separators or a grid of horizontal and vertical separators on the roadmap; or
establishing a system of binary trees of separators on the roadmap, wherein each separator is based on a one-dimensional recursive subdivision; or
establishing a system of quadtrees of separators on the road map, wherein, each separator is based on a two-dimensional recursive subdivision.
5. A non-transitory computer readable medium storing computer executable code, comprising a code for:
constructing in a preprocess step a separator tree and storing the separator tree with a network, wherein the separator tree includes at least one node or a road junction of a roadmap;
instructing in the preprocessing step to compute a a minimal cost value per road junction on a roadmap based on a set of separators and associating the value to the at least one node or the road junction for later use during an online query to compute a local separator heuristic (LSH) function;
storing the vectors of the preprocessing step with a map;
responding to the online query by a user through using the set of separators and stored vectors to compute the heuristic function and utilizing the set of separators and stored vectors, and the heuristic function that is computed after the preprocess step to determine a fast path on the roadmap; and
wherein, response to the online query is improved over a similar query utilizing a classical A* algorithm without this heuristic when computing fastest paths.
6. The non-transitory computer readable medium of claim 5 , further includes:
transmitting a fastest path to the user.
7. The non-transitory computer readable medium of claim 5 , further includes:
implementing a binary tree heuristic or implementing a quadtree heuristic to determine a fastest path on the roadmap.
8. The non-transitory computer readable medium of claim 5 , further includes:
scaling to provide an informed estimate of a fastest travel time between two vertices in the roadmap.