[News] Calculer le diamètre du réseau routier mondial

Ferroviaire, naval, routier, etc...

Modérateur : Modérateurs

Redbran
Messages : 619
Inscription : 16/05/2015 - 9:01:33
Activité : Profession libérale ou Indépendant

[News] Calculer le diamètre du réseau routier mondial

Message par Redbran » 15/12/2015 - 12:00:19

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.
ImageDiamètre du réseau routier mondial par continent
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é.
Image
Diamètre du réseau routier mondial par pays
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

Source: CNRS/INS2I
Illustration: INRIA

Avatar de l’utilisateur
POB
Messages : 548
Inscription : 08/05/2011 - 7:16:13
Activité : Retraité

Re: [News] Calculer le diamètre du réseau routier mondial

Message par POB » 15/12/2015 - 13:24:06

Point n'est besoin d'être grand clerc pour imaginer un maximum entre Le Cap et le détroit de Béring, maximum en distance et sans doute en temps au vu des contrées traversées.
Idem du Détroit de Béring au Cap Horn.
Le raid auto Cap Nord-Cap de Bonne Espérance n'a pas été refait et c'est bien dommage, cela changerait du sempiternel "Dakar".
Je sens la flamme du génie monter en moi. :D
:bieres:
C'est une grande misère de n'avoir pas assez d'esprit pour parler, ni assez de jugement pour se taire. (La Bruyère)

Avatar de l’utilisateur
macland
Messages : 4619
Inscription : 06/08/2005 - 9:44:31
Localisation : Ile de France

Re: [News] Calculer le diamètre du réseau routier mondial

Message par macland » 15/12/2015 - 16:06:59

...n'y a-t-il pas confusion entre diamètre et périmètre ???... :_grat:
L'homme est une espèce de singe qui a mal tourné!...
Si la tyrannie engendre des révoltes, le laxisme enfante l'anarchie…

Avatar de l’utilisateur
macland
Messages : 4619
Inscription : 06/08/2005 - 9:44:31
Localisation : Ile de France

Re: [News] Calculer le diamètre du réseau routier mondial

Message par macland » 15/12/2015 - 16:10:39

POB a écrit :...Le raid auto Cap Nord-Cap de Bonne Espérance n'a pas été refait et c'est bien dommage, cela changerait du sempiternel "Dakar"....
Je sens la flamme du génie monter en moi. :D
:bieres:
:+1: ...d'autant que le Paris Dakar n'a gardé que le nom pour s'expatrier outre-Atlantique...:0: :siffle:
L'homme est une espèce de singe qui a mal tourné!...
Si la tyrannie engendre des révoltes, le laxisme enfante l'anarchie…

Avatar de l’utilisateur
cisou9
Messages : 8795
Inscription : 12/03/2006 - 15:43:01
Activité : Retraité
Localisation : Pertuis en Lubéron

Re: [News] Calculer le diamètre du réseau routier mondial

Message par cisou9 » 15/12/2015 - 17:07:21

_____________________________ :_salut:
POB a écrit :Point n'est besoin d'être grand clerc pour imaginer un maximum entre Le Cap et le détroit de Béring, maximum en distance et sans doute en temps au vu des contrées traversées.
Imaginer oui, le calculer est une autre paire de manche !!! :lol:
macland a écrit : :+1: ...d'autant que le Paris Dakar n'a gardé que le nom pour s'expatrier outre-Atlantique...:0: :siffle:
Surtout que même Paris à disparu, seul Dakar reste !!! :fada2: _____
C'est vrai que le mot diamètre est surprenant il doit y avoir un problème de traduction !!! :_grat2: ___
Un homme est heureux tant qu'il décide de l'être et nul ne peux l'en empêcher.
Alexandre Soljenitsyne.

Kirken
Messages : 4
Inscription : 10/01/2011 - 22:09:09
Activité : Ingénieur

Re: [News] Calculer le diamètre du réseau routier mondial

Message par Kirken » 15/12/2015 - 20:16:35

Il faut revenir au sens littéral du terme diamètre. C'est bien d'un diamètre dont on parle.
Sur un cercle, il y a une infinité de diamètres qui passent par l'origine, mais ils sont tous égaux en longueur.
Dans une sphère, il y a une infinité de diamètres qui passent par l'origine, mais ils sont tous égaux en longueur.
Dans un graphe ouvert non dirigé, il y a un nombre fini de diamètres, mais tous de longueur variable.
On cherche le plus grand.

Pour rappel, le graphe est pondéré. Les arcs ont un poids, leur qualité étant le rapport distance, temps.
Les plus rapides sont sollicités. Mais nous cherchons les noeuds les plus écartés.
Les noeuds les plus diamétralement opposés au sens graphe.

Avatar de l’utilisateur
cisou9
Messages : 8795
Inscription : 12/03/2006 - 15:43:01
Activité : Retraité
Localisation : Pertuis en Lubéron

Re: [News] Calculer le diamètre du réseau routier mondial

Message par cisou9 » 16/12/2015 - 17:28:04

_______________ :_salut:
Merci Kirken en y réfléchissant bien, mon raisonnement était diamétralement opposé au tien !!! :lol: ___
Un homme est heureux tant qu'il décide de l'être et nul ne peux l'en empêcher.
Alexandre Soljenitsyne.

Répondre