Logiciels

Comment Waze trouve-t-il le chemin le plus court ou le plus rapide ?

Le Waze trouve le chemin le plus court ou le plus rapide entre deux points en utilisant diverses caractéristiques. Il combine les données des utilisateurs et les informations sur le trafic en temps réel avec des algorithmes et des principes mathématiques, sans lesquels il ne fonctionnerait pas.

Comment Waze trouve-t-il le chemin le plus court ?

Waze utilise les données envoyées en temps réel par les téléphones portables des utilisateurs pour trouver le chemin le plus court entre deux points en suggérant un itinéraire. Il applique ces informations en utilisant deux éléments principaux : la théorie des graphes et l’algorithme A*.

Qu’est-ce que la théorie des graphiques ?

La théorie graphique est une branche des mathématiques qui étudie les relations entre les éléments d’un ensemble. Elle a été créée par le mathématicien Leonhard Euler en 1736, lorsqu’il a présenté une solution au problème des 7 ponts de Königsberg : à cette époque, la ville (aujourd’hui Kaliningrad, Russie) était coupée par la Pergola, divisant la région en deux zones continentales et deux îles au milieu du fleuve, toutes reliées par des ponts.

  La nouvelle version de Dropbox pour Windows et OS X envoie automatiquement vos captures d'écran dans le Cloud

La proposition du problème était de trouver un moyen de traverser les sept ponts, en ne passant qu’une fois chacun d’entre eux. Euler a montré qu’il n’y avait pas de solution possible en créant un schéma, en transformant les ponts en lignes et les portions de la ville en points. Ce graphique est considéré comme le premier de l’histoire.

Le graphe d’Euler a ouvert une branche qui permet d’étudier les liens entre les éléments de différentes manières ; en Topologie, il permet d’étudier les itinéraires possibles (les arêtes) entre les points d’origine/destination (les sommets, ou nœuds). Un graphique peut attribuer des poids (valeurs) aux arêtes et aux nœuds, tandis que les premiers peuvent également avoir une direction. Dans ce cas, le graphique est appelé chiffre, graphique dirigé ou également carquois.

Qu’est-ce que l’algorithme A* ?

Sur une carte, les nœuds sont les points d’origine et de destination d’un itinéraire, tandis que les bords sont les itinéraires possibles. Pour que Waze puisse déterminer le meilleur itinéraire, il attribue des poids à chacun des itinéraires, en fonction des informations reçues en temps réel des utilisateurs, des agences de trafic et d’autres sources.

  Fitbit et Stanford s'unissent pour détecter les maladies portables

Le poids détermine le temps nécessaire pour effectuer le trajet, s’il est plus ou moins long, et c’est là qu’intervient l’algorithme A* (lire “L’étoile”), une extension de l’algorithme Djikstra pour le problème du plus court chemin. Il s’agit d’un algorithme de recherche basé sur des graphes avec des poids, destiné à trouver le chemin le plus court possible entre deux points au moindre coût, qui conserve tous les itinéraires mémorisés. C’est pourquoi il est le plus utilisé dans les solutions de calcul pour les itinéraires.

Le principe est le suivant : plus le poids d’un bord (route) est important, plus il faut de temps pour le parcourir. Le A* analyse les trajets possibles, fait la somme des poids des itinéraires et renvoie le meilleur itinéraire, en tenant compte de la distance et du temps. Le nœud suivant (le point d’extrémité d’un bord, ou d’une route ; dans le cas d’une rue, d’une avenue, etc.) est choisi en fonction de sa proximité avec le nœud de destination et de son poids.

  Quelle est la différence entre le taux FPS et la fréquence Hertz ?

Dans l’exemple ci-dessous, l’algorithme A* analyse les itinéraires possibles vers le point de destination, en tenant compte de l’obstacle rencontré. Plus c’est vert, plus on s’éloigne de l’origine.

N’oubliez pas que le chemin que Waze emprunte n’est pas nécessairement le plus court, car il donne la priorité à ce qui sera parcouru dans les plus brefs délais. L’application tient compte de variables telles que la vitesse moyenne des routes, l’heure de la journée (qui influence le nombre de véhicules), la rotation en vigueur ou non, les accidents, la réduction de la vitesse dans les virages, etc.

Plus important encore, les informations sur les itinéraires et le poids qui leur est attribué peuvent varier au cours de la journée, ce qui permet à Waze de recommander différents itinéraires à deux ou plusieurs personnes à partir du même point vers une destination commune, mais à des heures différentes.

A propos de l'auteur

Zineb

Enseignante en lycée, je m'intéresse à tout ce qui touche aux nouvelles technologies. #teamMac sur PerlmOl (je ne me sépare d'ailleurs jamais non plus de mon Iphone).

Laisser un commentaire