FR 3057951 A1 20180427 FR 1660326 A 20161025 1 La présente invention concerne le domaine de la navigation des véhicules, et en particulier le domaine de l'éco-navigation (de l'anglais « eco-routing »), qui détermine un itinéraire minimisant l'énergie consommée par le véhicule pour un itinéraire. Selon l'Agence Internationale de l'Energie, plus du 50% du pétrole utilisé dans le monde est destiné au secteur des transports, dont plus des trois quarts pour les transports routiers. Selon cette même agence, le secteur des transports est responsable pour presque un quart (23.8%) des émissions de gaz à effet de serre et plus d'un quart (27.9%) des émissions de CO2 en Europe en 2006. Il est donc de plus en plus important d'augmenter l'efficacité énergétique des déplacements routiers, pour réduire la consommation d'énergie, qu'il s'agisse d'énergies fossile ou électrique. Pour y parvenir les systèmes d'assistance à la conduite (ADAS, de l'anglais « Advanced Driver Assistance Systems ») représentent une solution prometteuse, car économique (car on peut utiliser simplement le téléphone intelligent du conducteur) et non intrusive (car on n'a pas besoin d'apporter des modifications aux composants mécaniques du véhicule). Parmi les systèmes d'assistance aux conducteurs destinés à l'amélioration de l'efficacité énergétique de la conduite, on trouve principalement deux stratégies qui peuvent et devraient être complémentaires : l'éco-conduite et l'éco-navigation (ou « éco-routing »). L'éco-conduite consiste à optimiser en termes de dépense énergétique un profil de vitesse au long d'un parcours. Ce profil de vitesse est ensuite suggéré au conducteur, qui peut réduire la consommation sur son trajet en suivant la trajectoire conseillée. Un exemple de procédé concernant l'éco-conduite est décrit dans la demande de brevet FR 2994923 (US 9286737). L'éco-navigation consiste à identifier la route optimale pour aller d'un point d'origine à un point de destination en minimisant la dépense énergétique, et en prenant en compte une multitude de paramètres comme les caractéristiques du véhicule, les caractéristiques topologiques du réseau routier, les conditions de trafic, etc.. L'éco-navigation a été envisagée dans les demandes de brevet suivants : US 2012123657, US 2012179315, US 2012066232, US 9091560. Toutefois, ces demandes de brevet ne précisent pas de quelle manière est déterminée l'itinéraire qui minimise la consommation énergétique, ni de quelle manière est déterminée la vitesse utilisée pour ces méthodes. Il n'est donc pas possible de connaître la précision obtenue par les méthodes décrites dans ces demandes de brevet. D'autres méthodes d'éco-navigation sont basées sur l'algorithme de Dijkstra de plus court chemin, pour déterminer l'itinéraire qui minimise la dépense énergétique. Toutefois, cet 3057951 2 algorithme ne prend pas en compte des valeurs négatives. Par conséquent, cet algorithme peut être utilisé uniquement pour des véhicules thermiques, et ne peut pas être utilisé pour des véhicules électriques, pour lesquels une récupération d'énergie est possible (par exemple avec un freinage récupératif). Par conséquent, ces méthodes ne sont pas 5 adaptables à tout type de véhicule. De telles méthodes sont décrites notamment dans les documents suivants : Andersen O, Jens CS, Torp K, Yang B (2013), « EcoTour : Reducing the environmental footprint of vehicles using eco-routes », Proc. 2013 IEEE 14th Int. Conf. on Mobile Data Management, Milan, Italy, 3-6 June 2013, 10 Boriboonsomsin K, Barth MJ, Zhu W, Vu A (2012), « Eco-routing navigation system based on multisource historical and real-time traffic information », IEEE Trans. on Intelligent Transportation Systems, vol. 13, no. 4, p. 1694-1704, Ben Dhaou I, « Fuel estimation model for ECO-driving and ECO-routing », Proc. 2011 IEEE Intelligent Vehicles Symposium, Baden-Baden, Germany, 5-9 June 15 2011, p. 37-42, Ericsson E, Larsson H, Brundell-Freij K (2006), « Optimizing route choice for lowest fuel consumption - Potential effects of a new driver support tool », Transportation research Part C, vol. 14, p. 369-383. 20 Pour pallier ces inconvénients, la présente invention concerne un procédé de détermination d'un itinéraire minimisant la dépense énergétique d'un véhicule, le procédé est basé sur l'utilisation d'un modèle dynamique du véhicule dépendant de la vitesse et de l'accélération du véhicule, la construction d'un graphe adjoint, et un algorithme de plus court chemin adapté aux énergies négatives. L'utilisation d'un tel modèle dynamique et la 25 construction d'un graphe adjoint permettent une meilleure précision de l'énergie consommée, notamment en prenant en compte les accélérations. L'algorithme adapté aux énergies négatives rend le procédé adaptable à tout type de véhicule, y compris les véhicules électriques. 30 Le procédé selon l'invention L'invention concerne un procédé de détermination d'un itinéraire minimisant la dépense énergétique d'un véhicule circulant au sein d'un réseau routier. Pour ce procédé, on réalise les étapes suivantes : a) on identifie la position et la destination dudit véhicule ; 35 b) on construit un modèle dynamique dudit véhicule qui relie l'énergie consommée par ledit véhicule à la vitesse et à l'accélération dudit véhicule ; 3057951 3 c) on construit un graphe adjoint dudit réseau routier entre ladite position identifiée dudit véhicule et ladite destination identifiée dudit véhicule ; d) on détermine l'énergie consommée par ledit véhicule pour chaque arc dudit graphe adjoint au moyen dudit modèle dynamique du véhicule et d'une vitesse moyenne 5 dudit véhicule sur ledit arc considéré, et d'une accélération dudit véhicule pour atteindre ladite vitesse moyenne sur ledit arc considéré ; e) on détermine ledit itinéraire entre ladite position identifiée dudit véhicule et ladite destination identifiée dudit véhicule au moyen d'un algorithme de chemin le plus court qui minimise sur ledit graphe adjoint ladite énergie consommée, ledit algorithme de 10 chemin le plus court étant apte à prendre en compte, le cas échéant, une énergie consommée négative sur au moins un arc dudit graphe adjoint. Selon un mode de réalisation, on détermine ladite vitesse moyenne et ladite accélération dudit véhicule au moyen de conditions de trafic et/ou de la topologie et/ou des infrastructures dudit réseau routier. 15 Conformément à une variante, lesdites conditions de trafic sont obtenues en temps réel par communication avec des services de données en ligne. Alternativement, lesdites conditions de trafic sont stockées dans des moyens de stockage de données historiques. Selon une caractéristique, on construit ledit graphe adjoint au moyen de la topologie 20 dudit réseau routier. Conformément à une option de réalisation, on détermine ladite topologie dudit réseau routier par des moyens de géolocalisation. Conformément à un mode de réalisation, ledit modèle dynamique du véhicule dépend de paramètres intrinsèques dudit véhicule. 25 De préférence, lesdits paramètres intrinsèques dudit véhicule sont obtenus depuis une base de données, ou sont indiqués par un utilisateur. Selon un mode de réalisation, on affiche ledit itinéraire sur un dispositif autonome ou sur le tableau de bord dudit véhicule. De manière avantageuse, ledit modèle dynamique dudit véhicule dépend de la 30 demande de puissance d'au moins un système auxiliaire dudit véhicule. De préférence, ladite demande de puissance d'au moins un système auxiliaire est fonction de la température extérieure. Selon une mise en oeuvre, ledit algorithme de chemin le plus court est un algorithme de Bellman-Ford. 35 Conformément à une variante de réalisation, on construit ledit graphe adjoint en mettant en oeuvre les étapes suivantes : 3057951 4 i) on construit un graphe direct (GD) dudit réseau routier (RR) avec des noeuds (N) et des arcs (A), lesdits noeuds (N) dudit graphe direct (GD) correspondant aux intersections dudit réseau routier, et lesdits arcs (A) dudit graphe direct correspondant aux routes reliant lesdites intersections ; et 5 ii) on construit ledit graphe adjoint (GA) dudit réseau routier (RR) avec des noeuds (N) et des arcs (A), lesdits noeuds (N) dudit graphe adjoint (GA) correspondant aux arcs (A) dudit graphe direct (GD) et lesdits arcs (A) dudit graphe adjoint (GA) correspondant à l'adjacence desdits arcs (A) dudit graphe direct (GD). 10 En outre, l'invention concerne un produit programme d'ordinateur téléchargeable depuis un réseau de communication et/ou enregistré sur un support lisible par ordinateur et/ou exécutable par un processeur ou un serveur, comprenant des instructions de code de programme pour la mise en oeuvre du procédé selon l'une des caractéristiques précédentes, lorsque ledit programme est exécuté sur un ordinateur ou sur un téléphone portable. 15 Présentation succincte des figures D'autres caractéristiques et avantages du procédé selon l'invention, apparaîtront à la lecture de la description ci-après d'exemples non limitatifs de réalisations, en se référant aux figures annexées et décrites ci-après. 20 La figure 1 illustre les étapes du procédé selon un mode de réalisation de l'invention. La figure 2 illustre les étapes du procédé selon un deuxième mode de réalisation de l'invention. La figure 3 illustre la construction d'un graphe adjoint selon un mode de réalisation de l'invention. 25 La figure 4 illustre la vitesse moyenne et les vitesses mesurées sur un premier parcours. La figure 5 illustre le cumul d'énergie consommée mesurée, le cumul d'énergie consommée déterminée par un modèle selon l'art antérieur, et le cumul d'énergie consommée déterminée par un modèle dynamique selon l'invention, pour l'exemple de la 30 figure 4. La figure 6 illustre la vitesse moyenne et les vitesses mesurées pour un deuxième parcours. La figure 7 illustre le cumul d'énergie consommée mesurée, le cumul d'énergie consommée déterminée par un modèle selon l'art antérieur, et le cumul d'énergie 35 consommée déterminée par un modèle dynamique selon l'invention, pour l'exemple de la figure 6. 3057951 5 Description détaillée de l'invention La présente invention concerne un procédé d'éco-navigation, c'est-à-dire un procédé de détermination d'un itinéraire minimisant la dépense énergétique d'un véhicule circulant au 5 sein d'un réseau routier. On appelle itinéraire, le chemin que devrait parcourir un véhicule pour aller d'un point de départ (la position actuelle du véhicule) à un point d'arrivée (la destination du véhicule). Le procédé selon l'invention est adapté à tout type de véhicule : véhicules thermiques, véhicules hybrides, véhicules électriques. 10 Notations Dans la suite de la description, on utilise les notations suivantes : v Vitesse du véhicule [m/s] x Position du véhicule [m] 15 m Masse du véhicule [kg] w Régime du moteur du véhicule [tr/s] Fw Effort de traction du véhicule à la roue [N] Fareo Effort aérodynamique sur le véhicule [N] Ffriction Effort de frottement subis par le véhicule [N] 20 F - slope Effort normal subi par le véhicule (gravité) [N] Fres Résultante des pertes aérodynamique et de roulement [N] a Angle d'inclinaison de la route [rad] Pa Densité de l'air [kg/m3] Af Surface frontale du véhicule [m2] 25 cd Coefficient de résistance aérodynamique H cr Coefficient de résistance au roulement H g Accélération gravitationnelle [m2/s] ao, a1 et a2 Paramètres du véhicule [-] r Rayon de la roue [m] 30 Pt Rapport de la transmission du véhicule [-] ilt Rendement de la transmission du véhicule [-] Tm Couple moteur [Nm] Tm,max Couple moteur maximal [Nm] Tm,min Couple moteur minimal [Nm] 35 Pm Puissance disponible sur l'arbre moteur [W] 3057951 6 Pb Puissance demandée à la batterie [W] 11b Rendement agrégé de la chaîne de traction électrique [-] Paux Puissance des auxiliaires du véhicule [W] Tarim Température ambiante [K] 5 i Segment de route i [-] i-1 Segment de route, précédent le segment de route i [-] f Vitesse moyenne du trafic [m/s] K Fonction Ei Energie consommée sur le segment i [Wh] 10 E b Energie consommée à la batterie [Wh] Pi Puissance du véhicule sur le segment i à la vitesse moyenne [W] Pi Puissance du véhicule sur le segment i à vitesse variable [W] Ti Temps de parcours sur le segment i [s] /i Longueur du segment i [m] 15 Ejump,i Energie consommée associée à la variation de vitesse pour le segment i[Wh] tjump,i Temps pour réaliser la variation de la vitesse pour le segment i [s] Wi; Poids de l'arc du graphe adjoint [Wh] Pour ces notations, la dérivée par rapport au temps est notée cl ou par un point au- 20 dessus de la variable considérée. Le procédé selon l'invention comporte les étapes suivantes : 1) identification de la position et de la destination du véhicule 2) construction d'un modèle dynamique du véhicule 25 3) construction d'un graphe adjoint 4) détermination de l'énergie consommée sur le graphe adjoint 5) détermination de l'itinéraire. Les étapes de construction du modèle dynamique du véhicule et de construction du graphe adjoint peuvent être réalisées dans cet ordre, simultanément ou dans l'ordre inverse. 30 La figure 1 illustre, schématiquement et de manière non limitative, les étapes du procédé selon un mode de réalisation de l'invention. 1) identification de la position et de la destination du véhicule (D/A) 2) construction du modèle dynamique du véhicule (MOD) 35 3) construction du graphe adjoint (GA) 3057951 7 4) détermination de l'énergie consommée sur le graphe adjoint, au moyen du modèle dynamique (MOD) et du graphe adjoint (GA) 5) détermination de l'itinéraire (ITI) d'éco-navigation au moyen d'un algorithme de plus court chemin (ALG) appliqué au graphe adjoint (GA) pondéré par l'énergie consommée. 5 La figure 2 illustre, schématiquement et de manière non limitative, les étapes du procédé selon un deuxième mode de réalisation de l'invention. En plus des étapes décrites en relation avec la figure 1, le procédé comporte les étapes facultatives suivantes : détermination de la topologie du réseau routier (TOP), la topologie du réseau 10 routier peut servir à la construction du modèle dynamique (MOD) et à la construction du graphe adjoint (GA), détermination du trafic routier (TRA), la détermination du trafic peut servir à la construction du modèle dynamique (MOD) et à la construction du graphe adjoint (GA), 15 détermination des paramètres intrinsèques du véhicule (PAR), ces paramètres peuvent servir à la construction du modèle dynamique (MOD), construction d'un graphe direct (GD) du réseau routier, le graphe direct peut être obtenu au moyen de la topologie (TOP) du réseau routier, et peut servir à la construction du graphe adjoint (GA). 20 Les étapes de détermination de la topologie du réseau routier (TOP), du trafic routier (TRA) et des paramètres intrinsèques du véhicule (PAR) sont indépendantes. Il est donc possible de réaliser seulement une partie de ces étapes. Toutes les étapes du procédé, y compris leurs variantes proposées sur la figure 2 sont 25 décrites ci-dessous. 1) Identification de la position et de la destination du véhicule Lors de cette étape, on identifie la position actuelle et la destination du véhicule. En d'autres termes, on identifie le départ et l'arrivée de l'itinéraire à parcourir. 30 La position actuelle du véhicule peut être identifiée au moyen d'un système de géolocalisation (par exemple de type GPS ou Galiléo). Alternativement, la position actuelle peut être indiquée par un utilisateur au moyen d'une interface avec celui-ci (par exemple un téléphone intelligent, le tableau de bord, ou un système de géolocalisation). La destination du véhicule peut être indiquée par un utilisateur au moyen d'une 35 interface avec celui-ci. Alternativement, la destination peut être stockée dans une base de données, par exemple s'il s'agit d'une destination préalablement connue (par exemple un téléphone intelligent, le tableau de bord, ou un système de géolocalisation). 3057951 8 2) Construction du modèle dynamique du véhicule Lors de cette étape, on construit un modèle dynamique du véhicule. On appelle modèle dynamique du véhicule, un modèle qui relie l'énergie consommée par le véhicule à la vitesse 5 et à l'accélération du véhicule. Le modèle dynamique du véhicule peut être construit au moyen du principe fondamental de la dynamique, associé à un modèle énergétique de la motorisation. Selon une mise en oeuvre de l'invention (cf. étape de détermination des paramètres 10 intrinsèques du véhicule de la figure 2), le modèle peut être construit à partir de paramètres macroscopiques du véhicule, par exemple : motorisation du véhicule, masse du véhicule, puissance maximale, vitesse maximale, type de transmission, paramètres aérodynamiques, etc.. Ainsi, le modèle dynamique est représentatif du véhicule, et prend en compte ses caractéristiques spécifiques. 15 Selon une variante de réalisation, les paramètres macroscopiques peuvent être obtenus depuis une base de données, qui répertorie les différents véhicules en circulation. Par exemple, les paramètres macroscopiques peuvent être obtenus en indiquant le numéro d'immatriculation du véhicule, la base de données associant le numéro de plaque à sa conception (marque, modèle, motorisation...), et comprenant les paramètres 20 macroscopiques du véhicule. Alternativement, les paramètres macroscopiques peuvent être des données constructeurs renseignées par l'utilisateur, en particulier au moyen d'une interface (par exemple un téléphone intelligent, le tableau de bord, ou un système de géolocalisation). 25 Le modèle dynamique du véhicule peut également dépendre de paramètres de la route, tels que la pente de la route. De telles données peuvent être obtenues à partir d'une topologie (cf. étape de détermination de la topologie de la figure 2) ou d'une cartographie du réseau routier. 30 Le modèle dynamique du véhicule prend en compte la dynamique du véhicule. Il peut être construit à partir de l'application du principe fondamental de la dynamique du véhicule appliqué sur son axe longitudinal, et peut s'écrire sous la forme suivante : dv(t) m - dt - Fw - Faero - Ffriction - Fslope Où m est la masse du véhicule, v(t) sa vitesse, Fw la force à la roue, Faero la force aérodynamique, friction la force de résistance au roulement, Fs1ope la force gravitationnelle. 35 Donc, le modèle peut être récrit : 3057951 9 1 ml(t) = Fw - -2 paAfcci19(t)2 - mgcr - mg sin(a(x)) Où pa est la densité de l'air, Af la surface frontale du véhicule, cd le coefficient de résistance aérodynamique, cr le coefficient de résistance au roulement, a(x) la pente de la route en fonction de la position, et g l'accélération gravitationnelle. La somme des pertes aérodynamiques et de roulement sont généralement approximées avec un polynôme de 5 second ordre en fonction de la vitesse U : Fres = Faero Ffriction = a2v(t)2 + aiv(t) + ao Où les paramètres c/o, a1 et a2 peuvent être identifiés pour le véhicule considéré à partir d'un essai standard appelé « coast down », signifiant pente descendante. Donc, la force à la roue peut être exprimée comme : Fw = miy(t) + a2v(t)2 + aiv(t) + ao + mg sin(a(x)) Dans la suite, le modèle dynamique du véhicule est décrit pour un mode de réalisation 10 non limitatif d'un véhicule électrique. Le véhicule électrique comprend au moins une machine électrique, au moins un moyen de stockage de l'énergie électrique (telle qu'une batterie) pour alimenter le moteur électrique ou pour être alimentée par la machine électrique (dans le cas de freinage récupératif) et des moyens de récupération de l'énergie, notamment des moyens de freinage récupératif. Toutefois, le modèle est adaptable à tout type de 15 motorisation (thermique, hybride, électrique). Le couple demandé à la machine électrique pour réaliser la force requise à la roue est défini comme (dans les équations « if » est la traduction anglaise de « si ») : Tm = {Fwr Prilt Fwriit Pt if Fw > 0 if Fw Tm,max Tmco(t), if Tm,min G Tm 0 if Pm 0 Pt f Fw ,i G 0 Le régime moteur est aussi constant dans le temps puisque on assume une vitesse constante fi : _ iPt w = r La puissance mécanique disponible à la machine électrique est récrite comme suit : 20 1Tm,max ' ( 7 h, Pm,i = Tm,i ' moi, if Tm,i Tm,max h, fTm,min 0 if Pm,i REVENDICATIONS1) Procédé de détermination d'un itinéraire minimisant la dépense énergétique d'un véhicule circulant au sein d'un réseau routier (RR), caractérisé en ce qu'on réalise les étapes suivantes : a) on identifie la position et la destination dudit véhicule ; b) on construit un modèle dynamique (MOD) dudit véhicule qui relie l'énergie consommée par ledit véhicule à la vitesse et à l'accélération dudit véhicule ; c) on construit un graphe adjoint (GA) dudit réseau routier entre ladite position identifiée dudit véhicule et ladite destination identifiée dudit véhicule ; d) on détermine l'énergie consommée par ledit véhicule pour chaque arc dudit graphe adjoint (GA) au moyen dudit modèle dynamique (MOD) du véhicule et d'une vitesse moyenne dudit véhicule sur ledit arc considéré, et d'une accélération dudit véhicule pour atteindre ladite vitesse moyenne sur ledit arc considéré ; e) on détermine ledit itinéraire (ITI) entre ladite position identifiée dudit véhicule et ladite destination identifiée dudit véhicule au moyen d'un algorithme de chemin le plus court (ALG) qui minimise sur ledit graphe adjoint (GA) ladite énergie consommée, ledit algorithme de chemin le plus court étant apte à prendre en compte, le cas échéant, une énergie consommée négative sur au moins un arc dudit graphe adjoint. 2) Procédé selon la revendication 1, dans lequel on détermine ladite vitesse moyenne et ladite accélération dudit véhicule au moyen de conditions de trafic (TRA) et/ou de la topologie (TOP) et/ou des infrastructures dudit réseau routier. 3) Procédé selon la revendication 2, dans lequel lesdites conditions de trafic (TRA) sont obtenues en temps réel par communication avec des services de données en ligne. 4) Procédé selon la revendication 2, dans lequel lesdites conditions de trafic (TRA) sont stockées dans des moyens de stockage de données historiques. 5) Procédé selon l'une des revendications précédentes, dans lequel on construit ledit graphe adjoint (GA) au moyen de la topologie (TOP) dudit réseau routier. 6) Procédé selon l'une des revendications 2 à 5, dans lequel on détermine ladite topologie (TOP) dudit réseau routier (RR) par des moyens de géolocalisation. 7) Procédé selon l'une des revendications précédentes, dans lequel ledit modèle dynamique (MOD) du véhicule dépend de paramètres intrinsèques (PAR) dudit véhicule. 3057951 24 8) Procédé selon la revendication 7, dans lequel lesdits paramètres intrinsèques (PAR) dudit véhicule sont obtenus depuis une base de données, ou sont indiqués par un utilisateur. 5 9) Procédé selon l'une des revendications précédentes, dans lequel on affiche ledit itinéraire (ITI) sur un dispositif autonome ou sur le tableau de bord dudit véhicule. 10) Procédé selon l'une des revendications précédentes, dans lequel ledit modèle 10 dynamique (MOD) dudit véhicule dépend de la demande de puissance d'au moins un système auxiliaire dudit véhicule. 11) Procédé selon la revendication 10, dans lequel ladite demande de puissance d'au moins un système auxiliaire est fonction de la température extérieure. 15 12) Procédé selon l'une des revendications précédentes, dans lequel ledit algorithme de chemin le plus court (ALG) est un algorithme de Bellman-Ford. 13) Procédé selon l'une des revendications précédentes, dans lequel on construit ledit 20 graphe adjoint (GA) en mettant en oeuvre les étapes suivantes : i) on construit un graphe direct (GD) dudit réseau routier (RR) avec des noeuds (N) et des arcs (A), lesdits noeuds (N) dudit graphe direct (GD) correspondant aux intersections dudit réseau routier, et lesdits arcs (A) dudit graphe direct correspondant aux routes reliant lesdites intersections ; et 25 ii) on construit ledit graphe adjoint (GA) dudit réseau routier (RR) avec des noeuds (N) et des arcs (A), lesdits noeuds (N) dudit graphe adjoint (GA) correspondant aux arcs (A) dudit graphe direct (GD) et lesdits arcs (A) dudit graphe adjoint (GA) correspondant à l'adjacence desdits arcs (A) dudit graphe direct (GD). 30 14) Produit programme d'ordinateur téléchargeable depuis un réseau de communication et/ou enregistré sur un support lisible par ordinateur et/ou exécutable par un processeur ou un serveur, comprenant des instructions de code de programme pour la mise en oeuvre du procédé selon l'une des revendications précédentes, lorsque ledit programme est exécuté sur un ordinateur ou sur un téléphone portable. 35