Maniere dont Waze calcule les intinéraires

From waze
Jump to: navigation, search

Ceci est ma première traduction, à relire et à corriger. 70% de la traduction terminée.

Itinéraire basé sur le client

Calculer un itinéraire optimal est une tâche difficile. Alors que l'application pour l'appareil client a un algorithme d'itinéraire inclus, cela n'est pas utilisé à moins qu'il n'y ait aucune connection au serveur waze.

Suppositions

L'algorithme de routage utilisé par le serveur waze n'est pas divulgué au public, et ce qui suit est basé sur des observations, des suppositions, et sur quelques informations dévoilées par l'équipe de Waze. Nous pouvons supposer que la gestion du serveur d'itinéraire est considérée comme propriétaire et comme un avantage concurrentiel pour Waze. Nous pouvons aussi supposer qu'il est sujet à changement, et que toute information qui a été dévoilée à son sujet pourrais être incomplète ou périmée.

Demande d'itinéraire

Quand vous demandez un calcul d'itinéraire, la requête est envoyée au serveur Waze. Cet itinéraire est alors renvoyé à votre appareil client et affiché.

La requête de demande d'itinéraire varie en fonction des paramètres que vous avez choisis sur votre appareil client. Dans itinéraire, vous pouvez choisir:

  • Plus rapide, ou bien Plus court.
  • Soit autoriser les routes non-goudronnées, soit ne jamais autoriser les routes non-goudronnées, soit encore éviter les longues routes non-goudronnées
  • De minimiser ou non le nombre de fois ou il faudra tourner
  • D'éviter ou non les autoroutes
  • D'essayer ou non d'utiliser le plus possible la fonctionnalité cookie munching (grignotage de cookie?)

L'itinéraire le plus court fait référence à la distance réelle parcourue. Il vaut toujours mieux choisir l'option d'Itinéraire le plus rapide. En effet, 100km d'autoroute valent mieux que 90km de chemins de campagne.

cookie munching (grignotage de cookie?) fait référence à pacman ou à des routes dont l'existence n'a pas encore été confirmée. Lorsque cette option est activée, l'itinéraire prendra un chemin moins direct pour passer par des routes dont l'existence n'a pas encore été confirmée, vous faisant ainsi gagner des points. Ceci ajoute typiquement 10 minutes à votre temps de trajet. Du coup, un trajet de 3 heures deviens un trajet de 3 heures et 10 minutes. Mais un trajet de 20 minutes deviens un trajet de 30 minutes.

Routes manquantes et connexions d'intersection incorrecte

Waze essaye de trouver l'itinéraire le plus rapide entre vous et votre destination. Evidement, il ne peut que prendre en compte les routes qu'il connait déjà, donc votre itinéraire ne sera pas optimal s'il existe un meilleur itinéraire dont les routes n'ont pas les bonnes connections dans la Live Map

Vitesse actuelle du trafic en temps-réél

(Real-time current road speeds)

Nous pouvons être certains du fait que Waze utilise des rapporteurs de l'état du trafic en temps-réél plutôt que des moyennes statistiques pré-établies de l'état moyen du trafic à une heure donnée de la journée. Nous savons que Waze utilise des rapports de congestion du trafic pour recalculer l'itinéraire de manière à contourner les ralentissements et/ou embouteillages. Les premières versions du client signalaient aussi le fait que le trafic soit fluide - ceci a été supprimé en raison d'encombrement des cartes. Mais Waze continuera encore a recevoir cette information. Nous pouvons supposer que la vitesse de tout wazer devant vous sur une potion de route sera la vitesse utilisée quand votre route sera calculée.

Au fur et à mesure que le nombre et la densité de wazers croit, ces données en temps-réél gagnent en importance. Cet effet boule de neige est en partie une conséquence du but originel de Waze consistant à optimiser les modifications. Comme Waze a grossi jusqu'à être utilisé comme un appareil de navigation par GPS plus générique, et en particulier à être utilisé sur les routes les moins empruntées, la moyenne historique de l'état du trafic devient plus utile.

En effet, puisque Waze utilise l'heure à laquelle vous prévoyez d'être sur un segment de rue pour calculer la vitesse prévue sur ce segment, il ne peut pas utiliser de données temps-réél lorsque la durée de votre trajet s'étale jusqu'à un créneau horaire suivant. Donc les trajets de plus de 30 minutes (et en moyenne de plus de 15 minutes) vont inclure des créneaux horaires dans le futur dans lesquels les données sur le trafic réellement constaté à ce moment là ne sont pas encore disponibles. Quand vous entrez dans un nouveau créneau horaire, des données sur l'état du trafic en temps-réel peuvent être disponibles, ce qui peut faire recalculer votre Heure Estimée d'Arrivée (HEA) à votre client, et qui peut lui faire changer votre itinéraire.

Itinéraire le plus rapide

Waze connait la vitesse moyenne de chaque rue confirmée entre vous et votre destination. Le serveur Waze peut calculer quelle liste de rue prendre pour minimiser le temps de trajet total.

Alors que chaque requête est traitée en temps-réel, on semble remarquer que Waze caches certaines requêtes d'itinéraire ou de points d'intérêt. Cela signifie que s'il connait déjà le meilleur itinéraire de B vers C, et que vous demandez un itinéraire de A vers C, il peut se contenter de calculer le meilleur itinéraire de A vers B, une fois qu'il a vérifié qu'il n'y avait pas de meilleur itinéraire évitant absolument B. Ceci signifie que lorsqu'il y a un Live map update certain itinéraires peuvent être moins qu'optimaux pendant au maximum une journée, lorsque les itinéraires sont mis en cache et recalculés.

Lors d'un calcul complexe, calculer l'itinéraire optimal est possible. La complexité survient avec la "vitesse moyenne" du trafic.

Changement d'itinéraire à cause d'une origin différente

(Changes in route due to different origin)

Considérons le calcul d'un itinéraire de A vers Z. L'itinéraire suggéré peut être A vers B vers C vers D vers Z. Ensuite calculez l'itinéraire de B vers Z. Vous pouvez obtenir un itinéraire suggéré de B vers C vers E vers Z. De prime abord, cela suggère que l'un des itinéraires n'est pas optimal.

Nous pouvons tenter de deviner ce qui pourrais être en train de se produire. Il peut y avoir un problème associé au cache possible des itinéraire. Ou il pourrais y avoir un effet de "fenêtre temporelle": les heures d'arrivées différentes au point C pourraient changer le meilleur itinéraire vers Z. Ou il pourrais y avoir un effet d'ajustement précis dans les itinéraires, peut être pour éviter de tourner trop de fois. Du coup, en abandonnant le segment A vers B, le segment C vers E vers Z ne dépasse plus un certain seuil.

Cet effet peut être observé en conduisant. Si vous recalculez un itinéraire vers une destination tout en conduisant suivant un itinéraire déjà calculé vers cette même direction, l'itinéraire peut changer.

Ceci sont de vieux rapports ou les wazers n'ont pas proposé un itinéraire pour contourner un trafic dense, mais reçoivent en fait un nouvel itinéraire en le demandant manuellement. Il se peut qu'il aurraient reçu cet itinéraire alternatif à ce stade de toute manière, qu'il y ait eu ou non une mauvaise circulation devant. Cela pose en fait la question de savoir quand et comment Waze considères une modification de l'itinéraire, mais tout ceci peut avoir été réglé dans la version actuelle.

Problemes avec la vitesse moyenne du trafic

(Problems with average road speeds) Si la vitesse moyenne du trafic n'est pas correcte, alors l'itinéraire ne sera pas optimal. Les sections qui suivent présentent des raisons pour lesquelles utiliser la vitesse moyenne du trafic peut être un mauvais choix.

Variations en fonction de l'heure

Considérez une route que la plupart des wazers empruntent à 17 heures, quand la vitesse est de 20 km/h. Vous choisissez votre itinéraire vers 10 heures du matin, lorsque la route est dégagée, et que la vitesse moyenne est de 90 km/h. Elle est bien la meilleure route à emprunter, mais Waze choisit un itinéraire différent car il n'a aucune information au sujet de la vitesse à 10 heures du matin, et suppose que la vitesse y est de 20 km/h toute la journée.

Vous pouvez bien sûr emprunter l'itinéraire vous-même, et Waze finira par apprendre. Nous ne savons pas combien de temps Waze utilise pour ses calculs. Cependant si Waze se débarrasse des vieilles informations temporelles, vous risquez de ne pas en accumuler de nouvelles plus vite qu'il ne s'en débarrasse.

Plus d'utilisateurs sur Waze aideraient à corriger cela.

Attente pour tourner

(note du traducteur: sur une voie, lorsqu'on veux tourner à gauche, il faut parfois attendre qu'il n'y ait plus de voiture qui arrivent en face. Parfois il faut attendre longtemps, alors que parfois, on peut tourner immédiatement).

Considérez une rue longue d'un kilomètre où vous conduisez tout droit, et traversez les intersections, le tout à 160 km/h, ce qui prendrait 22 secondes. Ou bien, à la fin de la rue, vous pouvez vous immobiliser, et attendre 5 minutes pour pouvoir tourner. Dans le premier cas, votre vitesse moyenne est de 160 km/h. Dans le deuxième cas, votre vitesse moyenne n'est même pas de 20 km/h. (note du traducteur: oui, 160 km/h c'est peut être un peu trop rapide, mais moi, je ne fais que traduire le wiki anglais ... ils sont fous ces anglophones ...)

Maintenant, si 9 wazers sur 10 passent directement sans pause, la vitesse moyenne de la rue est de 146 km/h. Waze va recommander cet itinéraire, même si cela implique de tourner, et que la route n'est pas optimale.

Au contraire, si 9 wazers sur 10 effectuent ce virage qui requiert 5 minutes, la vitesse moyenne de la route est de 30 km/h, et quand bien même votre route optimale vous y ferait passer à 160 km/h, Waze ne le suggèrera pas, car il ne voit que la vitesse moyenne de 30 km/h.

Nous pouvons supposer que Waze est au courant de ce problème. Vous pouvez choisir l'option de minimiser le nombre de tournants dans vos paramètres d'itinéraires. Ou bien vous pouvez utiliser vos propres préférences. La bonne nouvelle est qu'en collectant vos informations sur l'itinéraire, Waze collecte suffisamment d'informations pour donner des conseils d'itinéraire lors qu'il en aura la fonctionnalité. Il connait la vitesse moyenne des gens qui vont tout droit, et il connait la vitesse moyenne des gens qui effectuent le virage de 5 minutes. Et il peut appliquer la bonne vitesse moyenne lorsqu'il calcule votre meilleur itinéraire. Cela rend les calculs plus complexes, mais cela peut être fait.

Actuellement, ce n'est pas effectué.

édition de Cartouche

La vitesse moyenne du trafic sur une rue donnée peut être tragiquement altérée par l'édition dans Cartouche. Considérez une portion de rue de 50 mètres parcourue en 36 secondes. Un correcteur étend cette portion de rue aux 10 km de la rue. Cartouche enregistre maintenant cette route comme mesurant 10km de long, mais aussi comme étant parcourue en 36 secondes, pour une vitesse moyenne étant donc égale à 1000km/heures! Ceci a en particulier été un problème quand des gens ajustent les longueurs des échangeurs.

Feux de circulation et panneaux de stop

Waze n'enregistre pas l'emplacement des feux de circulation. Bien que d'autres systèmes de navigation GPS offrent des guidages du genre "tournez au prochain feu de signalisation", l'information est souvent incomplète, incorrecte ou périmée. L'opinion consensuelle est que Waze ne devrait pas enregistrer l'emplacement des feux de circulation.

En fait, Waze prend en compte les feux de circulation et les panneaux stop à travers l'effet qu'ils ont sur la vitesse du trafic. Considérons un feu rouge avec des temps d'attente longs. Le segment de rue qui mène à ce feu rouge aura une vitesse moyenne basse. Si la vitesse moyenne (basée sur le temps d'attente moyen) devient assez long, un itinéraire plus long qui évite ce feu deviendra l'itinéraire préféré. Ceci a déjà été observé en pratique et est un exemple de comportements émergents. Waze n'est pas programmé pour éviter les feux de circulation, mais il va éviter les rues "lentes", et si des feux de circulation rendent la rue lente, alors Waze va l'éviter.

(note du traducteur: en intelligence artificielle, un comportement émergent est l'apparition spontané d'une capacité dans une machine qui n'a pas été explicitement programmée pour avoir cette capacité. CF émergence sur wikipedia).

Certains conducteurs vont régulièrement prendre des itinéraires plus long pour éviter tout dos d'âne ou feu de circulation, zigzaguant à travers les ruelles secondaires. Waze avait la réputation de suggérer cela, et aussi de rebasculer sur l'attente au feu rouge quand l'information d'une meilleure vitesse moyenne était collectée depuis des ruelles secondaires.

Mais remarquez que ceci peut être moins qu'optimal en raison des temps d'attente pour tourner exposés ci-dessus.

Vitesses de rue périmées et anormales

Les conditions de circulation changent, les travaux changent d'emplacement, et la vitesse moyenne d'une rue peut changer considérablement. Un jour, vous pouvez être coincés derrière un camin, et un autre jour, vous vous trainez à 2 heures du matin car vous transportez votre poisson rouge. Ou encore votre GPS pète un câble, et prétend que vous circulez à 1000 km/h. (Or your GPS throws a glitch and has you travelling a 1000 mph.) En résumé, les vitesses moyennes peuvent changer au fil du temps, et alors les temps enregistrés sont anormaux ou simplement faux. Et ils peuvent rester faux très longtemps.

Nous pouvons supposer que Waze est au courant de cela. Il y a des preuves que les vitesses de rues anormales et les anciennes vitesses de rues sont effacées, ou au moins, pas utilisées lors du calcul de la vitesse moyenne des rues.

Vitesse moyenne de rue "réduction de fenêtre"

S'il y a assez de vitesses enregistrées sur une rue, alors Waze utilise une fenêtre rétrécissante de vitesses pour mieux estimer la vitesse moyenne au moment ou vous la parcourez. Waze utilise la vitesse de chaque segment de rue dans des intervalles pouvant se réduire à 30 minutes, pour chaque sens. Donc une rue à double sens, peut avoir jusqu'à 48 vitesses de rue moyennes. Nous pouvons supposer que lorsqu'il n'y a pas assez d'enregistrements pour un segment de temps donné, un plus grand intervalle de temps est pris, jusqu'au maximum le jour entier. Lorsque que la rue est parcourue davantage, le segment de temps rétrécirais à 30 minutes. (Note Du Traducteur: is driven more / would shrink : problème de concordance des temps déjà présent dans la version anglaise).

Nous pouvons supposer qu'il puisse y avoir d'autres informations utilisées grâce au jour de la semaine. Il y a des preuves observées qu'une rue qui est encombrée les jours de la semaine et non utilisée dans les choix d'itinéraires, sera choisie comme itinéraire optimal le weekend.

A partir d'un certain moment, Waze aurait aussi besoin de considérer les mois de l'année car les variations saisonnières peuvent affecter la vitesse des routes.

Waze utilise la vitesse moyenne du segment de rue pour le créneau horaire qui correspond à l'heure à laquelle vous êtes supposés arriver à un segment de rue. (Note Du Traducteur: confus déjà en version anglaise: Waze uses the average road segment speed for the time slot that applies at time you are expected to arrive at a road segment.)

A cause de cette "fenêtre temporelle", Waze va suggérer différents itinéraires a différents moments de la journée. Mais c'est dépendant de combien de durées sont enregistrés au sujets des rues sur l'itinéraire. Et si elles sont toutes enregistrées environ au même moment de la journée, alors la fenêtre temporelle ne va pas aider. Si 1000 durées sont enregistrées vers 5 heures de l'après midi, et que 2 durées sont enregistrées à 10 heures du matin, alors votre vitesse moyenne de 10 heures du matin sera tout de même essentiellement basée sur des durées mesurées à 5 heures de l'après midi.

Routing algorithm refinements

Routing options

Il est facile de voir comment les options d'itinéraire peuvent être implémentées. Par example, pour minimiser le nombre de tournants, nous pouvons ajouter une pénalité de temps pour l'itinéraire le plus rapide ou une pénalité de distance pour l'itinéraire plus court, lors du calcul de l'itinéraire le plus court ou le plus rapide.

Pénalités de carrefours

Actuellement, Waze appliques un temps de pénalité de 5 secondes pour chaque traversée de carrefour. Alors que ce n'est pas une approche déraisonnable pour gérer les intersections, cela a généré quelques défauts d'itinéraires, et est en train d'être revu. Un problème majeur surviens dans les longues autoroutes qui peuvent être consituées de centaines de segments connectés ensemble. Ceci peut ajouter une pénalité de 5 minutes à un trajet, bien que les intersections ne soient pas réelles.

Currently Waze applies a 5 second time penalty for passing through each junction. While not an unreasonable approach to dealing with intersections, it has generated some flawed routing and is being reviewed. One major issue arises in long highways which may be made up of hundreds of segments connected together. This may add a 5 minute penalty to a trip, even though the intersections are not real.

This supports the arguments of those who aim to have a clean edit of maps where junctions are only used when necessary. In practice we need to deal with the map as it stands. An automated tool to remove the junctions is needed as the manual work that is required is enormous.

The routing problem can be fixed in a variety of ways. One could not apply the penalty when there are no other existing roads meeting. Not apply the penalty when you are travelling on to a road with the same name. Not apply the penalty when the road you are travelling on is a higher class (eg highway versus street, primary street versus street) where we can assume the higher class road has the right of way. Or just not apply the penalty when travelling on freeways, motorways and highways.

Even if a road is correctly connected with no unnecessary segments, the junction penalty can still give incorrect results. For example a busy highway may be correctly connected to the ramps along its length. A quiet country road running in parallel may not have all the minor connecting roads recorded - it looks like a straight section of road with no junctions. Waze may choose it as the preferred route because of the lack of junctions.

What to do if you think the generated route is wrong

Firstly, use the option to generate alternative routes. This may give you some clues as to why Waze is offering that route.

Secondly, if you think there is a better route, check in Cartouche that the roads are all connected along the route.

Thirdly, post a message detailing the problem route - origin, destination and a Cartouche permalink to the Navigation forum. Other eyes will check it, and you may indeed find a flaw in the Waze routing algorithm. Fixing it may make it better for everyone.

Change of Routing

When Waze receives notification of traffic conditions it uses the actual speed of roads on your route, rather than the average speed. This is based only on the automatic traffic condition reports - light, moderate, heavy traffic or complete standstill. Manual reports of traffic jams and accidents are for your information only and do not change routing.

It may be that even with the traffic reports, there is no better route and Waze will not offer you one.

You are the driver

Waze can never see that the traffic light is green going straight, or know that today is a public holiday. It can offer you guidance as to what is the best route under average conditions. But you are the driver and you are in the best position to make the decision for today under today's conditions.

If everyone followed Waze directions and never drove on a new route, Waze may never learn that route is better. When Waze is recording your travels, every trip helps make Waze better for everyone. That includes when you think you know better. Sometimes you will be right. And sometimes you will be wrong. But it is better to find out you are wrong so you can choose the better route. And when you are right, all Waze users benefits by sharing in your knowledge.