Salut tout le monde,
Le débat sur la classification des routes m’a amené à rafraîchir et actualiser mes connaissances en la matière, ayant fait des études d’informatique il y a longtemps. Voilà ce que j’ai retrouvé, peut-être que ça peut aider à comprendre des choses :
Le problème de trouver un trajet dans un réseau routier n’est qu’une instance d’un problème classique de l’informatique théorique : la recherche du chemin le moins coûteux dans un graphe.
Pour faire simple, dans notre cas, un graphe est un ensemble de sommets (jonctions) reliés par des arêtes (segments). On peut aller d’un sommet à un autre s’il y a une arête entre ces sommets, et cette transition a un coût. On définit le coût comme on veut.
Ce problème est étudié depuis longtemps, et en 1959, le chercheur néerlandais E. Dijkstra propose l’algorithme qui porte son nom depuis. Cet algorithme trouve à tous les coups la solution, si elle existe. Le souci c’est seulement que l’algorithme doit examiner une grande quantité de sommets et d’arêtes, et que son temps d’exécution est proportionnel au carré de la taille du graphe. Dans les années 1980, d’autres chercheurs améliorent cet algorithme et proposent une implémentation dont le temps d’exécution est proportionnel à n log(n), n étant la taille du graphe. C’est beaucoup mieux, mais pour des réseaux routiers de la taille d’un continent, c’est encore insuffisant.
Depuis l’arrivée des GPS sur la marché, ce problème a été très étudié par les chercheurs en informatique, et il y a maintenant un grand nombre d’algorithmes qui sont plus ou moins des descendants de celui de Dijkstra. Ils trouvent tous la solution aussi, mais beaucoup plus rapidement. La plupart d’entre eux fonctionne en deux temps. Dans un premier temps, ils construisent des données auxiliaires permettant d’accélérer les requêtes. (Je pense que c’est ce qui se passe quand Waze construit ses ‘tiles’.) Dans un second temps, l’itinéraire est calculé.
Pour construire ces données auxiliaires, pas mal d’algorithmes récents exploitent le fait que certaines arêtes, ou certains sommets sont plus importants que d’autres. Et c’est là que la classification des routes intervient : une route importante aura plus de données auxiliaires associées qu’une autre, et l’algo va passer plus de temps à les examiner pendant la première phase.
Tous les algorithmes récents garantissent de trouver LE chemin le moins coûteux, et pas une approximation. Quand Waze ne trouvait pas d’itinéraire dans les tests qui ont été réalisés, je pense que c’est juste que le serveur arrête de chercher au bout d’un certain temps limite, pour des raisons bassement matérielles.
Mais ce qu’il faut comprendre, c’est que généralement, la classification des routes sert surtout à accélérer la recherche d’itinéraire. Bien sûr, rien n’empêche de la faire intervenir aussi dans la notion de coût, mais dans le cas de Waze, je parie que le temps de parcours moyen sur le segment est l’élément principal, avec aussi leur système de pénalités.
Voilà, je pense qu’une bonne manière intuitive de voir la classification des routes, c’est de se dire que plus une route est classée haut, plus elle est visible de loin. Ça ne change sans doute pas grand chose à son coût, (probablement avec l’exception des routes particulières : Parking Lot, etc). Par exemple, si on a une Major Highway qui traverse une ville et qu’il y a plein de feux, et que la circulation est toujours horrible, etc, avec une vitesse moyenne minable, ça ne veut pas dire que Waze va forcément préférer cette route. Ça veut seulement dire que le caractère pourri de cette route va être connu de loin.
Bon, bien sûr, je ne connais pas l’algorithme secret utilisé par Waze, donc tout ceci reste de la spéculation. Mais tous les algorithmes connus ont tout de même suffisamment de points communs pour avoir une petite idée…
