Retour dans le monde opaque de la recherche privée. Après mon "échec" pour percer les secrets des accéléromètres , j'ai eu plus de succès avec les GPS...

Une actualité mathématique récente ( m'a fait me poser la question toute simple suivante : comment les sites web et les navigateurs GPS de voitures trouvent le chemin le plus court entre deux points ? Franchement, je l'ignorais. J'ai donc appelé, en plus des chercheurs de l'article et de groupes concurrents, Viamichelin, mappy et TomTom et...obtenu des réponses !

Première surprise, dans ce produit très à la mode, il y a une idée mathématique datant de 1959... Une carte routière se représente en fait comme un maillage dans lequel les noeuds sont les villes et villages et les liens entre eux, des routes. L'algorithme de Dijkstra, du nom de son inventeur, consiste à explorer complètement cette structure pour trouver le chemin le plus court. C'est assez rustique, même si des améliorations ont été inventées depuis (n'explorer la carte que dans la direction générale de la cible ; partir en même temps de la cible et du point de départ ; utiliser des "raccourcis"...).

Deuxième surprise, alors que les villes et villages n'ont pas bougé depuis belle lurette, la complexité des calculs augmente... Depuis les années 2000, l'activité de recherche a même repris de plus belle. L'explosion du réseau internet ou des réseaux de communication y est pour beaucoup, mais le problème du calcul des chemins routiers y contribue aussi. En fait, les cartes "grossissent" car elles s'enrichissent d'attributs de plus en plus précis comme la vitesse autorisée, les itinéraires "conseillés", "touristiques", les radars (sans compter les informations sur le trafic ou les travaux...). Et puis, la puissance informatique doit maintenant être embarquée sur de petites machines, voire sur des téléphones portables, donc il faut être le moins gourmand possible en calcul. Alors si tout le monde utilise les mêmes algorithmes, la différence se fait sur la qualité des "cartes". Chaque fabricant pondère à sa façon les différents noeuds. Il construit aussi sa propre hiérarchie (en gros autoroute, nationale, départementale...). Là les méthodes sont plus heuristiques, donc moins exactes. A la différence de l'algorithme des allemands de l'université de Karlsruhe, à l'origine de mon questionnement.

Troisième (petite) surprise, ce n'est pas parce que la méthode théorique promet d'aller dix ou cent fois plus vite qu'elle va être adoptée rapidement... L'implémentaiton de la technique peut s'avérer coûteuse en temps de développement et en temps de calcul ensuite. C'est ce que mes interlocuteurs, qui n'avaient pas (encore) eu vent de cet article révolutionnaire, m'ont laissé entendre, tout en promettant de faire suivre à leurs équipes (vais-je indirectement contribuer à une révolution technologique ?). De leur côté, les chercheurs m'ont indiqué être en contact avec des industriels. A suivre...