POUR SYSTÈME DE CALCUL D'ITINÉRAIRES

DOMAINE TECHNIQUE DE L'INVENTION

[0001] La présente invention concerne un procédé d'identification de données de direction à suivre pour un graphe routier interurbain d'un système de calcul d'itinéraire. Elle concerne également un système d'identification de données de direction à suivre pour un graphe routier interurbain d'un système de calcul d'itinéraire.

ETAT DE LA TECHNIQUE ANTÉRIEURE

[0002] De façon classique, il est d'usage d'informer un conducteur sur un itinéraire à suivre en lui donnant une ou plusieurs directions successives à suivre le long de l'itinéraire. Le conducteur fait ensuite appel aux panneaux routiers le long des routes pour repérer les directions à suivre et effectuer les man uvres telles qu'indiquées sur les panneaux en relation avec les directions concernées. Pour que ce mode de guidage souvent utilisé lors d'un échange de personne à personne puisse être utilisé en mode de calcul d'itinéraire automatique, il est essentiel que les bases de données utilisées soient complètes, à jour et fiables. Or, dans la plupart des bases de données routières, on retrouve un certain nombre de données de direction pour certaines routes ou certains secteurs, mais rarement pour le graphe en entier. [0003] Le document EP 1865284 décrit un dispositif d'affichage d'itinéraire qui comprend un moyen d'extraction des points géographiques concernant une ville existant le long d'un itinéraire, un moyen d'affichage et un moyen de commande d'affichage permettant de visualiser un itinéraire schématique. [0004]Le document JP 2010145087 décrit un dispositif d'affichage qui comprend: un moyen de stockage pour stocker les noms des environs de son lieu d'habitation, un moyen de détermination pour déterminer si oui ou non une intersection prédéterminée est constituée d'une route menant au quartier de son lieu d'habitation, et des moyens de guidage pour générer le parcours à l'aide des noms de quartier si l'intersection est constituée par une route menant au quartier de son lieu d'habitation.

[0005]Ces deux types de mise en oeuvre font appel aux bases de données classiques et ne permettent pas de pallier à l'insuffisance de ces bases en ce qui a trait aux données de direction.

[0006] Par ailleurs, si on souhaite compléter les bases de données classiques actuelles afin de les rendre suffisamment exhaustives pour être utilisables de façon fiable, les modes manuels d'entrée de données classiques permettant de documenter les bases sont longs et fastidieux à mettre en uvre.

[0007] Pour pallier ces différents inconvénients, l'invention prévoit différents moyens techniques.

EXPOSE DE L'INVENTION

[0008] Un premier objet de l'invention consiste à prévoir un procédé permettant de compléter les bases de données de direction ne comportant pas suffisamment de données pour être utilisées dans des calculs d'itinéraires de façon fiable.

[0009] Un autre objet de l'invention consiste à prévoir un procédé permettant de compléter les bases de données de direction ne comportant pas suffisamment de données, sans faire appel à des modes classiques de collecte ou d'entrées de données.

[0010] Un autre objet de l'invention consiste à prévoir un procédé permettant de scruter le graphe afin de déterminer si des données de direction peuvent être identifiées.

[0011]Pour ce faire, l'invention prévoit un procédé de calcul d'itinéraire permettant de déterminer un parcours routier entre deux points d'un graphe routier, comportant les étapes consistant à :

- recevoir un point de départ et un point d'arrivée ;

- parcourir le graphe afin d'identifier les itinéraires potentiels entre ces points ; - élire les points et/ou segments du graphe permettant de générer un itinéraire optimal en fonction de critères donnés ;

- effectuer un parcours virtuel de l'itinéraire afin de déterminer des références de guidage susceptibles de permettre à un utilisateur de parcourir ledit itinéraire, les références de guidage comportant des données de directions ;

- les données de direction ayant été préalablement identifiées au moyen des étapes suivantes, consistant à :

i) subdiviser les carrefours du graphe routier interurbain en trois types de carrefours, le premier type comprenant les intersections à niveau ou sorties de rond-point ; le second type comprenant les sorties sous forme de bretelles ; le troisième type comprenant les entrées de voies rapides sous forme de bretelles ;

ii) effectuer, pour le premier type de carrefours un parcours du graphe en recherchant, pour chaque carrefour du graphe de ce type, des données de nom de ville parcourues pendant la phase d'exploration du graphe ;

iii) mémoriser les noms de ville dont le niveau d'importance est supérieur à un seuil donné;

iv) associer les noms de villes mémorisées aux points de départ pour lesquels un lien existe, sur le graphe exploré, entre le carrefour et la ville, en tant que données de direction à suivre en relation avec un itinéraire à définir ;

v) effectuer, pour le second type de carrefours, un parcours de graphe en recherchant, pour chaque carrefour du graphe de ce type, des données de nom de ville parcourues pendant la phase d'exploration du graphe ;

vi) reprendre les étapes iii) et iv) pour le second type de carrefours ;

vii) effectuer, pour le troisième type de carrefours un parcours de graphe en recherchant, pour chaque carrefour du graphe de ce type, des données de nom de ville parcourues pendant la phase d'exploration du graphe ;

viii) reprendre les étapes iii) et iv) pour le troisième type de carrefours.

[0012] Le procédé selon l'invention permet de créer ou de compléter des bases de données de direction, en faisant appel à des données déjà présentes dans la base, à partir desquelles les données de direction sont générées. On évite ainsi de devoir faire appel à des modes de saisies de données à partir du terrain, souvent coûteux et fastidieux. [0013] Selon un mode de réalisation avantageux, le procédé comporte les étapes consistant à :

- vérifier si l'exploration du graphe du premier type ou du troisième type de carrefours est possible tout en assurant une continuité ;

- poursuivre l'exploration dans le cas où la continuité est assurée ;

- cesser l'exploration en cas de rupture de continuité.

[0014] Selon une variante avantageuse, le calcul de l'itinéraire est effectué à postériori de l'enrichissement de la base de données.

[0015]Selon une autre variante, le calcul de l'itinéraire est effectué simultanément à l'enrichissement de la base de données.

[0016] L'invention prévoit également un procédé permettant de compléter une base de données de direction à suivre pour un graphe routier interurbain d'un système de calcul d'itinéraire, comportant les étapes consistant à :

i) subdiviser les carrefours du graphe routier interurbain en trois types de carrefours, le premier type comprenant les intersections à niveau ou sorties de rond-point ; le second type comprenant les sorties sous forme de bretelles ; le troisième type comprenant les entrées de voies rapides sous forme de bretelles ;

ii) effectuer, pour le premier type de carrefours un parcours du graphe en recherchant, pour chaque carrefour du graphe de ce type, des données de nom de ville parcourues pendant la phase d'exploration du graphe ;

iii) mémoriser les noms de ville dont le niveau d'importance est supérieur à un seuil donné;

iv) associer les noms de villes mémorisées aux points de départ pour lesquels un lien existe, sur le graphe exploré, entre le carrefour et la ville, en tant que données de direction à suivre en relation avec un itinéraire à définir ;

v) effectuer, pour le second type de carrefours, un parcours de graphe en recherchant, pour chaque carrefour du graphe de ce type, des données de nom de ville parcourues pendant la phase d'exploration du graphe ;

vi) reprendre les étapes iii) et iv) pour le second type de carrefours ; vii) effectuer, pour le troisième type de carrefours un parcours de graphe en recherchant, pour chaque carrefour du graphe de ce type, des données de nom de ville parcourues pendant la phase d'exploration du graphe ;

viii) reprendre les étapes iii) et iv) pour le troisième type de carrefours ;

ix) enregistrer les nouvelles données de direction dans la base de données de direction.

[0017] Le procédé selon l'invention permet de faire appel à des bases de données enrichies en ce qui a trait aux données de directions. Grâce à cette fonctionnalité technique, il est désormais possible de générer des cartes ou des guidages avec des données de direction, sans risque d'incohérence ou erreurs liées à des bases de données incomplètes. Cette même fonctionnalité permet également une expression synthétique des itinéraires, puisque l'utilisation de directions à suivre permet d'omettre les détails précis qui rendent souvent les instructions difficiles à appréhender.

[0018] Grâce à l'utilisation de bases de données de direction comportant un nombre important de données pour l'ensemble du graphe, il est possible d'industrialiser des procédés de calculs d'itinéraires à l'aide d'indications de direction sans risque que des portions d'itinéraires ne soient pas adéquatement renseignées.

[0019] Selon un mode de réalisation avantageux, le procédé comporte les étapes consistant à :

- vérifier si l'exploration du graphe du premier type ou du troisième type de carrefour est possible tout en assurant une continuité ;

- poursuivre l'exploration dans le cas où la continuité est assurée ;

- cesser l'exploration en cas de rupture de continuité.

DESCRIPTION DES FIGURES

[0020]Tous les détails de réalisation sont donnés dans la description qui suit, complétée par les figures 1 à 4, présentées uniquement à des fins d'exemples non limitatifs, et dans lesquelles: -la figure 1 présente un organigramme fonctionnel présentant les étapes d'une première phase du procédé selon l'invention ;

-la figure 2 présente un organigramme fonctionnel présentant les étapes d'une seconde phase du procédé selon l'invention ;

-la figure 3 présente un organigramme fonctionnel présentant les étapes d'une troisième phase du procédé selon l'invention ;

-la figure 4 présente une représentation schématique d'un système d'identification de données de direction selon l'invention. DESCRIPTION DETAILLEE DE L'INVENTION

Procédé en trois phases :

[0021] Le procédé selon l'invention est subdivisé en trois phases ou étapes, correspondant à autant de catégories de carrefours. Ainsi, une première phase d'exploration du graphe afin d'établir des liens entre des données de carrefours et des données de directions ou destinations potentielles atteignables depuis ces carrefours est effectuée pour les carrefours de type intersections à niveau et sorties de rond-point.

[0022] Une seconde phase d'exploration afin d'établir des liens entre des données de carrefours et des données de directions ou destinations potentielles atteignables depuis ces carrefours est effectuée pour les carrefours de type sorties de réseau sous forme de bretelles.

[0023] Enfin, une troisième phase d'exploration afin d'établir des liens entre des données de carrefours et des données de directions ou destinations potentielles atteignables depuis ces carrefours est effectuée pour les carrefours de type entrées du réseau de voies rapides sous forme de bretelles.

1 ^re catégorie de carrefours :

[0024] La figure 1 illustre les différentes étapes effectuées par un système d'identification de données 1 selon l'invention pour les étapes inhérentes à la première catégorie de carrefours routiers. A l'étape 110, un module de sélection 6 sélectionne le graphe routier interurbain et identifie, à l'étape 120, les carrefours du graphe représentant des intersections à niveau ou des sorties de ronds-points. A l'étape 130, le seuil d'importance de la ville à atteindre est déterminé en fonction du niveau d'importance de la route empruntée au départ par le module de sélection 6.

[0025] A l'étape 140, le module de parcours de graphe 8 effectue un parcours du graphe depuis les carrefours identifiés et dans chacune des directions permises au départ. A l'étape 150, le module de parcours de graphe 8 effectue une vérification afin de déterminer si l'exploration peut être poursuivie dans la continuité.

[0026] Si tel n'est pas le cas (étape 170), le processus se termine à l'étape 180. Si l'exploration dans la continuité est possible (étape 160), lorsqu'une ville est atteinte, le module de test 7 vérifie si la ville nouvellement atteinte a le niveau d'importance le plus élevé depuis le début de l'exploration. Si tel n'est pas le cas, (étape 162), ces données de direction ne sont pas retenues (étape 163) et l'exploration du graphe se poursuit (étape 169) à l'étape 150.

[0027] Si la ville rencontrée a le niveau d'importance le plus élevé depuis le départ, (étape 164), le module d'appariement 9 relie les données de cette ville aux carrefours pour lesquels un lien existe. Un appariement est effectué pour tous les carrefours identifiés à l'étape 120 et rencontrés au fil de l'exploration.

[0028] A l'étape 165, le module de test 7 vérifie si le niveau d'importance de la ville atteinte est égal ou supérieur au seuil déterminé au départ. Si c'est le cas, (étape 167), l'exploration s'arrête à l'étape 180. Dans le cas contraire (étape 168), l'exploration du graphe est poursuivie (étape 69) à partir de l 'étape 150.

2 ^e catégorie de carrefours :

[0029] La figure 2 illustre les différentes étapes effectuées par un système d'identification de données 1 selon l'invention pour les étapes inhérentes à la seconde catégorie de carrefours routiers. A l'étape 210, un module de sélection 6 sélectionne le graphe routier interurbain et identifie, à l'étape 220, les carrefours du graphe représentant des sorties du réseau de voies rapides sous forme de bretelles.

[0030]A l'étape 230, le module de parcours de graphe 8 effectue un parcours du graphe depuis les carrefours identifiés, uniquement via les bretelles. [0031]A l'étape 240, le module de parcours de graphe 6 teste les carrefours parcourus et stoppe le parcours dès qu'un carrefour comportant des données issues de la première phase d'exploration est atteint. [0032]A l'étape 250, les données de direction obtenues sont filtrées de façon à éliminer les données au delà d'un seuil limite. Par exemple, un seuil est fixé à 30km et applique aux villes d'importance moyenne et haute (villes dont « l'importance de la direction » dans le tableau 1 est supérieure à 4).

[0033] A l'étape 260, le module d'appariement 10 relie les données restantes aux carrefours pour lesquels un lien existe.

3 ^e catégorie de carrefours :

[0034] La figure 3 illustre les différentes étapes effectuées par un système d'identification de données 1 selon l'invention pour les étapes inhérentes à la troisième catégorie de carrefours routiers. A l'étape 310, un module de sélection 6 sélectionne le graphe routier interurbain et identifie, à l'étape 320, les carrefours du graphe représentant des entrées du réseau de voies rapides sous forme de bretelles. A l'étape 330, le seuil d'importance de la ville à atteindre est déterminé en fonction du niveau d'importance de la route empruntée au départ par le module de sélection 6.

[0035]A l'étape 340, le module de parcours de graphe 8 effectue un parcours du graphe depuis les carrefours identifiés, uniquement via les bretelles et le réseau qu'elles alimentent.

[0036]A l'étape 350, le module de parcours de graphe 8 effectue une vérification afin de déterminer si l'exploration peut être poursuivie dans la continuité. [0037] Si tel n'est pas le cas (étape 370), le processus se termine à l'étape 380. Si l'exploration dans la continuité est possible (étape 360), lorsqu'une bretelle de sortie est atteinte, le module de test 7 vérifie si la bretelle comporte des directions vers des villes avec un niveau d'importance plus élevé que celles déjà rencontrées depuis le début de l'exploration. Si tel n'est pas le cas, (étape 362), ces données de direction ne sont pas retenues (étape 363) et l'exploration du graphe se poursuit (étape 369) à l'étape 350. [0038] Si la bretelle rencontrée comporte des directions vers des villes dont le niveau d'importance est plus élevé que celles rencontrées depuis le départ, (étape 364), le module d'appariement 9 relie ces données de direction au point de départ de l'exploration.

[0039]A l'étape 365, le module de test 7 vérifie si le niveau d'importance de la ville atteinte est égal ou supérieur au seuil déterminé au départ. Si c'est le cas, (étape 367), l'exploration s'arrête à l'étape 380. Dans le cas contraire (étape 368), l'exploration du graphe est poursuivie (étape 369) à partir de l 'étape 350.

Variantes

[0040] Bien entendu, l'affectation des diverses étapes aux différents modules du système d'identification de données de direction est donnée à titre d'exemple. Diverses variantes d'affectation sont possibles, en fonction de l'agencement des instructions. Ces variantes sont sans effet notable sur le procédé en tant que tel.

[0041]Le tableau 1 , ci-après, illustre un exemple de données susceptibles d'être obtenues au moyen du procédé d'identification de données de direction selon l'invention.

Tableau 1 : exemple de données résultant de la mise en oeuvre du procédé selon l'invention

[0042] Dans cet exemple, des identifiants sont prévus pour les points de départs, les tronçons, et les directions. Des données de noms de direction sont prévues, en association avec les villes ou agglomérations constituant des cibles à viser pour une partie ou la totalité d'un itinéraire ultérieurement calculé. [0043] Les données d'importance de la direction permettent de prioriser les choix possibles lorsque plusieurs possibilités se présentent.

[0044] Les données d'identification de route permettent de compléter l'information de direction par une information de route à suivre vers ladite direction. Enfin, les données de distances permettent par exemple de sélectionner de préférence une direction qui pourrait être suivie plus longtemps pour un itinéraire donné.

[0045] La figure 4 montre un exemple de système d'identification de données de direction selon l'invention. Dans cet exemple, le système est agencé selon une pluralité de modules, en fonction des principales opérations à effectuer. Diverses variantes d'architectures et d'agencement des modules, tant par le nombre de modules que par la répartition des fonctions entre les modules, sont possibles, sans sortir du cadre de l'invention.

[0046] Dans l'exemple illustré à la figure 4, le système d'identification de données de direction comporte :

- un module de sélection 6 adapté pour sélectionner le graphe ou portion de graphe pertinent pour la phase en cours et sélectionner les carrefours du graphe pertinent pour la phase en cours.

- un module de test de niveau d'importance 7, qui, en fonction de l'étape en cours, soit, lorsqu'une ville est atteinte, vérifie si la ville nouvellement atteinte a le niveau d'importance le plus élevé depuis le début de l'exploration ou, vérifie si le niveau d'importance de la ville atteinte est égal ou supérieur au seuil déterminé au départ.

- un module de parcours de graphe 8 permet de parcourir les tronçons et nœuds du graphe.

- un module d'appariement 9 est adapté pour relier les données des villes atteintes aux carrefours pour lesquels un lien existe entre les deux.

[0047] Deux bases de données intégrées au système sont illustrées à la figure 4, soit une base de données de réseau routier 2 et une base de données de direction 3. Ces bases peuvent être internes, externes et/ou à distance. Elles peuvent aussi être combinées en une seule base. [0048] Les Figures et leurs descriptions faites ci-dessus illustrent l'invention plutôt qu'elles ne la limitent. En particulier, l'invention et ses différentes variantes viennent d'être décrites e relation avec un exemple particulier de procédé comportant trois phases.

[0049] Néanmoins, il est évident pour un homme du métier que l'invention peut être étendue à d'autres modes de réalisation dans lesquels en variantes, on prévoit un nombre différent de phases, par exemple en combinant des phases décrite ci-dessus ou en ajoutant une ou plusieurs autres phases.

[0050] Les signes de références dans les revendications n'ont aucun caractère limitatif. Les verbes "comprendre" et "comporter" n'excluent pas la présence d'autres éléments que ceux listés dans les revendications.