Method and device for determining the minimal cost path between two points in a road network

• US 20050119825A1
• Filed: 01/09/2002
• Published: 06/02/2005
• Est. Priority Date: 01/09/2002
• Status: Active Grant

• Current Assignee: Webraska Mobile Technologies SA (Atlantia SpA)
• Original Assignee: Webraska Mobile Technologies SA (Atlantia SpA)
• Inventors: Serre, Julien
• Granted Patent: US 7,437,239 B2
• Time in Patent Office: Days
• US Class Current: 701/202
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

Abstract

The invention relates to a network comprising numerous nodes which are paired by means of segments. The inventive method consists in: allocating a cost to each segment in the network; producing two path graphs, essentially from two points respectively; interrupting the production of the two graphs when they comprise at least a first common interference node; determining the two minimal cost paths which belong respectively to the two graphs; and linking the two minimal cost paths in order to obtain the minimal cost path between the two points. The invention also relates to a server which is used to implement said method.

Claims

1. Method for determining the minimal cost path between two points (A,B), via a transport network comprising a plurality of nodes (P_n) which are connected in pairs by segments, wherein:

a cost is attributed to each segment of the network;

a path graph is developed, substantially starting from at least one of the two points (A,B); and

the minimal cost path which connects the two points (A,B) is determined, the method being characterised in that

two path graphs are developed, substantially starting from two points (A,B) respectively;

the development of the two graphs is interrupted when they comprise at least one first common interference node (P_i);

the two minimal cost paths belonging respectively to the two graphs are determined; and

the two minimal cost paths are connected in order to obtain the minimal cost path between the two points (A,B).

2. Method according to claim 1, wherein, in the case when at least one of the points (A,B) is situated substantially at the location of a node, the corresponding graph is developed starting from the said node.

3. Method according to claim 1, wherein, for at least one of the two points (A,B), at least two adjacent nodes (P_A,n, P_A,n+1) of the said point (A) are sought, a non-zero basic cost is attributed to each of these two nodes (P_A,n, P_A,n+1), and a single graph is developed starting from these two nodes (P_A,n, P_A,n+1).

4. Method according to claim 3, wherein since the two nodes (P_A,n, P_A,n+1) form a segment on which the point (A) is substantially situated the basic cost of each node (P_A,n, P_A,n+1) is determined by proportionality starting from the cost of the segment between these two nodes (P_A,n, P_A,n+1).

5. Method according to claim 1, wherein:

the segments are classified according to a plurality of network levels;

during the development of at least one of the two graphs, the number of segments of the graph which belong to the lowest level m_inf is calculated; and

starting from a predefined threshold of number of segments of level m_inf, the graph is developed taking into account only the segments which belong to the levels which are strictly higher than the level m_inf.

6. Method according to claim 5, wherein:

during the development of the two graphs, the number of segments of each graph which belong to the lowest level m_inf is calculated; and

when the number of segments of level m_inf has reached the said threshold for the two graphs, the development of the two graphs is continued, taking into account only the segments which belong to the levels which are strictly higher than the level m_inf.

7. Method according to claim 5, wherein the development of the said graph is started by taking into account all the segments which belong to all the levels of the network.

8. Method according to claim 1, wherein:

a group of successive segments with a given level m is sought, comprising exclusively intermediate nodes which do not belong to any segment with a level which is at least equal to m, other than those of the group of successive segments with the level m concerned; and

the group of successive segments is substituted by a single segment with a level m.

9. Method according to claim 1, wherein each graph is developed in a globally concentric manner.

10. Method according to claim 9, wherein the two graphs are developed by using a bucket algorithm.

11. Method according to claim 1, wherein the two graphs are developed simultaneously.

12. Method according to claim 1, wherein, having found the said first common interference node (P_i), the optimal interference node (P_io) is sought from amongst the nodes already analysed, in order to determine the two minimal cost paths which contain the optimal interference node (P_io).

13. Road navigation aid server for implementation of the method according to claim 1, comprising an interface for connection to a communication network, a block for receipt of requests from client terminals, a block for receipt of road network data, a block for classification of road segments, a block for creation of a virtual road network, a block for labelling of road segments, a calculation module and a transmission block.

14. Server according to claim 13, wherein the calculation module comprises a graph development block, a block for detection of a change of level of segments, and a block for determination of the minimal cost path.