Route Calculation Method and Device with Progressive Elimination of Data Corresponding to the Road Network

• US 20080189029A1
• Filed: 10/13/2005
• Published: 08/07/2008
• Est. Priority Date: 10/18/2004
• Status: Abandoned Application

• Current Assignee: Societe De Technologie Michelin (Compagnie Generale DES Etablissements Michelin SCA)
• Original Assignee: Societe De Technologie Michelin (Compagnie Generale DES Etablissements Michelin SCA)
• Inventors: Hayot, Pierre, Legrand, Christophe
• Application Number:
  US11/665,653
• Publication Number:
  US 20080189029A1
• Time in Patent Office: Days
• 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

Abstract

A method of determining routes between a point of departure(a) and a point of arrival (β) comprising the following steps:

a) the nodes surrounding a departure node are scanned so as to determine the cost of each of these nodes;

b) said scanning is continued until the point of arrival of the route is reached;

c) during said scanning, the nodes are scanned so as to identify the nodes that can be used to form a mesh with a given starting index Id;

d) when a mesh with an index Id is identified, the nodes and segments whose index is less than this index Id are eliminated;

e) scanning the nodes continues so as to identify the nodes that can be used to form a new mesh, whose index Is is greater than that of the preceding mesh;

f) nodes and segments whose index is less than this new index Is are eliminated;

g) steps e and f are repeated until the desired elimination level is reached.

Claims

1. A method of determining routes between a point of departure (a) and a point of arrival (β

) for a digital road mapping system consisting of a set of segments and nodes each having their importance index, said nodes and segments being put together so as to represent a road network formed of a plurality of meshes of different importance indices, each of the meshes being defined by a set of nodes of identical or greater value than a given value, defining an area, said method comprising the following steps;

a) via the segments, the nodes surrounding a departure node are scanned so as to determine the cost of each of these nodes;

b) said scanning is continued until the point of arrival of the route is reached;

c) during said scanning, the nodes are scanned so as to identify the nodes that can be used to form a mesh with a given starting index Id;

d) when a mesh with an index Id is identified, the segments whose index is less than this index Id are eliminated;

e) scanning the nodes continues so as to identify the nodes that can be used to form a new mesh, whose index Is is greater than that of the preceding mesh;

f) segments whose index is less than this new index Is are eliminated;

g) steps e and f are repeated until;

either the scanning enables the point of arrival of the route to be reached;

or a maximum index Im of elimination is reached.

2. The method of determining routes as claimed in claim 1, characterized in that the nodes are scanned so as to progressively form meshes whose index increases regularly.

3. The method of determining routes as claimed in claim 1, characterized in that the index of a subsequent mesh corresponds to the index following that of the immediately preceding mesh.

4. The method of determining routes as claimed in claim 1, characterized in that the importance index of a node corresponds to the highest index of the incident segments.

5. The method of determining routes as claimed in claim 1, characterized in that in order to determine the route, a plurality of potential routes is identified from which one route is selected according to given criteria.

6. The method of determining routes as claimed in claim 1, characterized in that the plurality of routes is identified by selecting a first modeling element of the road network, preferably a node, close to the point of departure, and a second modeling element of the road network, preferably a node, close to the point of arrival, identifying a plurality of routes, each consisting of a plurality of route elements connected from the first element to the second element, and searching for at least one intermediate element for each of said routes in said set of road network modeling elements.

7. The method of determining routes as claimed in claim 1 in which scanning the nodes is carried out using Dijkstra'"'"'s algorithm.

8. The method of determining routes as claimed in claim 1, in which scanning the nodes is carried out using FORD'"'"'s algorithm.

9. Software comprising code elements programmed for implementing the method as claimed in claim 1, when said software is loaded into a computer system and executed by said computer system.

10. The software as claimed in claim 9, in the form of a product recorded onto a machine-readable medium, comprising programmed code elements.

11. A route calculation device, comprising:

a data input unit, for receiving the data associated with a point of departure and those associated with a point of arrival;

access to a storage unit comprising a set of road network modeling elements;

a calculation unit designed for identifying a plurality of routes enabling each to connect the points of departure and arrival;

means of elimination, first for identifying at least one elimination level or threshold and secondly for eliminating at least one portion of the basic set of data whose index is below said elimination level or threshold.

12. The device as claimed in claim 11, including a guidance unit, designed to generate guidance information as a function of the mapping elements of the selected route.

13. A computer system including a device as claimed in claim 11.