Data formats and usage for massive point to point route calculation

• US 8,000,891 B2
• Filed: 05/22/2006
• Issued: 08/16/2011
• Est. Priority Date: 02/22/2000
• Status: Active Grant

• Current Assignee: GeoTab Incorporated
• Original Assignee: Pointserve, Inc. (GeoTab Incorporated)
• Inventors: Indseth, Runar, Powell, G. Edward, Chen, Sheng
• Primary Examiner(s): Zanelli; Michael J.
• Application Number:
  US11/437,815
• Publication Number:
  US 20090326793A1
• Time in Patent Office: 1,912 Days
• Field of Search: None
• US Class Current: 701/201
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

The invention is directed to a method by which optimal paths are found between one or more start destinations and one or more end destinations. First destination and travel data is converted into a node and edge data format, wherein the nodes represent start points and the edges have a weight related to a travel weight. These nodes and edges are subdivided into subsets. The paths between the start nodes and each of the end nodes are determined using the node and edge representations stored in the subsets. A selected union of subsets is determined that contains the start end destinations. The optimal paths are determined by using the travel values associated with the edges connecting the nodes. The union of subsets, which may comprise less than the full amount of subsets, is loaded for the path determination. Or, when the path determination perceives that a relevant boundary has been reached in a path determination, that next subset in the union of subsets is loaded. The newly loaded subset is “joined” to the already loaded subsets, thus allowing the completion of the path determination.

Claims

1. A method for dynamically generating transport parameter values from an arbitrarily selected origin point to all possible destination points in a spatially-oriented array of points, the method being executed using at least one processor and comprising the steps of:

dynamically generating, using at least one processor, a minimal area spatially-oriented array comprising a set of desired points for which overall transport parameter values are desired, the minimal area spatially-oriented array positioned relative to the arbitrarily selected points;

generating, using the at least one processor, at a prior time a plurality of pre-processed data sets comprising precalculated transport parameter values for points within each of the plurality of pre-processed data sets, the pre-processed data sets comprising at least the set of desired points;

dynamically associating selected ones of the pre-processed data sets so that each of the associated pre-processed data sets intersects the minimal area spatially-oriented array; and

dynamically generating, using the at least one processor, transport parameter values from the arbitrarily selected origin point to all possible destination points within the set of desired points by relating to the origin point the precalculated transport parameter values, in which the dynamically generated transport parameter values are constant over time.

2. The method of claim 1 wherein the transport parameter values are travel times on a road.

3. The method of claim 1 wherein the transport parameter values are travel parameters associated with a computer network.

4. The method of claim 1 further comprising:

dynamically making available the selected ones of the pre-processed data sets on an as needed basis.

5. A method for dynamically generating transport parameter values from an arbitrarily selected origin point to all possible destination points in a spatially-oriented array of points, comprising the steps of:

dynamically generating, using at least one processor, a minimal area spatially-oriented array comprising a set of desired points for which overall transport parameter values are desired, the minimal area spatially-oriented array positioned relative to the arbitrarily selected points;

generating, using the at least one processor, at a prior time a plurality of pre-processed data sets comprising precalculated transport parameter values for points within each of the plurality of pre-processed data sets, the pre-processed data sets comprising at least the set of desired points;

dynamically associating selected ones of the pre-processed data sets so that each of the associated pre-processed data sets intersects the minimal area spatially-oriented array; and

dynamically generating, using the at least one processor, transport parameter values from the arbitrarily selected origin point to all possible destination points within the set of desired points by relating to the origin point the precalculated transport parameter values, in which the dynamically generated transport parameter values vary over time.

6. The method of claim 5 wherein the transport parameter values are travel times on a road.

7. The method of claim 5 wherein the transport parameter values are travel parameters associated with a computer network.

8. The method of claim 5 further comprising:

dynamically making available the selected ones of the pre-processed data sets on an as needed basis.