Calculer le diamètre du réseau routier mondial

L'équipe-projet commune Inria Gang du Laboratoire d'Informatique Algorithmique: Fondements et Applications (LIAFA - CNRS/Université Paris-Diderot) a calculé récemment le diamètre du réseau routier mondial. Plus qu'un défi calculatoire, il s'agit d'un pas dans la résolution effective des problèmes de distances dans les grands graphes.



Le diamètre d'un graphe est la distance entre les deux points les plus éloignés du graphe. Dans le réseau routier, la notion de distance qui nous intéresse le plus souvent est le temps de trajet. Trouver le diamètre du réseau routier mondial revient donc à trouver deux points tels que le temps de trajet pour aller de l'un à l'autre est maximal. Une fois ces deux points identifiés, on peut alors calculer le plus court trajet qui va de l'un à l'autre pour obtenir, en quelque sorte, le plus long "road trip" possible au monde. Calculer le diamètre d'un graphe requiert en général de calculer toutes les distances pour toutes paires de nœuds, ce qui est infaisable pour un graphe aussi grand.


C'est un sujet d'actualité qui a donné lieu à de nombreux résultats théoriques montrant la quasi-impossibilité d'un algorithme vraiment efficace sur tous les graphes (temps de calcul proportionnel à la taille de la donnée). Cette impossibilité dépend d'une conjecture SETH (Strong Exponential Time Hypothesis) sur la résolution du problème de satisfiabilité (SAT) qui est central en théorie de la complexité.


Cependant, l'équipe a développé une algorithmique basée sur des parcours de graphes qui s'avère très efficace sur de nombreux graphes rencontrés en pratique. Les réseaux routiers avec leurs structures très diversifiées fournissent un ensemble de données de grande taille qui ont permis de tester les algorithmes. Grâce à OpenStreetMap, l'équipe a pu ainsi calculer le diamètre routier du monde (et d'autres parties plus restreintes du réseau routier) et les visualiser. Les algorithmes peuvent être adaptés pour calculer aussi les centres des réseaux, c'est-à-dire les points depuis lesquels on peut atteindre tout autre point en un temps qui soit le plus petit possible. Cependant le calcul des centres s'avère moins efficace que pour le calcul du diamètre de certaines parties du réseau et la prochaine étape consistera donc à l'améliorer. À plus long terme, l'équipe cherche à obtenir des représentations succinctes et algorithmiquement efficaces de toutes les distances dans de tels graphes.

Pour plus d'information voir:
Road network project at Gang