Patent attributes
A routing system for efficiently determining a route between an origin and destination is provided. The routing system operates on route data that is organized into rectangular grids. The route data includes edges with their costs, and nodes that identify connecting edges. The route data is also organized according to a hierarchy, with higher level grids corresponding to at least one lower level grid. The lowest level grids contain all route data corresponding to the area covered by each low level grid. The higher level grids contain a copy of route data from their corresponding lower level grids for only those routes that are identified as important routes. A routing algorithm uses the hierarchy in a manner such that higher level grids are used whenever practical to efficiently find a route from the origin to the destination.
