Data formats and usage for massive point-to-point route calculation

• US 7,050,904 B2
• Filed: 02/22/2001
• Issued: 05/23/2006
• Est. Priority Date: 02/22/2000
• Status: Expired due to Term

• 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:
  US09/790,333
• Publication Number:
  US 20020016670A1
• Time in Patent Office: 1,916 Days
• Field of Search: 701/201, 701/202, 701/209
• 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 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 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, comprising the steps of:

dynamically generating 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 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 points 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 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.

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.