Un nouvel algorithme permet d’éviter les embouteillages dans n’importe quelle mégalopole

Le trafic routier est sans doute le domaine où l'irrationalité humaine fait le plus de dégâts. Nous construisons toujours plus de voies de circulation autour des villes, en gardant à l'esprit une hypothèse totalement erronée : sur la route, les individus se comportent de telle manière à encourager une conduite régulière et efficace, et à dissuader une conduite dangereuse et anarchique. Ainsi, on tente de faire circuler des quantités invraisemblables de voitures dans un espace limité, à une vitesse suffisamment élevée pour que le trafic soit fluide.

Évidemment, ça ne fonctionne pas. Pourquoi ? Parce que la conduite humaine ne ressemble en aucun cas à la conduite idéale que l'on modélise pour prédire l'évolution du trafic. Les gens coincés dans les bouchons démarrent et accélérèrent brusquement dès que la voiture qui les précède avance de trois mètres, un temps pluvieux favorise l'énervement et les ralentissements injustifiés, et enfin, tout le monde appuie sur la pédale de frein devant un carambolage dans l'espoir d'apercevoir un type en sang.

Parce qu'il existe des conducteurs prudents, des conducteurs imprudents, des personnes impulsives, des mous et des spécialistes du tête à queue, en matière de conduite automobile, il n'existe pas vraiment de « conduite typique » qui permettrait de faire des prédictions précises sur l'état du trafic en un temps t. Conséquences : la plupart des métropoles sont si embouteillées que l'on gagnerait à se rendre au travail en deltaplane.

Depuis quelques années, les urbanistes, ingénieurs et autres spécialistes de prospective urbaine imaginaient que l'émergence des voitures autonomes allait régler tous les problèmes de circulation automobile du monde. Si nous pouvions nous débarrasser du comportement irrationnel des humains au volant en déléguant le pilotage de la bagnole à une IA, alors on pourrait sérieusement fluidifier le trafic routier. Le problème, c'est que tous ces joyeux experts n'avaient pas prévu que le public répugnerait à confier son destin à un système intelligent. Ils n'avaient pas prévu non plus qu'en 2017, l'horizon de la voiture autonome parfaitement fonctionnelle serait encore très lointain.

En attendant ce jour béni, des chercheurs en informatique de l'Université technologique de Nanyang ont développé un nouvel algorithme de routage intelligent qui permet de réduire la fréquence des « embouteillages spontanés » – ces accumulations de voitures provoquées par la convergence de plusieurs voies de circulation. Il s'agit d'un système de calcul distribué extrêmement rapide qui satisfait toutes les exigences d'un système de gestion du trafic en temps réel. Le travail des chercheurs est décrit dans le numéro d'avril d'IEEE Transactions on Emerging Topics in Computational Intelligence.

Le routage (ou sélection de route) est une branche traditionnelle de l'informatique. Ici, il s'agit plus précisément de s'appuyer sur la théorie des graphes, un domaine qui utilisait des algorithmes bien avant que le premier ordinateur électronique ne soit construit. Le problème, c'est que les algorithmes de routage peuvent être extrêmement complexes, même quand ils n'ont à gérer qu'un petit nombre d'acteurs et de chemins possibles. Le trafic routier réel, lui, exige d'effectuer des calculs impliquant un très grand nombre de routes, de voitures et autres agents (comme les feux de circulation).

L'algorithme des chercheurs de Nanyang part de l'assomption selon laquelle à partir d'une certaine densité de circulation, les problèmes vont émerger d'eux-mêmes. À un moment ou à un autre, un conducteur va forcément prendre une mauvaise initiative qui perturbera le trafic jusqu'à provoquer une rupture du réseau. Ce terme technique signifie que pendant une certaine période de temps, sur un segment de route donné, le trafic sortant sera moindre que le trafic entrant.

« Nous partons du principe que nous possédons déjà un bon modèle de répartition du trafic, et que la probabilité d'une rupture du trafic est supérieure à zéro (ce qui signifie qu'à un moment donné, il va nécessairement y avoir un ralentissement ou un embouteillage). Notre objectif est de rediriger les flux de la circulation de telle sorte que la probabilité de rupture du trafic soit réduite au maximum, » écrivent Hongliang Guo et ses collègues. En d'autres termes, « notre objectif est de maximiser la probabilité qu'aucune des routes du réseau ne soit sujette à un embouteillage. »

Cet objectif, c'est celui de l'algorithme, qui se matérialise sous la forme d'une équation toute simple. À partir de là, il suffisait de construire un système de machine learning efficace qui permet d'analyser le trafic en un temps t, d'y ajouter la charge de trafic supplémentaire qui pourrait affecter le réseau à tout moment, puis de calculer la probabilité d'une rupture à chacun des nœuds du réseau (ou intersections). Ajoutez à cela un soupçon d'algèbre linéaire et vous obtenez un système de calcul d'itinéraire idéal.

Guo et co. ont réussi à mettre au point les outils d'optimisation mathématiques qui permettent ce genre de calcul possible en temps réel. Ils ont pu démontrer l'efficacité de leur algorithme dans des simulations, et travaillent actuellement à améliorer leur système en partenariat BMW, qui leur fournit une vaste base de données de son parc automobile partagé de Munich.

Cette technologie pourrait être implantée très rapidement. En outre, il suffit d'optimiser l'itinéraire de 10% des véhicules du réseau pour fluidifier la circulation, ce qui signifie que la plupart des automobilistes pourront continuer à conduire comme des branques, en toute sérénité. Formidable, non ?