Brevet FR2876819A1 — publié le 20060421

P10-1673 1 PROCEDE DE DETERMINATION D'UN ITINERAIRE EN FONCTION DE L'INDICE DE SINUOSITE La présente invention concerne un procédé de détermination d'itinéraires entre un point de départ (a) et un point d'arrivée ((3) pour système numérique de cartographie routière constitué d'un ensemble de tronçons et/ou de noeuds, dans lequel l'itinéraire établi tient compte du niveau de sinuosité indiqué par l'utilisateur lors de sa requête. On connaît de multiples façons de calculer les itinéraires permettant d'établir la façon la plus avantageuse, pour un usager du système routier, de se déplacer d'un point de départ à un point d'arrivée donnés. Différents critères permettent aujourd'hui aux différents types d'usagers de choisir leurs parcours en privilégiant certains critères, et/ou en pénalisant certains autres critères. Par exemple, on peut souhaiter effectuer un itinéraire par un trajet favorisant le passage par des autoroutes, ou minimisant la consommation de carburant, etc. Toutefois, aucun critère relatif à la sinuosité d'une route ou d'une portion de route n'est aujourd'hui pris en considération. Pourtant, ce dernier point peut être déterminants quant au choix d'un itinéraire plutôt qu'un autre. Par exemple, l'utilisation prolongée d'une route sinueuse peut entraîner une fatigue plus importante que sur une route plus rectiligne. Certains conducteurs ou passagers âgés et/ou malades peuvent souffrir du mal des transports et subir des symptômes tels que des nausées, vertiges ou étourdissements, etc. Dans le passé, le cartographe renseignait, à partir d'une carte papier, les données relatives à la sinuosité de certaines routes ou tronçons de route. Ainsi, certaines bases de données servant à la modélisation de réseaux routiers comportent encore de telles indications.Toutefois, ces informations ayant été obtenues à partir d'une carte papier, elles sont peu précises du fait de la généralisation de la représentation sur la carte et subjectives. De plus, le maintien à jour de telles données, en raison de la modification du réseau routier, est très fastidieux et très coûteux. P10-1673 2 Par ailleurs, les sources de données actuelles, pour la plupart à grande échelle (c'est-à-dire une échelle comportant un très grand niveau de détails), ne comportent pas de telles indications. Compte tenu de l'envergure titanesque que cela représenterait, étant donné le nombre d'objets des bases de données routières actuelles, il est inimaginable de renseigner (ou de mettre à jour) manuellement ces bases afin de les doter des données relatives à la sinuosité. L'évaluation de l'indice de sinuosité implique que l'on puisse prendre en compte tous les détails du tracé de tous les tronçons. En effet, simplification de la représentation de certains lacets, ou boucles ou autres virages, dans les modèles à petite échelle (c'est-à-dire une échelle comportant un faible niveau de détails), produit des erreurs souvent importantes pour l'évaluation de la sinuosité et par conséquent du temps de trajet qui en découle. Ainsi, ni les techniques manuelles, ni les technologies numériques classiques ne permettent actuellement d'évaluer de façon précise l'indice 1s de sinuosité de tronçons ou trajets donnés, en particulier les trajets très sinueux et longs, où la vitesse réelle du véhicule peut varier de façon considérable par rapport à celle calculée. Pour pallier ces différents inconvénients, l'invention propose un procédé de détermination d'itinéraires entre un point de départ (a) et un point d'arrivée (f3) pour système numérique de cartographie routière constitué d'éléments numériques de modélisation d'un réseau routier comportant un ensemble de tronçons représentatifs dudit réseau routier et des données relatives à la sinuosité pour au moins une portion de ces tronçons, et comprenant les étapes suivantes: -on reçoit une requête d'itinéraire comportant: -les points de départs et d'arrivée; -une sélection du niveau de sinuosité à privilégier; -on identifie une pluralité d'itinéraires; -on attribue à chacun des dits itinéraires potentiels une cote en fonction de son indice 30 de sinuosité global établi à partir de l'indice de sinuosité de chacun des tronçons constituant lesdites routes potentielles; P10-1673 3 -on élit l'itinéraire potentiel dont l'indice de sinuosité correspond le mieux au niveau de sinuosité de la requête. Une telle méthode permet de classer ou catégoriser les routes ou portions de routes s susceptibles d'être empruntées par un usager, afin de lui permettre de pouvoir considérer cet aspect dans son choix de route ou d'itinéraire. En fonction de la situation, du temps dont il dispose, de sa forme physique, etc, un usager pourra donc choisir un itinéraire plus ou moins sinueux. Dans certains cas, par exemple lors de voyages avec de jeunes enfants à bord, ou pour des usagers plus sensibles ou en moins bonne santé, des itinéraires moins sinueux seront privilégiés, même parfois au détriment du temps de trajet. Il est ainsi possible d'éviter les inconvénients ou symptômes liés au mal des transports. 1s Dans d'autres cas, les utilisateurs vont souhaiter favoriser un itinéraire passant par exemple par une route sinueuse, car une telle route correspond parfois à un relief accidenté et souvent pittoresque voire même enchanteur, comme par exemple les gorges du Tarn. Pour les adeptes du plaisir de conduire, un itinéraire plus sinueux signifie souvent une conduite pouvant éventuellement être plus variée et donc plus agréable. Selon un mode de réalisation avantageux de l'invention, le type de sinuosité indique une préférence pour la route potentielle possédant une sinuosité sensiblement la plus élevée ou sensiblement la plus faible. Selon un autre mode de réalisation avantageux de l'invention, le type de sinuosité indique une préférence pour la route potentielle possédant une sinuosité sensiblement la plus élevée, sensiblement la plus faible, ou une sinuosité intermédiaire. En effet, la sélection éventuelle du niveau de sinuosité le plus faible implique pour certains itinéraires des détours considérables. Dans de tels cas, un P10-1673 4 compromis peut être établi entre le niveau de sinuosité et la distance totale à parcourir. De manière avantageuse, ladite cote correspond à l'indice moyen de sinuosité de l'itinéraire, évalué grâce à la relation suivante: Fis(IStronçon X Ltronçon)/ Ltotale, dans laquelle IStronçon correspond à l'indice de sinuosité d'un tronçon donné, Ltronçon correspond à sa longueur, et Ltotale correspond à la longueur totale de l'itinéraire. De manière préférentielle, l'étape d'identification de la pluralité d'itinéraires potentiels comprend en outre les étapes suivantes: -a) on explore les tronçons adjacents au noeud (ou point) de départ ou au noeud retenu de façon à déterminer le coût de chacun des noeuds auxquels ces tronçons conduisent; -b) parmi ces noeuds, on sélectionne celui dont le coût est le plus favorable en fonction des critères établis (le plus court, le plus rapide, le plus économique, favorisant les autoroutes, etc, ou encore une combinaison de ces critères) ; -c) on reprend l'étape a et on poursuit ladite exploration jusqu'à ce que le noeud dont le coût est le plus favorable corresponde au point d'arrivée. Les noeuds peuvent être soit des noeuds correspondant à des points ou données effectives des éléments de modélisation, ou encore des noeuds virtuels, correspondant à des intersections de tronçons. Pendant cette phase d'exploration, la multiplicité de noeuds valorisés implique qu'une multiplicité d'itinéraires alternatifs sont en fait évalués ou considérés. On retient en fin de procédé un ou plusieurs itinéraires susceptibles de satisfaire les critères de la requête. P10-1673 5 De manière avantageuse, l'exploration des noeuds est réalisée à l'aide de l'algorithme de Dijkstra. Selon un autre mode de réalisation avantageux, l'exploration des noeuds est réalisée à l'aide de l'algorithme de FORD. L'itinéraire préférentiel est celui pour lequel la somme des cotes ou coûts entre le point de départ et le point d'arrivée est optimale. Bien évidemment, l'établissement de la cote ou coût global peut être fait en tenant compte d'un nombre de paramètres plus ou moins important, selon le cas. Par exemple, on peut considérer l'indice de sinuosité seul, ou avec d'autres paramètres tels que la distance parcourue, les péages, le temps de parcours, l'économie d'essence, etc. Chacun de ces différents paramètres peut prendre une importance plus ou moins déterminante, en associant à chacun des pondérations plus ou moins importantes, selon le cas, par exemple en fonction d'un ou plusieurs souhaits de l'utilisateur. L'invention prévoit également un logiciel comprenant des éléments de code programmés pour la mise en oeuvre du procédé préalablement décrit, lorsque ledit logiciel est chargé dans un système informatique et exécuté par ledit système informatique. Ce logiciel peut être sous forme d'un produit enregistré sur un support lisible par un système informatique, comprenant des éléments de code programmés tel qu'énoncé ci-dessus. L'invention prévoit par ailleurs un dispositif de détermination d'itinéraires entre un point de départ (a) et un point d'arrivée ((3) pour système numérique de cartographie routière constitué d'éléments numériques de modélisation d'un réseau routier comportant un ensemble de tronçons représentatifs dudit réseau routier et des données relatives à la sinuosité pour au moins une portion de ces tronçons, comprenant: P10- 1673 6 -une unité d'entrée des données, destinée à recevoir, les données associées à un point de départ a, un point d'arrivée R et un niveau de sinuosité souhaité pour l'itinéraire à établir; -un accès à une unité de stockage comportant un ensemble d'éléments de s modélisation d'un réseau routier; -une unité de calcul agencée pour identifier une pluralité de routes permettant chacune de relier les points de départ et d'arrivée en prenant en compte l'indice de sinuosité des tronçons de chacune des routes. lo De manière avantageuse, l'indice de sinuosité est utilisé afin de pondérer différemment des trajets comportant un fort indice de sinuosité par rapport à des trajets comportant un indice de sinuosité inférieur. Ainsi, à l'aide de ce dispositif, il est possible de faire en sorte que les trajets moins 15 sinueux (à faible indice de sinuosité) soient favorisés, au détriment de trajets plus sinueux (dont l'indice de sinuosité est plus élevé). De façon similaire, selon un autre mode de réalisation, il est possible de faire en sorte que les trajets plus sinueux (à fort indice de sinuosité) soient favorisés, au détriment 20 de trajets moins sinueux (dont l'indice de sinuosité est plus faible). Selon un mode de réalisation avantageux, le dispositif comporte une unité de guidage, agencée de façon à générer des informations de guidage en fonction des éléments cartographiques de la route sélectionnée. L'invention prévoit enfin un système informatique comprenant un dispositif tel que préalablement décrit. Tous les détails de réalisation sont donnés dans la description qui suit, complétée par 3o les figures 1 à 3 dans lesquelles: P10-1673 7 la figure 1 présente un exemple de tronçons sur lequel les points intermédiaires (de 1 à 9) sont indiqués. la figure 2 illustre une représentation d'une portion d'un réseau routier dans la région 5 de Lachaux, avec au droit de chaque tronçon de la base de données, son indice de sinuosité ; la figure 3 montre une représentation d'une portion d'un réseau routier avec trois possibilités d'itinéraires entre Vinça et Amélie-les-Bains, possédant trois indices de 10 sinuosité qui diffèrent de manière significative. Dans la présente description, les termes suivants sont utilisés notamment avec les significations suivantes: On désigne noeud un point d'intersection entre un premier élément de réseau cartographique ou routier (ou autre réseau) et un second élément d'un tel réseau, notamment l'intersection entre une pluralité de voies routières. Un noeud désigne également un point de changement physique ou qualitatif d'un tronçon, comme par exemple un passage de deux à trois voies, un changement de la limitation de vitesse, une zone (même temporaire) faisant l'objet de travaux, un point de rupture tel une frontière, etc. On désigne tronçon une portion de voie entre deux noeuds. On désigne carrefour une intersection de plusieurs routes au même niveau. On désigne un itinéraire un sous-ensemble de points issus des éléments de modélisation d'un réseau routier, créant un lien entre des données de façon à leur permettre de modéliser ou représenter un trajet ou parcours sur ledit réseau routier permettant de relier un point de départ et un point d'arrivée. Ce sous-ensemble est constitué par les données relatives aux tronçons permettant de relier le départ et P10- 1673 8 l'arrivée. Par données relatives aux tronçons, on entend les identifications, les longueurs des tronçons et les coordonnées spatiales. Ce sous-ensemble peut servir à représenter ledit itinéraire sous différentes formes, par exemple au moyen d'une représentation graphique, de préférence sous la forme d'une carte comprenant le point de départ, le point d'arrivée, et les tronçons formant ledit itinéraire, ou sous la forme d'une feuille de route ou liste d'instructions, comportant une énumération ou suite d'instructions écrites ou représentées par des pictogrammes, expliquant à un éventuel conducteur d'un véhicule, les différentes lo étapes à suivre pour effectuer ledit itinéraire. Selon le mode préférentiel de réalisation, on calcule la densité de points intermédiaires pour 100m de chaque tronçon mesurant plus de 50m et ayant plus de 5 points intermédiaires. En fonction de cette densité, on applique par la suite des facteurs de pénalisation affectant le temps de parcours (et bien évidemment la vitesse) des différents tronçons. La figure 1 montre un exemple de tronçon sur lequel les points intermédiaires (de 1 à 9 dans cet exemple) sont représentés. Un point intermédiaire permet de représenter un changement d'orientation entre deux tronçons ou entre deux portions d'un même tronçons. Ainsi, un tronçon représentant une route rectiligne comporte peu de points intermédiaires, tandis qu'un tronçon représentant une route sinueuse comporte une pluralité de points intermédiaires. Selon le mode de réalisation préférentiel, on applique ensuite les niveaux de pénalités comme suit: si d 3o Le tableau ci-après présente un exemple de données obtenues grâce à la méthode selon l'invention. Ce tableau comprend les différents tronçons permettant de relier P10-1673 9 Chateldon à Vignolle-Basse. Le tableau comporte les identifiants de chacun des tronçons, leur longueurs, les indices de sinuosité calculés, le temps de parcours standard (sans tenir compte de la sinuosité), et le temps ou durée de parcours obtenu en tenant compte de la sinuosité. Cet exemple montre bien que les temps de parcours des tronçons à indice de sinuosité élevé sont susceptibles d'être fortement corrigés grâce à la méthode selon l'invention. Id tronçon longueur indice indice Durée durée (mètres) sinuosité * long. origine finale Chateldon 517640122 42 2 84 70 70 517640127 34 6 204 53 64 517691733 104 5 520 157 188 517643257 52 4 208 79 87 517694716 30 0 0 45 45 517643250 129 3 387 194 213 517599346 64 0 0 64 64 517688011 786 3 2358 786 865 517641069 3397 4 13588 3397 3737 517662762 593 4 2372 593 652 517655149 1221 5 6105 1221 1465 Vignole- 6452 Indice moyen 25826 6659 7450 Basse 6,4km 4,0 6m40s 7m27s vitesse moyenne 58 52 Le parcours présenté dans de tableau est par ailleurs illustré à la figure 2. Cette io figure illustre un exemple d'éléments de modélisation présentés sous la forme d'une carte, pour un secteur donné, à savoir les alentours de Lachaux. Les indices de sinuosité des tronçons, obtenus au moyen de la méthode selon l'invention, sont indiqués sur la carte. On note que les tronçons comportant un indice élevé sont nombreux. La possibilité de pouvoir tenir compte de l'impact de cette sinuosité sur les itinéraires est donc particulièrement importante pour des secteurs tels que celui illustré dans cet exemple. Enfin, le tableau qui suit (ci-dessous) ainsi que la figure 3 présentent un exemple d'utilisation des données de sinuosité pour effectuer des calculs d'iti et des temps de P10-1673 10 parcours de façon très précis. Trois itinéraires différents, permettant chacun de relier Amélie-lesBains à Vinça, ont été établis. En fonction d'une requête précise de l'utilisateur, il est possible de fournir l'itinéraire correspondant le mieux, à savoir avec un indice de sinuosité le plus ou le moins élevé, voire un indice intermédiaire. Autrement, plusieurs itinéraires, avec des indices de sinuosité différents, peuvent être suggérés. L'utilisateur a la possibilité de retenir celui de son choix. La figure 3 illustre très bien l'impact que peut avoir la sinuosité sur un itinéraire entre deux points donnés. Le procédé selon l'invention permet aux utilisateurs de prendre en compte de type de situation en permettant de générer des itinéraires précis et de calculer précisément le 15 temps de parcours. De façon générale, les itinéraires sont établis en procédant à l'identification d'une pluralité de routes. Ceci est effectué en sélectionnant un premier élément de modélisation du réseau routier, de préférence un noeud, à proximité du point de départ (ci) et un second élément de modélisation du réseau routier, de préférence un noeud, à proximité du point d'arrivée (R), en identifiant une pluralité de routes, chacune consistant en une pluralité d'éléments de modélisation reliés du premier élément au second élément, et en recherchant au moins un élément intermédiaire pour chacune desdites routes dans ledit ensemble d'éléments de modélisation de réseau routier. On utilise par exemple un algorithme de type connu, tel que celui de Dijkstra ou de Ford afin d'identifier les itinéraires susceptibles de remplir les critères de la requête. Itinéraire d'Amélie-les-Bains à Vinça iti N distance temps indice de km minutes sinuosité Variante 1 (Prunet) 43,6 51 4,57 Variante 2 (Llauro) 46,2 52 3,14 Variante 3 (Le Boulou) 53,2 53 1,99 P10-1673 11 REVENDICATIONS 1. Procédé de détermination d'itinéraires entre un point de départ (a) et un point d'arrivée (R) pour système numérique de cartographie routière constitué d'éléments numériques de modélisation d'un réseau routier comportant un ensemble de tronçons représentatifs dudit réseau routier et des données relatives à la sinuosité pour au moins une portion de ces tronçons, et comprenant les étapes suivantes: -on reçoit une requête d'itinéraire comportant: lo -les points de départs et d'arrivée; -une sélection du niveau de sinuosité à privilégier; -on identifie une pluralité d'itinéraires potentiels; -on attribue à chacun des dits itinéraires potentiels une cote en fonction de son indice de sinuosité global établi à partir de l'indice de sinuosité de chacun des tronçons 15 constituant lesdites routes potentielles; -on élit l'itinéraire potentiel dont l'indice de sinuosité correspond le mieux au niveau de sinuosité de la requête. 2. Procédé de détermination d'itinéraires selon la revendication 1, dans lequel le niveau de sinuosité indique une préférence pour l'itinéraire potentiel possédant une sinuosité sensiblement la plus élevée ou sensiblement la plus faible. 3. Procédé de détermination d'itinéraires selon la revendication 1, dans lequel le niveau de sinuosité indique une préférence pour l'itinéraire potentiel possédant une sinuosité sensiblement la plus élevée, sensiblement la plus faible, ou une sinuosité intermédiaire. 4. Procédé de détermination d'itinéraires selon l'une des revendications précédentes, dans lequel ladite cote correspond à l'indice moyen de sinuosité de l'itinéraire, évalué grâce à la relation suivante: Eis(IStronçon X Ltronçon)/ Ltotale, dans laquelle IStronçon correspond à l'indice de sinuosité d'un tronçon donné, P10-1673 12 Ltronçon correspond à sa longueur, et Ltotale correspond à la longueur totale de l'itinéraire. 5. Procédé de détermination d'itinéraires selon l'une des revendications s précédentes, dans lequel l'étape d'identification de la pluralité d'itinéraires potentiels comprend en outre les étapes suivantes: -a) on explore les tronçons adjacents au noeud (ou point) de départ ou au noeud retenu de façon à déterminer le coût de chacun des noeuds auxquels ces tronçons conduisent; -b) parmi ces noeuds, on sélectionne celui dont le coût est le plus favorable en fonction des critères établis; (le plus court, le plus rapide, le plus économique, favorisant les autoroutes, etc, ou encore toute combinaison de ces critères) -c) on reprend l'étape a et on poursuit ladite exploration jusqu'à ce que le noeud dont le coût est le plus favorable corresponde au point d'arrivée. 6. Procédé de détermination d'itinéraires selon la revendication 5, dans lequel l'exploration des noeuds est réalisée à l'aide de l'algorithme de Dijkstra 7. Procédé de détermination d'itinéraires selon la revendication 5, dans lequel l'exploration des noeuds est réalisée à l'aide de l'algorithme de FORD. 8. Logiciel comprenant des éléments de code programmés pour la mise en oeuvre du procédé selon l'une des revendication 1 à 7, lorsque ledit logiciel est chargé dans un système informatique et exécuté par ledit système informatique. 9. Logiciel sous forme d'un produit enregistré sur un support lisible par un système informatique, comprenant des éléments de code programmés selon la revendication 8. 10. Dispositif de détermination d'itinéraires entre un point de départ (a) et un point d'arrivée (13) pour système numérique de cartographie routière constitué d'éléments P10-1673 13 numériques de modélisation d'un réseau routier comportant un ensemble de tronçons représentatifs dudit réseau routier et des données relatives à la sinuosité pour au moins une portion de ces tronçons, et comprenant les étapes suivantes: -une unité d'entrée des données, destinée à recevoir, les données associées à un point de départ a, un point d'arrivée p et un niveau de sinuosité souhaité pour l'itinéraire à établir; -un accès à une unité de stockage comportant un ensemble d'éléments de modélisation d'un réseau routier; -une unité de calcul agencée pour identifier une pluralité de routes permettant 10 chacune de relier les points de départ et d'arrivée en prenant en compte l'indice de sinuosité des tronçons de chacune des routes. 11. Dispositif de calcul d'itinéraire selon la revendication 10, dans lequel l'indice de sinuosité est utilisé afin de pondérer différemment des trajets comportant un fort 1s indice de sinuosité par rapport à des trajets comportant un indice de sinuosité inférieur. 12. Dispositif de calcul d'itinéraire selon l'une des revendications 10 ou 11, comportant une unité de guidage, agencée de façon à générer des informations de 20 guidage en fonction des éléments cartographiques de la route sélectionnée.