GPS, Waze : comment fonctionnent leurs algorithmes ?

Le fait de travailler dans le développement informatique fait souvent s’intéresser au fonctionnement des outils que nous pouvons utiliser au quotidien. C’était le cas sur la route il y a peu, avec Waze lancé, en me demandant comment pouvaient fonctionner les algorithmes de guidage par GPS. Car quand on y réfléchit, aller d’un point A à un point B, avec les multitudes de routes possibles, cela peut donner un peu le vertige de savoir laquelle choisir. Surtout quand on y ajoute les contraintes liées aux conditions de circulation qui peuvent évoluer rapidement.

L’idée dans cet article n’est pas de vous dire précisément comment fonctionnent les algorithmes des GPS ou de Waze, car ils sont propriétaires. Néanmoins, il existe depuis longtemps un certain nombre d’algorithmes qui doivent prendre leur part dans la « recette » permettant d’aboutir au meilleur itinéraire.

Quand on y réfléchit de façon simple, pour arriver à trouver un itinéraire, il faut :

une cartographie à jour, pour tenir compte des derniers changements (nouvelles routes, changement de sens de circulation…)
calculer le meilleur itinéraire entre deux points. Dans des conditions standards, et tenir compte également des évènements de circulation (bouchons, accidentes, fermetures exceptionnelles…)

GPS, Waze : avoir une cartographie à jour

Il existe plusieurs possibilités pour avoir une cartographie à jour. Cela peut passer par des services cartographiques, ou par des communautés qui maintiennent une carte à jour. Par exemple, sur Waze vous pouvez soumettre des changements de carte.

On ne peut pas savoir comment fonctionne dans le détail les algorithmes de Waze ou d’autres GPS. Mais on peut imaginer aussi que l’algorithme permette de déduire des informations cartographiques. Par exemple, si une voiture passe à un endroit où aucune route n’est connue, on peut se poser une question. Si beaucoup de voitures passent par là, on peut sans doute en déduire à un moment donné la présence d’une route. Cela peut être vrai également pour les sens de circulation. Une voie en sens interdit mais qui est emprunté par beaucoup de véhicules sur plusieurs jours peut permettre d’en déduire un changement (même provisoire pour des travaux par exemple).

Cela peut d’ailleurs poser quelques soucis dans certains cas. Je me rappelle une fois rouler sur l’île de Ré, et Waze m’a envoyé sur une petite route car la route principale bouchonnait. Hors, celle-ci était interdite sauf aux véhicules agricoles. On peut s’imaginer qu’il l’a proposé car un certain nombre de voitures l’a emprunté.

GPS, Waze : trouver le meilleur itinéraire

Maintenant que nous avons une cartographie à jour, il faut déterminer le meilleur itinéraire. Et c’est là où les choses se corsent. Car imaginez d’un point A à un point B les possibilités d’itinéraires, avec le nombre d’options qui s’agrandit de manière exponentielle avec la distance.

La théorie des graphes

La première clé est de considérer une carte comme un graphe, avec des sommets et des arêtes. Les sommets sont des intersections, et les arêtes les routes reliant ces intersections.

Une fois le graphe représenté, il y a deux possibilités pour le parcourir :

Pour le calcul d’itinéraire, ce sera le parcours en largeur qui sera privilégié.

Côté application de ces algorithmes au développement, je vous recommande de regarder cet article sur le blog « je suis un dev ».

L’algorithme de Dijkstra

On sait comment parcourir un graphe, maintenant l’idée est de le faire de la façon la plus optimum possible. Pour répondre rapidement et éviter d’utiliser trop de ressources de calculs de façon inutile. C’est ce que propose de faire l’algorithme de Dijkstra permettant de calculer le plus court chemin qui a été publié en 1959.

Je vous propose deux vidéos explicatives sur le sujet, qui vaudront mieux qu’un long discours pour comprendre le principe :

L’algorithme A*

Toujours dans l’idée d’optimiser au maximum les calculs, d’autres algorithmes existent. C’est le cas de l’algorithme A*. L’idée est de rajouter à la recherche des critères heuristiques, c’est à dire des critères permettant de résoudre rapidement un problème, peut-être pas forcément de la façon la plus optimum. Cela veut dire que dans un grand nombre de cas, il sera plus optimum que Dijkstra. Mais dans certains cas plus particuliers non. Un critère heuristique possible dans le cadre de la recherche d’itinéraire, c’est la distance à vol d’oiseau.

Dans le cadre de A*, l’option est de prendre en compte le coût précédent, le coût à venir et la distance à vol d’oiseau pour orienter les choix. L’idée étant de se dire que plus on se rapproche de l’objectif, meilleure est la décision.

Je vous conseille cette vidéo (en anglais mais facile à comprendre) pour clarifier tout cela

GPS, Waze : Calculer le temps de trajet

On a vu dans le paragraphe précédent que pour trouver le meilleur itinéraire, plusieurs algorithmes étaient possibles. Mais tous suivent la théorie des graphes. A savoir partir d’un point A, passer par des arêtes pour atteindre d’autres sommets et au final le point B.

On comprend alors que le temps de trajet peut être associé à une arête. Via un attribut indiquant le temps qu’il faut pour parcourir cette dernière. En effet, on imagine aisément que les arêtes peuvent porter un certain nombre d’informations utiles :

distance
temps pour la parcourir
éventuellement tarif de péage
…

La question qui vient ensuite c’est comment déterminer ce temps ?

Là encore, plusieurs options sont possibles. Cela peut être un temps théorique si l’on n’a pas plus d’informations. Si en revanche, on dispose de données liées à l’utilisation du logiciel, on peut être plus précis. C’est ce que fait Waze, quand on utilise le logiciel il en profite pour récupérer des données. Notamment savoir quelle est la vitesse sur une arête, combien de temps il faut pour la traverser. Les valeurs aberrantes (conducteur beaucoup plus rapide ou beaucoup plus lent que les autres) sont mises de côté, comme souvent dans les études statistiques.

Cette information sert ensuite à deux choses :

une utilisation à court terme pour pouvoir donner aux automobilistes derrière des informations actualisées sur les temps de trajet. A noter aussi la possibilité via l’application de signaler des évènements (accidents, ralentissements, véhicule arrêté…).
une utilisation à plus long terme pour avoir des données statistiques sur l’arête en question. Cela permettra par exemple de faire des moyennes en fonction des jours et des heures. Et de déterminer ainsi même à l’avance un temps approximatif en roulant tel jour à telle heure.

J’ai d’ailleurs vu sur un trajet récent l’utilisation de ces temps statistiques sur les temps de trajet. Je suis arrivé un mardi en fin d’après midi sur la région parisienne en pleines vacances de Noël. Aucun bouchon n’était annoncé, mais il a tenu compte je pense des conditions de circulation un mardi en fin d’après midi habituel (hors vacances). Car il a surestimé l’ETA (estimation de l’heure d’arrivée) en anticipant des bouchons.

Vous pouvez d’ailleurs voir le trafic en temps réel, et également calculer un temps de trajet estimé par heure sur https://www.waze.com/livemap