Method and Device for Determining a Route with Points of Interest

• US 20080120022A1
• Filed: 02/01/2006
• Published: 05/22/2008
• Est. Priority Date: 02/07/2005
• Status: Abandoned Application

• Current Assignee: Compagnie générale des établissements Michelin
• Original Assignee: Societe De Technologie Michelin (Compagnie Generale DES Etablissements Michelin SCA)
• Inventors: Hayot, Pierre, Raynaud, Michel
• Application Number:
  US11/883,811
• Publication Number:
  US 20080120022A1
• 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
• CPC Class Codes: G01C 21/3476 using point of interest [POI] information, e.g. a route passing visible POIs

Abstract

A method for determining routes for a digital road network system on the basis of a main route connecting a starting point to a finishing point. The method makes it possible to reach a point of interest (POI) reachable by a plurality of secondary routes intersecting the main route. An optimal POI overall route is determined by performing the following steps. First, a POI overall route is evaluated for each of the potential secondary routes on the basis of at least the following route elements: (1) a useful portion of a main route and a corresponding score, the score being assigned a factor “k” lying between 0.1 and 0.7, and (2) the chosen secondary route and a corresponding score. Then, the POI overall route whose resulting score is optimal is chosen.

Claims

1. A method for determining routes for a digital road network system stored on a memory medium and comprising a plurality of sections and of positioning indications for these sections, said sections being capable of being arranged in a reconstruction of a road network so as to form road portions and junctions, in which method, on the basis of a main route connecting a starting point, selected from a database, to a finishing point, also selected from a database, said route being constructed from sections and possibly nodes, said sections connecting said nodes, said method furthermore making it possible to reach at least one point of interest (POI) reachable by a plurality of secondary routes intersecting the main route, an optimal POI overall route is determined by performing the following steps:

a POI overall route is evaluated for each of the potential secondary routes on the basis of at least the following route elements;

a useful portion of main route and a corresponding score, said score being assigned a factor “

k”

, the value of said factor “

k”

lying between 0.1 and 0.7, and preferably between 0.3 and 0.5,

the chosen secondary route and a corresponding score;

the POI overall route whose resulting score is optimal is chosen from the set of evaluated POI overall routes.

2. The method for determining routes as claimed in claim 1, in which the POI overall route comprises said useful portion of main route combined with the chosen secondary route.

3. The method for determining routes as claimed in claim 1 or 2, in which the optimal score is the lowest.

4. The method for determining routes as claimed in claim 1 or 2, in which the score corresponds to the journey time.

5. The method for determining routes as claimed in claim 1 or 2, in which the origin of the useful portion of the main route is the starting point of the main route.

6. The method for determining routes as claimed in claim 1 or 2, in which the origin of the useful portion of the main route is the first intersection point between the main route and one of the potential secondary routes, taking account of the direction of the main route.

7. The method for determining routes as claimed in claim 1 or 2, in which the network also comprises nodes, making it possible, in a representation of the road network, to join together a plurality of sections.

8. The method for determining routes as claimed in claim 1 or 2, in which in order to determine the route, a plurality of potential roads is identified from which a route is elected on the basis of given criteria, the identification of the plurality of roads being performed by selecting a first modeling element for the road network, preferably a node, in proximity to the starting point, and a second modeling element for the road network, preferably a node, in proximity to the finishing point;

identifying a plurality of roads, each comprising a plurality of connected road elements from the first element to the second element; and

searching for at least one intermediate element for each of said roads in said set of road network modeling elements.

9. The method for determining routes as claimed in claim 1 or 2, in which the route is determined with the aid of a Dijkstra algorithm.

10. The method for determining routes as claimed in claim 1 or 2, in which the route is determined with the aid of the FORD algorithm.

11. A POI selection method for a digital mapping system in which, on the basis of a main route connecting a starting point, selected from a database, to a finishing point also selected from a database, said route being constructed from sections and possibly nodes connecting said sections, in which a plurality of POI overall routes, determined with the method according to claim 1 or 2, is used to select a plurality of POI'"'"'s.

12. A piece of software comprising code elements programmed for the implementation of the method as claimed in claim 1 or 2, when said piece of software is loaded into a computer system and executed by said computer system.

13. The piece of software as claimed in claim 12, in the form of a product recorded on a medium readable by a computer system, comprising programmed code elements.

14. Route calculation device, comprising:

a data entry unit, intended to receive the data associated with a starting point and those associated with a finishing point;

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

a calculation unit devised to identify a plurality of roads each making it possible to connect the starting and finishing points;

evaluation means, making it possible to evaluate, for a plurality of potential secondary routes connecting the main route to at least one point of interest, a POI overall route on the basis of at least the following route elements;

a useful portion of main route and a corresponding score, said score being assigned a factor “

k”

, the value of said factor “

k”

lying between 0.1 and 0.7, and preferably between 0.3 and 0.5;

the chosen secondary route and a corresponding score;

and making it possible to choose, from the set of evaluated POI overall routes, the POI overall route whose resulting score is optimal.

15. The device as claimed in claim 14, comprising a guidance unit devised so as to generate guidance information as a function of the mapping elements of the selected route.

16. A computer system comprising a device as claimed in one of claims 14 or 15.