Brevet FR2928727A1 — publié le 20090918

Estimation de plus court chemin dépendant du temps dans un réseau routier La présente invention concerne une estimation d'un plus court chemin en temps de parcours dépendant d'un instant de départ donné et de l'évolution du trafic dans un réseau routier, appelé le plus court chemin dépendant du temps. Plus particulièrement, elle a trait à une détermination d'un chemin très proche du plus court chemin selon le temps de parcours prenant en compte, pendant le parcours en temps réel, l'évolution du trafic sur un réseau routier dont le temps de parcours sur un arc donné est prévisible dans le futur. Des systèmes d'informations routières fournissent des historiques sous forme de vitesse ou des temps de parcours exprimant des conditions de circulation sur des tronçons routiers. Ces historiques sont déterminés à partir d'informations relevées en permanence sur le terrain par différents moyens tels que des capteurs fixes, ou des capteurs mobiles dans des véhicules. Des procédés statistiques d'analyse déterminent des profils stables et très réalistes de caractéristiques fortement probables du trafic à un instant de départ donné. Certains procédés s'appuient sur des informations calendaires telles que le jour de la semaine ou la date des vacances scolaires. Ces informations sont regroupées dans les historiques en classes hétérogènes. Par exemple, tous les lundis de la période scolaire sont regroupés dans une même classe et tous les lundis des vacances sont regroupés dans une autre classe. Un profil moyen est extrait de chacune de ces classes résumant les différentes situations observées en fonction des journées. Des procédés plus fins s'appuient intrinsèquement sur les données observées pour constituer les classes. Quel que soit le procédé de construction de profils, l'observation des conditions réelles de trafic et des variables calendaires permet de se rapprocher du profil réel correspondant et de prévoir avec une bonne probabilité l'état du trafic futur à court, moyen ou long terme. En fonction de ces données statistiques, il est utile de déterminer le plus court chemin entre deux points du réseau routier en considérant l'évolution du trafic en temps réel pendant le parcours, appelé le plus court chemin dépendant du temps ("time- dependent shortest path" en anglais). Cette détermination est théoriquement mise en oeuvre par l'algorithme de Dijkstra. En pratique, cependant, l'algorithme de Dijkstra est trop lent pour des applications en temps réel. Sur un très grand réseau routier représenté par de nombreux noeuds reliés entre eux par des arcs, par exemple d'une dizaine de millions de noeuds pour le réseau routier dans un pays comme la France, plusieurs secondes sont nécessaires pour déterminer un seul chemin. La technique de détermination du plus court chemin entre deux points du réseau routier peut être également mise en oeuvre par une recherche bidirectionnelle. Cependant la recherche bidirectionnelle ne peut être appliquée sur un réseau routier évoluant avec le temps, puisque que l'heure d'arrivée à la destination n'est pas connue impliquant de ce fait une impossibilité d'estimer les temps de parcours sur les tronçons routier.35 L'objectif de l'invention est de réduire le temps de détermination d'un plus court chemin dépendant du temps en utilisant une recherche de type bidirectionnelle sur un graphe représentatif du réseau routier dépendant du temps. Pour atteindre cet objectif, un procédé pour estimer le plus court chemin en temps de parcours dépendant d'un instant de départ donné entre un noeud source et un noeud de destination appartenant à un graphe orienté représentatif d'un réseau routier et contenant des noeuds et des arcs orientés entre les noeuds, est caractérisé en ce qu'il comprend une recherche bidirectionnelle de noeuds le long du plus court chemin incluant itérativement une recherche avant et une recherche arrière jusqu'à ce que le noeud de destination soit exploré en recherche avant, la recherche avant déterminant des plus courts temps de parcours entre le noeud source et des noeuds à explorer selon des fonctions de temps de parcours prévisionnel variant au cours du temps associées respectivement aux arcs du graphe orienté reliant les noeuds à explorer, et la recherche arrière déterminant des plus courts temps de parcours entre des noeuds à explorer et le noeud de destination selon des fonctions statiques associées respectivement aux arcs du graphe orienté reliant les noeuds à explorer et correspondant à des temps de parcours prévisionnels minimaux sur les arcs reliant les noeuds à explorer, le plus court chemin en temps de parcours entre le noeud source et le noeud de destination étant estimé en recherche avant. Les temps de parcours des chemins sont dépendant des temps de parcours prévisionnels des arcs orientés formant les chemins, ces temps de parcours prévisionnels évoluant dynamiquement au cours du temps. Selon les recherches bidirectionnelles connues, l'heure d'arrivée au noeud de destination ne peut être déterminée à partir d'un graphe dépendant du temps impliquant de ce fait l'impossibilité de déterminer les temps de parcours sur les différents arcs du graphe et ainsi d'estimer le chemin le plus court entre le noeud source et le noeud de destination. Comparativement à ces recherches bidirectionnelles connues, la recherche bidirectionnelle selon l'invention se base sur des estimations de temps de parcours prévisionnels des arcs du graphe, et est conduite en utilisant en recherche avant des fonctions de temps de parcours prévisionnel variant au cours du temps associées respectivement aux arcs du graphe orienté et en recherche arrière des fonctions statiques associées respectivement aux arcs du graphe orienté qui sont des bornes inférieures aux fonctions variant au cours du temps et correspondent à des temps de parcours prévisionnels minimaux sur les arcs. Selon une caractéristique de l'invention, la recherche bidirectionnelle de noeuds comprend une première phase de traitement au cours de laquelle chaque noeud à explorer en recherche avant est l'extrémité orientée d'un arc relié à un noeud précédemment exploré en recherche avant et chaque noeud à explorer en recherche arrière est l'origine d'un arc relié à un noeud précédemment exploré en recherche arrière, et une deuxième phase de traitement activée dès qu'un premier noeud intermédiaire est exploré dans les deux recherches pendant la première phase de traitement et au cours de laquelle chaque noeud à explorer en recherche avant est l'extrémité orientée d'un arc relié à un noeud précédemment exploré en recherche avant et chaque noeud à explorer en recherche arrière est l'origine d'un arc relié à un noeud précédemment exploré en recherche arrière et est distinct des noeuds explorés en recherche avant. Une troisième phase de traitement peut être activée dès qu'une condition relative au plus court temps de parcours entre le noeud source et le noeud de destination et passant par le premier noeud intermédiaire est satisfaite. La condition peut consister en ce que le plus court temps de parcours entre le noeud source et le noeud de destination passant par le premier noeud intermédiaire soit inférieur à une valeur minimum d'une des clés de priorité associées aux noeuds à explorer en recherche arrière, chaque clé de priorité d'un de ces derniers noeuds étant égale à une somme du plus court temps de parcours déterminé entre ledit noeud et le noeud de destination et une sous-estimation du plus court temps de parcours entre le noeud source et ledit noeud. La succession des trois phases de traitement a pour avantage d'augmenter la rapidité d'estimation du plus court chemin entre un noeud source et un noeud de destination du graphe orienté, le procédé diminuant progressivement selon la phase de traitement son champ d'exploration des noeuds du graphe selon les noeuds déjà explorés en recherche avant et/ou en recherche arrière. L'invention a aussi pour objet un dispositif d'estimation pour estimer le plus court chemin en temps de parcours dépendant d'un instant de départ donné entre un noeud source et un noeud de destination appartenant à un graphe orienté représentatif d'un réseau routier et contenant des noeuds et des arcs orientés entre les noeuds. Le dispositif est caractérisé en ce qu'il comprend un moyen pour rechercher bidirectionnellement des noeuds le long du plus court chemin incluant iterativement une recherche avant et une recherche arrière jusqu'à ce que le noeud de destination soit exploré en recherche avant, des moyens déterminant en recherche avant des plus courts temps de parcours entre le noeud source et des noeuds à explorer selon des fonctions de temps de parcours prévisionnel variant au cours du temps associées respectivement aux arcs du graphe orienté reliant les noeuds à explorer, et des moyens déterminant en recherche arrière des plus courts temps de parcours entre des noeuds à explorer et le noeud de destination selon des fonctions statiques associées respectivement aux arcs du graphe orienté reliant les noeuds à explorer et correspondant à des temps de parcours prévisionnels minimaux sur les arcs reliant les noeuds à explorer, le plus court chemin en temps de parcours entre le noeud source et le noeud de destination étant estimé en recherche avant. Enfin, l'invention se rapporte à un programme d'ordinateur apte à être mis en oeuvre dans un dispositif informatique tel que le dispositif d'estimation de plus court chemin dépendant du temps de parcours selon l'invention. Le programme comporte des instructions qui, lorsque le programme est exécuté dans ledit dispositif, réalisent les étapes conformes au procédé de l'invention. D'autres caractéristiques et avantages de la présente invention apparaîtront plus clairement à la lecture de la description suivante de plusieurs réalisations de l'invention données à titre d'exemples non limitatifs, en référence aux dessins annexés correspondants dans lesquels : - la figure 1 est un graphe d'arcs et de noeuds respectivement associés aux tronçons d'un réseau routier ; - la figure 2 est un bloc-diagramme schématique d'un dispositif d'estimation de plus court chemin selon l'invention ; - la figure 3 est un algorithme simplifié relatif au procédé d'estimation du plus court chemin dépendant du temps entre deux intersections du réseau routier selon l'invention ; et - les figures 4 et 5 correspondent à un algorithme plus détaillé du procédé d'estimation du plus court chemin dépendant du temps entre deux intersections du réseau routier selon l'invention. L'invention concerne plus particulièrement l'estimation d'un temps de parcours le plus court à un instant donné Tp d'un chemin reliant deux entités d'un réseau routier notamment par l'application d'une recherche bidirectionnelle. En référence à la figure 1, un réseau routier est représenté formellement dans une base de données d'un dispositif de traitement sous la forme d'un graphe orienté GRT(N,A,Fc) comportant un ensemble N de noeuds avec IN1 noeuds, un ensemble A d'arcs orientés avec IA1 arcs orientés et une fonction Fc qui associe, pour chaque arc et pour chaque instant donné, un temps de parcours prévisionnel. Un instant donné correspond par exemple à une heure spécifique d'un jour précis : un lundi à 8 heure ou un jeudi à 14 heure. Chaque noeud est désigné par un identificateur et chaque arc est désigné par un identificateur. Un noeud Nn, avec 1 n INI, représente une intersection à la jonction de deux ou plusieurs tronçons du réseau routier. Les intersections de routes et de rues telles que carrefours, échangeurs et bifurcations sont représentées par des noeuds. Un arc orienté A1,2 représente un sens de circulation sur un tronçon routier respectif s'étendant entre deux noeuds N1 et N2. Une route à double sens, considérée comme un tronçon entre deux noeuds, par exemple les noeuds Nu et NV, est représentée par un premier arc Au,v orienté depuis le noeud Nu vers le noeud NV, et par un deuxième arc Av,u orienté depuis le noeud Nv vers le noeud Nu. La fonction Fc, telle qu'une fonction sinusoïdale, a une valeur variant au cours du temps représentative de profils de temps de parcours prévisionnels pour chaque tronçon correspondant à chaque arc orienté du graphe et selon chaque instant donné. A chaque arc et selon un instant donné est associée aussi une borne inférieure Binf à la fonction Fc, correspondant à un temps de parcours prévisionnel minimal sur le tronçon déduit notamment du rapport de la longueur du tronçon routier associé à l'arc sur la vitesse de circulation prévisionnelle minimale à parcourir sur le tronçon. Les valeurs liées à la fonction Fc et à la borne Binf sont déduites notamment des informations prévisionnelles évoluant dynamiquement au cours du temps en fonction du trafic routier, classées dans des historiques de mesures du trafic routier et mémorisées dans la base de données. Chaque arc est alors associé à des temps de parcours prévisionnels différents sur un même tronçon selon respectivement des instants donnés. Un sous-ensemble de noeuds L dans le graphe GRT contient ILI noeuds de repère ("Landmarks" en anglais), représentés par des cercles gris foncés à la figure 1, sélectionnés selon divers procédés connus afin qu'ils soient localisés de manière relativement homogène dans le graphe GRT. Les temps de parcours les plus courts des chemins reliant respectivement chaque noeud de repère L1, avec 1 Le procédé d'estimation du plus court chemin dépendant du temps entre un noeud source NS et un noeud de destination Nd du graphe GRT à un instant donné Tp comporte trois phases de traitement spécifiques. Les deux premières phases de traitement sont relatives à une recherche bidirectionnelle à appliquer sur le graphe GRT alors que la troisième phase de traitement est relative à une recherche unidirectionnelle à appliquer toujours sur le graphe GRT. Une recherche bidirectionnelle comprend un mode de recherche avant et un mode de recherche arrière. La recherche unidirectionnelle selon l'invention comprend le mode de recherche avant. Le mode de recherche avant consiste à explorer progressivement depuis le noeud source NS vers le noeud de destination Nd, des noeuds du graphe GRT(N,A,Fc), en répertoriant à partir d'un noeud à explorer des noeuds adjacents à celui-ci et en sélectionnant, à chaque itération, un nouveau noeud à explorer entre les noeuds déjà répertoriés comme le noeud répertorié mais non exploré ayant en mode de recherche avant une estimation minimale du temps de parcours entre le noeud source et le noeud de destination passant par le noeud sélectionné. Le poids de chaque arc orienté du graphe entre le noeud à explorer et un noeud adjacent représenté par le temps de parcours est déterminé dynamiquement par application de la fonction dynamique Fc associée à l'arc. Le mode de recherche arrière consiste à explorer progressivement depuis le noeud de destination Nd vers le noeud source NS, des noeuds du graphe GRT (N, A, Binf ) en répertoriant à partir d'un noeud à explorer des noeuds adjacents à celui-ci et en sélectionnant, à chaque itération, un nouveau noeud à explorer entre les noeuds déjà répertoriés comme le noeud répertorié mais non exploré ayant en mode de recherche arrière une estimation minimale du temps de parcours entre le noeud source et le noeud de destination passant par le noeud sélectionné. Le poids de chaque arc orienté du graphe entre un noeud adjacent et le noeud à explorer représenté par le temps de parcours est prédéterminé statiquement en fonction de la borne inférieure Binf associée à l'arc. Comme montré à la figure 2, un dispositif d'estimation de plus court chemin DEC dans un réseau routier selon l'invention comprend une unité centrale de traitement UC, trois modules de traitement MT1, MT2 et MT3 correspondant respectivement au trois phases de traitement, une base de données BD, une mémoire tampon MTP et une mémoire de registre MR. Le dispositif d'estimation de plus court chemin DEC selon l'invention est par exemple inclus dans un ordinateur personnel ou un serveur. Les blocs fonctionnels du dispositif DEC représentés à la figure 2 assurent des fonctions ayant un lien avec l'invention et peuvent correspondre à des modules logiciels et/ou matériels. Selon une réalisation, le dispositif DEC est inclus dans ou relié à un système de navigation routière par exemple à bord d'un véhicule ou inclus dans des terminaux de radiocommunication portables, comme des assistants numériques personnels communicants PDA (smartphones) ou des assistants numériques de navigation, pour déterminer des itinéraires dans le réseau routier. Le dispositif DEC reçoit périodiquement des informations de trafic relevées par des équipements de mesure ou diffusées par un serveur, et comprenant des informations prévisionnelles, telles que des informations calendaires, déterminées à partir de traitements sur des relevés permanents provenant des équipements de mesure de trafic sur le terrain, classées et mises à jour dans des historiques de mesures et exprimant des conditions de circulation sur des tronçons du réseau routier. L'unité centrale de traitement UC, telle qu'un processeur, contrôle l'exécution du procédé en activant et désactivant successivement les modules de traitement MT1, MT2 et MT3, et est reliée aux ou intègre les composants précités dans le dispositif. La base de données BD est liée au dispositif DEC, c'est-à-dire elle est soit intégrée dans le dispositif DEC, soit incorporée dans un serveur de gestion de base de données et reliée au dispositif DEC par une liaison locale ou distante. La base de données BD comprend notamment des informations nécessaires au fonctionnement du dispositif DEC de l'invention telles que des informations prévisionnelles classées dans des historiques de mesures, et des données cartographiques du réseau routier caractérisant le graphe d'arcs orientés GRT représentant le réseau routier, défini précédemment. La base de données BD comprend plus particulièrement une première représentation du graphe GRT(N,A,Fc) dans lequel le temps de parcours de chaque arc orienté du graphe est déterminé dynamiquement par application de la fonction dynamique Fc associée à chaque arc, et une deuxième représentation du graphe GRT(N,A,Binf) dans lequel le temps de parcours de chaque arc orienté du graphe est prédéterminé statiquement en fonction de la borne inférieure Binf associée à chaque arc. La base de données BD comprend également l'ensemble de noeuds de repère Ll-LN et les temps de parcours prédéterminés les plus courts des chemins sur le graphe GRT(N,A,Binf) reliant respectivement chaque noeud de repère Ll et chaque noeud Nn du graphe GRT, ainsi que les temps de parcours prédéterminés les plus courts des chemins sur le graphe GRT(N,A,Binf) reliant respectivement chaque noeud Nn du graphe GRT et chaque noeud de repère L1. Ces temps de parcours prédéterminés sont nécessaires à la détermination de sous-estimations de temps de parcours suivantes relatives à des fonctions de potentiel : - lr_av[NI] à lr_av[NN] : des fonctions de potentiel pour une recherche avant; pour un noeud Nn du graphe GRT, chaque fonction de potentiel ir_av[Nn] est relative à une sous-estimation du temps de parcours le plus court du chemin reliant le noeud Nn au noeud de destination Nd, prédéterminée en fonction de temps de parcours les plus courts de chemins reliant respectivement chaque noeud de repère de l'ensemble L et chaque noeud du graphe GRT, obtenus en n'utilisant que la borne inférieure Binf associée à chaque arc; et - lr_ar [Nl] à ir_ar [NN] : des fonctions de potentiel inverses pour une recherche arrière; pour un noeud Nn du graphe GRT, chaque fonction de potentiel 7L_ar [Nn] est relative à une sous- estimation du temps de parcours le plus court du chemin reliant le noeud source NS au noeud Nn, et prédéterminée en fonction de temps de parcours les plus courts de chemins reliant respectivement chaque noeud de repère de l'ensemble L et chaque noeud du graphe GRT, obtenus en n'utilisant que la borne inférieure Binf associée à chaque arc. La mémoire tampon MTP comporte notamment : - t[N1] à t[NN] : des temps de parcours les plus courts associés à des noeuds répertoriés du graphe GRT à explorer en mode de recherche avant; plus particulièrement pour un noeud répertorié Nn du graphe GRT, t[Nn] définit le temps de parcours le plus court du chemin reliant le noeud source NS au noeud Nn; - rt[NI] à rt[NN] : des temps de parcours inverses les plus courts associés à des noeuds répertoriés du graphe GRT à explorer en mode de recherche arrière; plus particulièrement pour un noeud répertorié Nn du graphe GRT, rt[Nn] définit le temps de parcours le plus court du chemin reliant le noeud Nn au noeud de destination Nd; - k[N1] à k[NN] : des clés de priorité de noeuds répertoriés du graphe GRT à explorer en mode de recherche avant; plus particulièrement pour un noeud répertorié Nn du graphe GRT, k[Nn] correspond à une estimation en mode de recherche avant du temps de parcours entre le noeud source et le noeud de destination passant par le noeud Nn, chaque clé de priorité k[Nn] correspond à la somme du temps de parcours le plus court t[Nn] du chemin reliant le noeud source NS au noeud répertorié Nn et une sous-estimation 7L_av[Nn] du temps de parcours le plus court du chemin reliant le noeud répertorié Nn au noeud de destination Nd; rk [Nl] à rk [NN] : des clés de priorité inverses de noeuds répertoriés du graphe GRT à explorer en mode de recherche arrière; plus particulièrement pour un noeud répertorié Nn du graphe GRT, rk[Nn] correspond à une estimation en mode de recherche arrière du temps de parcours entre le noeud source et le noeud de destination passant par le noeud Nn, chaque clé de priorité rk[Nn] correspond à la somme du temps de parcours inverse rt[Nn] le plus court du chemin reliant le noeud répertorié Nn au noeud de destination Nd et une sous-estimation 7L_ar[Nn] du temps de parcours le plus court du chemin reliant le noeud source NS au noeud répertorié Nn; - p[NI] à p[NN] : des identificateurs de noeuds parents déterminés en mode de recherche avant; un identificateur de noeud parent p[Nn] associé au noeud Nn est l'identificateur d'un noeud précédant le noeud Nn le long du chemin le plus court en temps reliant le noeud source NS au noeud de destination Nd sur le graphe GRT(N,A,Fc) évalué à partir de la fonction Fc; rp[NI] à rp[NN] : des identificateurs inverses de noeuds parents déterminés en mode de recherche arrière; un identificateur inverse de noeud parent rp[Nn] associé au noeud Nn est l'identificateur du noeud suivant le noeud Nn le long du chemin le plus court en temps reliant le noeud Nn au noeud de destination Nd sur le graphe GRT évalué par la borne inférieur Binf; - : la valeur minimum des clés de priorité de noeuds à explorer enregistrés en mode de recherche arrière; - : une borne supérieure du temps de parcours le plus court du chemin reliant le noeud source NS au noeud de destination Nd. Cette borne est déterminée comme le temps de parcours du chemin reliant le noeud source NS au noeud de destination Nd et passant par le premier noeud intermédiaire répertorié lors de la première phase de traitement. En variante, la borne supérieure peut être mise à jour durant l'exécution du procédé selon plusieurs réalisations possibles décrites ultérieurement. Les temps de parcours t[NI] à t [NN] et rt [Nl ] à rt[NN], les clés de priorité k[N1] à k[NN] et rk[N1] à rk [NN] , les identificateurs de noeuds parents p [NI] à p [NN] et rp [Nl ] à rp [NN] et les fonctions de potentiel lr_av[NI] à ir_av[NN] et lr_ar[NI] à ir_ar[NN] peuvent être respectivement enregistrés dans des tables de temps de parcours, des tables de clés de priorité, des tables de noeuds parents et des tables de fonctions de potentiel en association avec les identificateurs des noeuds correspondants. La mémoire de registre MR comprend des registres de noeuds utilisés lors de l'exécution du procédé selon l'invention, dont un registre QV de noeuds à explorer en mode de recherche avant contenant tous les noeuds répertoriés lors d'itérations précédentes du mode de recherche avant, un registre EV de noeuds déjà explorés en mode de recherche avant, un registre QR de noeuds à explorer en mode de recherche arrière contenant tous les noeuds répertoriés lors d'itérations précédentes du mode de recherche arrière, un registre ER de noeuds déjà explorés en mode de recherche arrière et un registre apte à enregistrer de manière ordonnée un résultat W composé des identificateurs de noeuds appartenant au chemin à déterminer entre le noeud source NS et le noeud de destination Nd ayant le temps de parcours le plus court à un instant donné T. Les noeuds Nqv et Nqr, avec 1 En référence à la figure 3, le procédé d'estimation du plus court chemin entre un noeud source NS et un noeud de destination Nd à un instant de départ donné Tp comprend trois phases de traitement successives, décrites de manière simplifiée aux étapes El à E16. La première phase de traitement, définie par un paramètre PH égal à 1, est mise en oeuvre dans le premier module de traitement MT1 qui exécute une recherche bidirectionnelle, aux étapes El à E6. Le module MT1 active à l'étape E2 le mode de recherche avant défini par un paramètre AV égal à 1, extrait à partir du noeud source NS l'un NX des noeuds du graphe GRT(N,A,Fc) du registre QV de noeuds à explorer en mode de recherche avant et dont l'estimation du temps de parcours entre le noeud source et le noeud de destination, passant par le noeud NX est la plus petite, avec 1 x IN1, et enregistre le noeud NX dans le registre EV de noeuds déjà explorés. Le module MT1 répertorie tous les noeuds Ny adjacents au noeud NX, c'est-à-dire constituant des extrémités orientées d'arcs dont l'origine est le noeud NX, non encore explorés en mode de recherche avant, avec 1 Le module MT1 active, à l'étape E3, le mode de recherche arrière défini par le paramètre AV égal à 0, extrait à partir du noeud de destination Nd l'un Nu des noeuds du graphe GRT(N,A,Binf) du registre QR de noeuds à explorer et dont l'estimation du temps de parcours entre le noeud source et le noeud de destination, passant par le noeud Nu est la plus petite, avec 1 u IN1, et l'enregistre dans le registre ER de noeuds déjà explorés. Le module MT1 répertorie tous les noeuds Nv adjacents au noeud Nu, c'est-à-dire constituant des origines d'arcs dont l'extrémité orientée est le noeud Nu, non encore explorés en mode de recherche arrière, avec 1 v 1NI, et enregistre les noeuds Nv non encore présents dans le registre QR. Les étapes E2 et E3 sont réitérées tant que, à l'étape E6, un même noeud Ny, Nv n'a pas été exploré et/ou répertorié dans les deux modes de recherche. Ce noeud correspond au premier noeud intermédiaire exploré dans les deux modes de recherche. Aux étapes E2 et E3, la première phase de traitement comprend notamment des déterminations itératives à l'instant de départ donné de plus courts temps de parcours t[Ny] reliant le noeud source NS à des noeuds Ny répertoriés, dits encore noeuds à explorer, en mode de recherche avant, et de plus courts temps de parcours inverses rt[NV] reliant des noeuds Nv répertoriés, dits encore noeuds à explorer, en mode de recherche arrière au noeud de destination. La première phase de traitement est activée tant qu'un même noeud Ny, Nv n'a pas été exploré et/ou répertorié dans les deux modes de recherche, ce qui est vérifié à l'étape E6. A l'étape E5, dès que le noeud Nd appartient au registre EV, le module de traitement MT1 retourne le chemin W ayant le plus court temps de parcours estimé en fonction des différents temps de parcours les plus courts précédemment déterminés des noeuds explorés. Le procédé est terminé. Dans le cas contraire, aux étapes E4 et E6, si le noeud Nd n'appartient pas au registre EV, le module MT2 continue l'itération des étapes E2 et E3. A l'étape E7, la deuxième phase de traitement, définie par le paramètre PH égal à 2, est mise en oeuvre dans le deuxième module de traitement MT2 qui continue l'exécution de la recherche bidirectionnelle aux étapes E7 à E12. Les étapes E2 et E8 relatives au mode de recherche avant sont exécutée de la même manière. L'exécution du mode de recherche arrière à l'étape E9 est sensiblement analogue à l'exécution de l'étape E3 lors de la première phase de traitement. En mode de recherche arrière, à l'étape E9, le module MT2 répertorie tous les noeuds NV, avec 1 v 1NI, adjacents au noeud Nu en cours d'exploration à l'itération courante, les noeuds Nv constituant des origines d'arcs dont l'extrémité orientée est le noeud Nu, non encore explorés en mode de recherche arrière, et non encore explorés en mode de recherche avant, les noeuds Nv n'appartenant pas aux registres ER et EV. Les étapes E8 et E9 sont réitérées tant qu'une condition spécifique CD relative au plus court temps de parcours entre le noeud source et le noeud de destination et passant par le premier noeud intermédiaire n'est pas satisfaite à l'étape E12. La condition CD est précisée ultérieurement en référence aux figures 4 à 6. Aux étapes E8 et E9, la deuxième phase de traitement comprend notamment des déterminations à l'instant de départ donné de plus courts temps de parcours t[Ny] reliant le noeud source NS à des noeuds Ny à explorer en mode de recherche avant, et de plus courts temps de parcours inverses rt[NV] reliant des noeuds NV à explorer en mode de recherche arrière et non explorés en mode de recherche avant au noeud de destination. Aux étapes E10 et E11, dès que le noeud Nd appartient au registre EV, le module de traitement MT2 retourne le chemin W ayant le plus court temps de parcours estimé en fonction des différents temps de parcours les plus courts précédemment déterminés des noeuds explorés. Le procédé est terminé. Dans le cas contraire, aux étapes E10 et E12, si le noeud Nd n'appartient pas au registre EV, le module MT2 continue l'itération des étapes E8 et E9. A l'étape E13, la troisième phase de traitement, définie par le paramètre PH égal à 3, est mise en oeuvre dans le troisième module de traitement MT3 qui exécute une recherche unidirectionnelle en mode de recherche avant. L'étape E14 est exécutée de manière sensiblement analogue aux étapes E2 et E8 relatives respectivement aux modes de recherche avant dans les deux premières phases de traitement. Les seuls noeuds Ny a répertorier dans la troisième phase de traitement sont des noeuds déjà explorés en mode de recherche arrière, c'est-à-dire appartenant au registre ER, et non encore explorés en mode de recherche avant, c'est-à-dire n'appartenant pas au registre EV. L'étape E14 est réitérée tant que, à l'étape E15, le noeud de destination Nd n'a pas été exploré en mode de recherche avant, le noeud Nd n'étant pas encore enregistré dans le registre EV. La troisième phase de traitement comprend notamment des déterminations des plus courts temps de parcours t [Ny] reliant le noeud source NS à des noeuds Ny déjà explorés en mode de recherche arrière à l'instant de départ donné. A l'étape E16, dès que le noeud Nd appartient au registre EV, le module de traitement MT3 retourne le chemin W ayant le plus court temps de parcours estimé en fonction des différents temps de parcours les plus courts précédemment déterminés des noeuds explorés. Le procédé est terminé. Le procédé d'estimation du plus court chemin dépendant du temps à un instant donné Tp reliant le noeud source NS au noeud de destination Nd est décrit plus en détail en référence aux figures 4 à 6, et comprend des étapes SO à S30. Le procédé comprend les trois phases de traitement successives dont les activations sont définies selon la valeur du paramètre PH égal respectivement à 1, 2 et 3. Le procédé comprend également le mode de recherche avant défini par le paramètre AV = 1 et exécuté itérativement dans les trois phases de traitement aux étapes S1 à S12, et le mode de recherche arrière défini par le paramètre AV = 0 et exécuté itérativement dans les deux premières phases de traitement aux étapes S13 à S25. A chaque itération d'un des deux modes de recherche, respectivement et successivement aux étapes S1 à S12 et S13 à S25, un seul noeud NX, Nu d'un des deux registres à explorer QV et QR est exploré. Dans une même phase de traitement, par exemple la première phase de traitement, l'exécution successive des deux modes de recherche est réitérée tant qu'une condition n'est pas satisfaite afin de passer à une autre phase de traitement. A l'étape initiale S0, l'unité centrale UC initialise divers registres, paramètres et indices nécessaires pour la mise en oeuvre du procédé selon l'invention. Les temps de parcours t[NI] à t [NN] et rt [Nl ] à rt[NN] et les clés de priorité k[N1] à k[NN] et rk [Nl ] à rk [NN] sont initialement égaux à l'infini. Les identificateurs des noeuds parents p[NI] à p[NN] et rp [Nl ] à rp [NN] sont vides. Relativement au mode de recherche avant, le registre QV ne comprend initialement que le noeud source NS, le registre EV est vide, et le temps de parcours le plus court t[NS] et la clé de priorité k[NS] du noeud source NS sont nuls. Relativement au mode de recherche arrière, le registre QR ne comprend initialement que le noeud de destination Nd, le registre ER est vide, et le temps de parcours inverse le plus court rt[Nd] et la clé de priorité inverse rk[Nd] du noeud de destination Nd sont nuls. Le paramètre PH définissant la phase de traitement est initialement mis à 1, le paramètre AV définissant le mode de recherche est également initialement mis à 1, indiquant de ce fait l'activation du mode de recherche avant. De même, la borne supérieure � définissant le temps de parcours du plus court chemin estimé entre le noeud source NS et le noeud de destination Nd et passant par le premier noeud intermédiaire répertorié lors de l'exécution de la première phase de traitement est initialement égale à l'infini. Le registre de résultat ordonné W est initialement vide. Au début de la première phase de traitement avec PH = 1 et de l'activation du mode de recherche avant avec AV = 1 aux étapes SO et S1, le module MT1 activé par l'unité centrale UC à l'étape S2 extrait de l'ensemble QV un noeud NX dont la clé de priorité k [NX] est la plus petite des clés de priorité k[Nqv] associées aux noeuds Nqv appartenant à l'ensemble QV. Lors de la première activation du mode de recherche avant, le noeud NX correspond au seul noeud inclus dans l'ensemble QV, le noeud N. Le module MT1 insère le noeud NX dans l'ensemble des noeuds explorés EV en mode de recherche avant à l'étape S3. Les étapes S4 à S12 sont réitérées afin que le module MT1 répertorie tous les arcs orientés reliant le noeud NX à d'autres noeuds, et ayant pour origine le noeud N. Lors de chaque itération, un noeud Ny avec 1 A l'étape S5, pour un arc AX,y, si le noeud Ny appartient à l'ensemble des noeuds explorés EV, le module MT1 traite un autre arc ayant pour origine le noeud NX en exécutant de nouveau l'étape S5, un noeud appartenant à l'ensemble EV étant considéré comme déjà exploré en mode de recherche avant. A l'étape S5, si le noeud Ny n'appartient pas à l'ensemble EV, le module MT1 exécute l'étape S6. A l'étape S6, si le noeud Ny n'appartient pas à l'ensemble QV, le module MT1 détermine, à l'étape S7, le temps de parcours le plus court t[Ny] reliant le noeud source NS au noeud Ny par la relation suivante : t[Ny] = t[NX]+ Fc(NX,Ny,t[NX]+To), avec - t [NX] le temps de parcours le plus court du chemin reliant le noeud NS au noeud NX, et - Fc (NX, Ny, t [NX] +To) la fonction Fc associée à l'arc AX,y définissant le temps de parcours prévisionnel de l'arc AX, y à l'instant t [NX] +To . Le temps t[Ny] est enregistré dans la mémoire tampon MTP en association avec l'identificateur du noeud Ny. Le module MT1 enregistre également dans la mémoire tampon MTP l'identificateur du noeud parent p [Ny] égal à l'identificateur du noeud NX en association à l'identificateur du noeud Ny, le noeud NX étant considéré comme le noeud parent courant du noeud Ny dans le chemin reliant le noeud source NS au noeud courant Ny. Le module MT1 détermine également à l'étape S7, la clé de priorité k [Ny] du noeud Ny par la relation suivante : k [Ny] = t [Ny] + 7r_av [Ny] , avec - t[Ny] le temps de parcours précédemment déterminé du noeud Ny, - 7r_av[Ny] la fonction de potentiel du noeud Ny déterminée en fonction des temps de parcours prédéterminés les plus courts des chemins reliant respectivement chaque noeud de repère Ll et chaque noeud Nn du graphe GRT selon des méthodes connues, cette fonction correspondant à une sous-estimation du temps de parcours le plus court du chemin reliant le noeud Ny au noeud de destination Nd. Le module MT1 insère ensuite le noeud Ny dans l'ensemble QV des noeuds à explorer. En revenant à l'étape S6, si le noeud Ny appartient à l'ensemble QV, le module MT1 compare la somme t [NX] +Fc (NX, Ny,t [NX] +To) au temps de parcours t [Ny] à l'étape S8. Si la somme t [NX]+Fc(NX,Ny,t[NX]+To) est strictement inférieure au temps de parcours t[Ny] alors à l'étape S9, le temps de parcours t[Ny], l'identificateur du noeud parent p [Ny] et la clé de priorité k [Ny] sont de nouveau déterminés de manière analogue à l'étape S7 et enregistrés par écrasement des anciennes valeurs dans la mémoire tampon MTP. En revanche à l'étape S8, si t [NX] + Fc (NX, Ny,t [NX] +To) t[Ny], aucune valeur t [Ny], k [Ny] et p [Ny] n'est modifiée. A l'étape S10 succédant à l'étape S7, S8 ou S9, le module MT1 vérifie que la condition suivante relative à l'étape E6 de la figure 3 est satisfaite : si le noeud Ny est déjà enregistré dans le registre de noeuds explorés ER relatif au mode de recherche arrière. Si le noeud répertorié Ny appartient au registre ER, indiquant de ce fait que le noeud Ny correspond au premier noeud intermédiaire exploré à la fois par le mode de recherche avant et le mode de recherche arrière, un premier chemin w reliant le noeud source au noeud de destination et passant par le noeud Ny est déterminé. Ce chemin est une concaténation d'un premier sous-chemin reliant le noeud source NS au noeud Ny ayant le temps de parcours le plus court t[Ny] déterminé en mode de recherche avant selon la fonction Fc et d'un deuxième sous-chemin reliant le noeud Ny au noeud de destination Nd ayant le temps de parcours inverse le plus court rt[Ny] déterminé en mode de recherche arrière selon la borne Binf. Le premier sous-chemin est déterminé à partir des identificateurs des noeuds parents p[NS] à p[Ny] en débutant par l'identificateur du noeud Ny. De même, le deuxième sous-chemin est déterminé à partir des identificateurs des noeuds parents inverses rp[Ny] à rp [Nd] en débutant par l'identificateur du noeud Ny La borne � est égale au temps de parcours le plus court du chemin w déterminé selon la fonction dépendant du temps Fc dans le graphe GRT(A,N,Fc), à l'étape S11. Le paramètre PH est mis à 2 ce qui indique l'activation de la deuxième phase de traitement. L'unité centrale UC désactive le premier module de traitement MT1 et active le deuxième module de traitement MT2, celui-ci continuant l'exécution du procédé de l'invention à l'étape S12. En revenant à l'étape S10 et lors de l'exécution de la première phase de traitement PH = 1, si le noeud Ny n'appartient pas au registre ER, le module MT1 continue l'exécution du procédé de l'invention à l'étape S12. A l'étape S12 succédant à l'étape S10 lors de la première phase de traitement, si tous les arcs reliés au noeud NX n'ont pas été traités, le module MT1 réitère les étapes S5 à S10 pour traiter un autre arc dont l'origine est le noeud N. Si tous les arcs ayant pour origine le noeud NX ont été traités, le module MT1 exécute l'étape S13 pour mettre à zéro le paramètre AV afin de désactiver le mode de recherche avant et inversement d'activer le mode de recherche arrière. Toujours lors de la première phase de traitement PH = 1, aux étapes S14 à S26, le mode de recherche arrière défini par AV = 0 est exécuté par le module MT1 de manière relativement analogue à l'exécution du mode de recherche avant aux étapes S1 à S12. A l'étape S14, le module MT1 vérifie que la première phase de traitement est activée et, à l'étape S15, extrait de l'ensemble QR un noeud Nu dont la clé de priorité inverse rk [Nu] est la plus petite des clés de priorité inverses rk[Nqr] associées aux noeuds Nqr appartenant à l'ensemble QR. Lors de la première activation du mode de recherche arrière, le noeud Nu correspond au seul noeud inclus dans l'ensemble QR, le noeud de destination Nd. Le module MT1 insère le noeud Nu dans l'ensemble des noeuds explorés ER en mode de recherche arrière à l'étape S16. Les étapes S18 à S25 sont réitérées afin que le module MT1 répertorie tous les arcs reliant le noeud Nu à d'autres noeuds et arrivant au noeud Nu. Lors de chaque itération, un noeud Nv avec 1 v IN1 est traité. A l'étape S18, le module MT1 vérifie notamment si le noeud Nv n'appartient pas au registre de noeuds explorés en mode de recherche arrière ER et ignore les autres conditions (Nv e ER ET Nv e EV) relatives à la deuxième phase de traitement exécutée par le module MT2 et présentée ultérieurement. A l'étape S18, pour un arc Av,u, si le noeud Nv appartient à l'ensemble des noeuds explorés ER, le module MT1 traite un autre arc ayant pour extrémité orientée le noeud Nu en exécutant de nouveau l'étape S18, un noeud appartenant à l'ensemble ER étant considéré comme déjà exploré en mode de recherche arrière. A l'étape S18, si le noeud Nv n'appartient pas à l'ensemble ER, le module MT1 exécute l'étape S19. A l'étape S19, si le noeud Nv n'appartient pas à l'ensemble QR, le module MT1 détermine, à l'étape S20, le temps de parcours inverse rt[Nv] le plus court du chemin reliant le noeud Nv au noeud de destination Nd par la relation suivante : rt [Nv] = rt [Nu] + Binf (Nv, Nu) , avec - rt[Nu] le temps de parcours le plus court du chemin reliant le noeud Nu au noeud Nd, et - Binf (NV,Nu) la borne inférieure de la fonction Fc associée à l'arc Av,u définissant le temps de parcours prévisionnel minimal de l'arc Av,u• Le temps rt[Nv] est enregistré dans la mémoire tampon MTP en association avec l'identificateur du noeud Nv. Le module MT1 enregistre également dans la mémoire tampon MTP l'identificateur du noeud parent inverse rp [Nv] égal à l'identificateur du noeud Nu en association à l'identificateur du noeud Nv, le noeud Nu étant considéré comme le noeud parent suivant courant du noeud Nv dans le chemin reliant le noeud Nv courant au noeud de destination Nd. Si un autre noeud a été identifié précédemment comme noeud parent, le module MT1 supprime de la mémoire MTP l'identificateur dudit noeud parent inverse en association à l'identificateur du noeud Nv. Le module MT1 détermine également à l'étape S20, la clé de priorité inverse rk [Nv] du noeud Nv par la relation suivante : rk[Nv] = rt[Nv]+ 7r_ar[Nv], avec rt[Nv] le temps de parcours précédemment déterminé du noeud Nv, et - 7r_ar[Nv] la fonction de potentiel inverse du noeud Nv déterminée en fonction des temps de parcours prédéterminés les plus courts des chemins reliant respectivement chaque noeud de repère Ll et chaque noeud Nn du graphe GRT selon des méthodes connues, cette fonction correspondant à une sous-estimation du temps de parcours le plus court du chemin reliant le noeud source NS au noeud N. Le module MT1 insère ensuite le noeud Nv dans l'ensemble QR des noeuds à explorer. En revenant à l'étape S19, si le noeud Nv appartient à l'ensemble QR, le module MT1 compare la somme rt [Nu] + Binf (NV, Nu) au temps de parcours rt [NV] à l'étape S21. Si la somme rt[Nu]+ Binf(NV,Nu) est strictement inférieure au temps de parcours rt[NV] alors à l'étape S22, le temps de parcours inverse rt [NV] , l' identificateur du noeud parent rp [NV] et la clé de priorité inverse rk[NV] sont de nouveau déterminés de manière analogue à l'étape S204 et enregistrés par écrasement des anciennes valeurs dans la mémoire tampon MTP. En revanche à l'étape S21, si rt [Nu]+ Binf (NV,Nu) rt [NV] , aucune valeur rt [NV] , rp [NV] et rk [NV] n'est modifiée. A l'étape S23 succédant à l'étape S20, S21 ou S22, le module MT1 vérifie que la condition suivante relative à l'étape E6 de la figure 3 est satisfaite : si le noeud Nv est déjà enregistré dans le registre de noeuds explorés EV relatif au mode de recherche avant. Si le noeud répertorié Nv appartient au registre EV, indiquant de ce fait que le noeud Nv correspond au premier noeud intermédiaire exploré à la fois par le mode de recherche avant et le mode de recherche arrière, un premier chemin w reliant le noeud source au noeud de destination et passant par le noeud Nv est déterminé. De manière analogue à l'étape S10, le chemin w est une concaténation d'un premier chemin reliant le noeud source NS au noeud Nv ayant le temps de parcours le plus court t [Nv] déterminé en mode de recherche avant selon la fonction Fc et d'un deuxième chemin reliant le noeud Nv au noeud de destination Nd ayant le temps de parcours inverse le plus court rt[NV] déterminé en mode de recherche arrière selon la borne Binf. La borne � est égale au temps de parcours le plus court du chemin w déterminé selon la fonction dépendant du temps Fc dans le graphe GRT(A,N,Fc), à l'étape S24. Le paramètre PH est mis à 2 ce qui indique l'activation de la deuxième phase de traitement. L'unité centrale UC désactive le premier module de traitement MT1 et active le deuxième module de traitement MT2, celui-ci continuant l'exécution du procédé de l'invention à l'étape S25. En revenant à l'étape S23 et lors de l'exécution de la première phase de traitement PH = 1, si le noeud Nv n'appartient pas au registre EV, le module MT1 continue l'exécution du procédé de l'invention à l'étape S25. A l'étape S25 succédant à l'étape S23 lors de la première phase de traitement, si tous les arcs reliés au noeud Nu n'ont pas été traités, le module MT1 réitère les étapes S18 à S23 pour traiter un autre arc dont l'extrémité orientée est le noeud Nu. Si tous les arcs ayant pour extrémité orientée le noeud Nu ont été traités, le module MT1 exécute l'étape S26 pour mettre à 1 le paramètre AV afin de désactiver le mode de recherche arrière et inversement d'activer le mode de recherche avant. Les deux modes de recherche sont successivement réitérés dans la première phase de traitement par le module MT1 tant que, à l'une des étapes S10 ou S23, le noeud répertorié Ny, Nv n'est pas respectivement dans le registre ER, EV. A l'étape S29, le module MT1 vérifie la condition suivante relative à l'étape E4 de la figure 3 : le noeud de destination Nd appartient-t-il au registre EV de noeuds explorés en mode de recherche avant. Si le noeud Nd appartient au registre EV, à l'étape S30, le module MT1 détermine à partir des identificateurs des noeuds parents p[NS] à p[Nd] le chemin le plus court en écrivant dans le registre W les identificateurs des noeuds du chemin en débutant par l'identificateur du noeud de destination Nd. Le module MT1 recherche en premier l'identificateur du noeud parent p[Nd] du noeud de destination Nd pour l'écrire dans le registre ordonné W à la suite de l'identificateur du noeud de destination Nd, puis recherche l'identificateur du noeud parent p [p [Nd] ] du noeud précédemment écrit p[Nd] dans le registre W et ainsi de suite, jusqu'à l'écriture de l'identificateur du noeud NS dans le registre W. Puis l'ensemble W est mémorisé dans la mémoire de registre MR. En revenant à l'étape S29, si le noeud Nd n'appartient pas au registre EV, le module MT1 exécute l'étape S1. La deuxième phase de traitement pour PH = 2 est exécutée par le module de traitement MT2 de manière relativement analogue à l'exécution de la première phase de traitement par le module de traitement MT1. Seules les étapes S11 et S24 ne sont plus sollicitées. En mode de recherche arrière, à l'étape S18, si le noeud Nv appartient au registre de noeuds explorés en mode de recherche arrière ER ou appartient au registre de noeuds explorés en mode de recherche avant EV, le module MT2 traite un autre arc ayant pour origine le noeud Nu en exécutant de nouveau l'étape S18. En mode de recherche arrière lors de la deuxième phase de traitement, seuls les noeuds non explorés par l'un des deux modes de recherche sont répertoriés. Aux étapes S7 et S9, le module MT2 enregistre dans la mémoire tampon MTP l'identificateur du noeud parent p[Ny] égal à l'identificateur du noeud NX en association à l'identificateur du noeud Ny, le noeud NX étant considéré comme le noeud parent courant du noeud Ny dans le chemin reliant le noeud source NS au noeud de destination Nd. De même, aux étapes S20 et S22, le module MT2 enregistre dans la mémoire tampon MTP l'identificateur du noeud parent inverse rp[NV] égal à l'identificateur du noeud Nu en association à l'identificateur du noeud NV, le noeud Nu étant considéré comme le noeud parent suivant courant du noeud NV dans le chemin reliant le noeud NV courant au noeud de destination Nd. A l'étape S27, le module MT2 vérifie que la condition spécifique suivante CD relative à l'étape E12 de la figure 3 est satisfaite : si la borne � est strictement supérieure à une variable R égale à la valeur de la plus petite clé de priorité inverse rk[Ngr] associées aux noeuds [Nqr] appartenant à l'ensemble QR. Si � > R, alors l'unité centrale UC met à 3 le paramètre PH ce qui activent la troisième phase de traitement ainsi que le troisième module de traitement MT3 et inversement désactive le deuxième module de traitement MT2.35 La troisième phase de traitement pour PH = 3 est exécutée par le troisième module de traitement MT3 qui traite uniquement le mode de recherche avant de manière sensiblement analogue à l'exécution des modes de recherche avant dans les deux premières phases de traitement aux étapes S1 à S13 et S27 à S30. A l'étape S5, si le noeud Ny appartient au registre de noeuds explorés en mode de recherche avant EV ou n'appartient pas au registre de noeuds explorés en mode de recherche arrière ER, le module MT3 traite un autre arc ayant pour origine le noeud NX en exécutant de nouveau l'étape S5. A la troisième phase de traitement, seuls les noeuds explorés en mode de recherche arrière et non encore explorés en mode de recherche avant sont répertoriés. Des modifications du procédé d'estimation du plus court chemin dépendant du temps avec un instant de départ donné Tp peuvent être implémentées afin de diminuer le temps de traitement de la deuxième phase de traitement en agissant notamment sur les valeurs de la borne � et de la variable R, comparées à l'étape S27 pour activer la troisième phase de traitement à l'étape S28. Selon une première variante la valeur R est multipliée par un coefficient arbitraire K1 impliquant, à l'étape S31, la comparaison suivante : > K1 R. Selon cette variante, le dispositif DEC estime une solution à K1 près, soit un temps de parcours estimé du chemin W qui n'est pas supérieur à K1 fois le temps de parcours réel du chemin W. Selon une deuxième variante, la valeur R est multipliée par un coefficient variable K2 déterminé en fonction du noeud source NS, du noeud de destination Nd et de l'instant de départ donné T. La valeur K2 est par exemple estimé à la fin de la première phase de traitement et dépend, par exemple, du rapport de temps entre un temps de parcours le plus court du chemin reliant le noeud Ns et le noeud de destination Nd et passant par le premier noeud intermédiaire répertorié, estimé de manière dynamique à partir du graphe GRT(N,A,Fc), et le temps de parcours de ce même chemin estimé de manière statique à partir du graphe GRT(N,A,Binf). Selon une troisième variante, la valeur est augmentée en estimant à chaque itération du procédé pour chaque noeud Nn une nouvelle fonction de potentiel n*_ar [Nn] afin de déterminer la clé de priorité inverse rk [Nn] = rt [Nn] + n*_ar [Nn] : n*ar [Nn] = max {iar [Nn], t [Nj ] + 7av [Nn] } , avec Ni correspondant au noeud exploré en mode de recherche avant lors de l'itération courante d'une des phases de traitement du procédé. Selon une quatrième variante, la valeur de � est mise à jour lors de la deuxième phase de traitement, PH = 2, en déterminant dynamiquement les temps de parcours d'autres chemins reliant le noeud source NS au noeud de destination Nd à partir du graphe(N,A,Fc) et en assignant à la borne � le temps minimum déterminé d'un de ces autres chemins. Par exemple, les temps de parcours de ces autres chemins sont déterminés en mode de recherche avant, itérativement ou périodiquement. Selon une cinquième variante, la valeur est augmentée d'une valeur déterminée de la manière suivante. En mode de recherche avant, pour chaque noeud NX en cours d'exploration, une différence est déterminée entre un temps de parcours, estimé dynamiquement à partir du graphe GRT(N,A,Fc), du plus court chemin dépendant du temps reliant les noeuds NS et Nd et passant par le noeud NX, et un temps de parcours du même chemin estimé statiquement à partir du graphe GRT(N,A,Binf). La différence minimum est ajoutée à la valeur R à chaque activation du mode de recherche avant. L'invention décrite ici concerne un procédé et un dispositif d'estimation du plus court chemin en temps de parcours dépendant d'un instant de départ donné entre un noeud source et un noeud destination. Selon une implémentation, les étapes du procédé de l'invention sont déterminées par les instructions d'un programme d'ordinateur incorporé dans un dispositif informatique tel que le dispositif d'estimation de plus court chemin DEC. Le programme comporte des instructions de programme qui, lorsque ledit programme est exécuté dans un processeur du dispositif dont le fonctionnement est alors commandé par l'exécution du programme, réalisent les étapes du procédé selon l'invention. En conséquence, l'invention s'applique également à un programme d'ordinateur, notamment un programme d'ordinateur enregistré sur ou dans un support d'informations lisible par un ordinateur et tout dispositif de traitement de données, adapté à mettre en oeuvre l'invention. Ce programme peut utiliser n'importe quel langage de programmation, et être sous la forme de code source, code objet, ou de code intermédiaire entre code source et code objet tel que dans une forme partiellement compilée, ou dans n'importe quelle autre forme souhaitable pour implémenter le procédé selon l'invention. Le support d'informations peut être n'importe quelle entité ou dispositif capable de stocker le programme. Par exemple, le support peut comporter un moyen de stockage ou support d'enregistrement sur lequel est enregistré le programme d'ordinateur selon l'invention, tel qu'une ROM, par exemple un CD ROM ou une ROM de circuit microélectronique, ou encore une clé USB, ou un moyen d'enregistrement magnétique, par exemple une disquette (floppy disc) ou un disque dur. REVENDICATIONS 1 - Procédé pour estimer le plus court chemin (W) en temps de parcours dépendant d'un instant de départ donné (T0) entre un noeud source (NS) et un noeud de destination (Nd) appartenant à un graphe orienté (GRT) représentatif d'un réseau routier et contenant des noeuds (N1-NN) et des arcs orientés (AX, y, Av, u) entre les noeuds, caractérisé en ce qu'il comprend une recherche bidirectionnelle de noeuds le long du plus court chemin incluant itérativement une recherche avant et une recherche arrière jusqu'à ce que le noeud de destination (Nd) soit exploré en recherche avant (S29), la recherche avant déterminant (S1, S12) des plus courts temps de parcours (t[Ny]) entre le noeud source et des noeuds à explorer (Ny) selon des fonctions de temps de parcours prévisionnel (Fc) variant au cours du temps associées respectivement aux arcs du graphe orienté (GRT) reliant les noeuds à explorer, et la recherche arrière déterminant (S13, S25) des plus courts temps de parcours (rt[NV]) entre des noeuds à explorer (NV) et le noeud de destination selon des fonctions statiques (Binf) associées respectivement aux arcs du graphe orienté (GRT) reliant les noeuds à explorer et correspondant à des temps de parcours prévisionnels minimaux sur les arcs reliant les noeuds à explorer, le plus court chemin (W) en temps de parcours entre le noeud source (NS) et le noeud de destination (Nd) étant estimé (S30) en recherche avant. 2 - Procédé conforme à la revendication 1, selon lequel la recherche bidirectionnelle de noeuds comprend une première phase de traitement (E1-E6) au cours de laquelle chaque noeud à explorer en recherche avant est l'extrémité orientée d'un arc relié à un noeud précédemment exploré en recherche avant et chaque noeud à explorer en recherche arrière est l'origine d'un arc relié à un noeud précédemment exploré en recherche arrière, et une deuxième phase de traitement (E7-E12) activée dès qu'un premier noeud intermédiaire est exploré dans les deux recherches (E6) pendant la première phase de traitement et au cours de laquelle chaque noeud à explorer en recherche avant est l'extrémité orientée d'un arc relié à un noeud précédemment exploré en recherche avant et chaque noeud à explorer en recherche arrière est l'origine d'un arc relié à un noeud précédemment exploré en recherche arrière et est distinct des noeuds explorés en recherche avant. 3 - Procédé conforme à la revendication 2, selon lequel la recherche bidirectionnelle de noeuds comprend une troisième phase de traitement (E13-E16) activée dès qu'une condition relative au plus court temps de parcours entre le noeud source et le noeud de destination et passant par le premier noeud intermédiaire est satisfaite (E12, S27). 4 - Procédé conforme à la revendication 3, selon lequel la condition (CD) consiste en ce que le plus court temps de parcours entre le noeud source et le noeud de destination passant par le premier noeud intermédiaire soit inférieur à une valeur minimum d'une des clés de priorité associées aux noeuds à explorer en recherche arrière, chaque clé de priorité d'un (NV) de ces derniers noeuds étant égale à une somme du plus court temps de parcours déterminé entre ledit noeud (NV) et le noeud de destination (Nd) et une sous-estimation (ir_ar[Nn]) du plus court temps de parcours entre le noeud source (NS) et ledit noeud (Nv). - Dispositif d'estimation (DEC) pour estimer 5 le plus court chemin (W) en temps de parcours dépendant d'un instant de départ donné (Te) entre un noeud source (NS) et un noeud de destination (Nd) appartenant à un graphe orienté (GRT) représentatif d'un réseau routier et contenant des noeuds (N1-NN) et des arcs orientés (AX,y, Av,u) entre les noeuds, caractérisé en ce qu'il comprend un moyen (UC) pour rechercher bidirectionnellement des noeuds le long du plus court chemin incluant iterativement une recherche avant et une recherche arrière jusqu'à ce que le noeud de destination (Nd) soit exploré en recherche avant, des moyens (MT1, MT2, MT3) déterminant en recherche avant des plus courts temps de parcours (t[Ny]) entre le noeud source et des noeuds à explorer (Ny) selon des fonctions de temps de parcours prévisionnel (Fc) variant au cours du temps associées respectivement aux arcs du graphe orienté (GRT) reliant les noeuds à explorer, et des moyens (MT1, MT2) déterminant en recherche arrière des plus courts temps de parcours (rt[Nv]) entre des noeuds à explorer (Nv) et le noeud de destination selon des fonctions statiques (Binf) associées respectivement aux arcs du graphe orienté (GRT) reliant les noeuds à explorer et correspondant à des temps de parcours prévisionnels minimaux sur les arcs reliant les noeuds à explorer, le plus court chemin (W) en temps de parcours entre le noeud source (NS) et le noeud de destination (Nd) étant estimé en recherche avant. 6 - Programme d'ordinateur apte à être mis en oeuvre dans un dispositif informatique (DEC) et destiné à estimer le plus court chemin (W) en temps de parcours dépendant d'un instant de départ donné (Te) entre un noeud source (NS) et un noeud de destination (Nd) appartenant à un graphe orienté (GRT) représentatif d'un réseau routier et contenant des noeuds (N1-NN) et des arcs orientés (Ax,y, Av,u) entre les noeuds, ledit programme étant caractérisé en ce qu'il comprend des instructions qui, lorsque le programme est exécuté dans ledit dispositif, réalisent : une recherche bidirectionnelle de noeuds le long du plus court chemin incluant itérativement une recherche avant et une recherche arrière jusqu'à ce que le noeud de destination (Nd) soit exploré en recherche avant (S29), la recherche avant déterminant (Si, S12) des plus courts temps de parcours (t[Ny]) entre le noeud source et des noeuds à explorer (Ny) selon des fonctions de temps de parcours prévisionnel (Fc) variant au cours du temps associées respectivement aux arcs du graphe orienté (GRT) reliant les noeuds à explorer, et la recherche arrière déterminant (S13, S25) des plus courts temps de parcours (rt[NV]) entre des noeuds à explorer (NV) et le noeud de destination selon des fonctions statiques (Binf) associées respectivement aux arcs du graphe orienté (GRT) reliant les noeuds à explorer et correspondant à des temps de parcours prévisionnels minimaux sur les arcs reliant les noeuds à explorer, le plus court chemin (W) en temps de parcours entre le noeud source (NS) et le noeud de destination (Nd) étant estimé (S30) en recherche avant.