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

• US 7,437,239 B2
• Filed: 01/09/2002
• Issued: 10/14/2008
• Est. Priority Date: 01/09/2002
• Status: Expired due to Fees

• Current Assignee: Webraska Mobile Technologies SA (Atlantia SpA)
• Original Assignee: Webraska Mobile Technologies SA (Atlantia SpA)
• Inventors: Serre, Julien
• Primary Examiner(s): Tran; Khoi H.
• Assistant Examiner(s): Broadhead; Brian J.
• Application Number:
  US10/500,991
• Publication Number:
  US 20050119825A1
• Time in Patent Office: 2,470 Days
• Field of Search: 701/201, 701/202, 701/209, 701/208
• 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. A 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, the method comprising the steps of:

attributing a cost to each segment of the network;

developing two path graphs, substantially starting from two points (A,B);

classifying the segments according to a plurality of network levels and for each network level, attributing a predefined threshold of number of segments of said level;

during the development of at least one of the two graphs;

searching a group of successive segments with a given level m, comprising exclusively intermediate nodes which do not belong to any segment with a level which is greater than or 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;

calculating the number of segments of the graph of a lowest level m_inf,

if the number of segments of the graph developed of a lowest level minf is equal or greater than starting from a predefined threshold of number of segments of level m_inf,

said at least one of the two path graphs is developed taking into account only the segments which belong to the levels which are strictly higher than the level m_inf,

the number of segments of the graph developed of a lowest level m_inf+1 is calculated;

if the number of segments of the graph developed of a lowest level m_inf+1 is equal or greater than a predefined threshold of number of segments of level m_inf+1, said at least one of the two path graphs is developed taking into account only the segments which belong to the levels which are strictly higher than the level m_inf+1;

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

determining two minimal cost paths belonging respectively to the two path graphs; and

connecting said two minimal cost paths in order to obtain a minimal cost path connecting the said two points (A,B).

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

3. Method according to claim 1, wherein, for at least one of said two points (A,B), at least two adjacent nodes (P_A,n, P_A,n+1) of the said at least one (A) of said two points 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) from a segment on which the at least one (A) of said two points is substantially situated, a basic cost of each node (P_A,n, P_A,n+) 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:

during the development of the two path graphs, the number of segments of each graph of a lowest level m_inf is calculated; and

when the number of segments of level m_inf has reached said predefined threshold for the two path 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.

6. Method according to claim 1, wherein the development of said at least one of the two path graphs is started by taking into account each of the segments which belong to any of the levels of the network.

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

8. Method according to claim 7, wherein the said two path graphs are developed by using a bucket algorithm.

9. 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.

10. Server according to claim 9, 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.