Le paradoxe de Braess

Interstate 405

L'Interstate 405 est l'une des principales autoroutes inter-États de Californie du Sud, et la plus importante route auxiliaire de l'Interstate 5 dans la région du Grand Los Angeles. 

La 405, qui compose le segment nord de la San Diego Freeway, est considéré comme l'autoroute la plus embouteillée du pays.

Le problème des embouteillages sur la San Diego Freeway si est important qu’il a donné naissance à une blague selon laquelle l'autoroute aurait été nommée 405 en raison du trafic qui s'y déplace à «quatre ou cinq» miles par heure. 

Il en résulte qu'il peut se révéler plus long de passer la région de Los Angeles en utilisant cette route qu'en prenant simplement l’ancien itinéraire, l'Interstate 5, bien que cette dernière passe par la ville. 

En 2011, une portion de l'autoroute a été fermée le temps d'un weekend afin d'y effectuer des travaux. Le fort impact sur le trafic qui était attendu avait qualifié l’événement de «Carmageddon», en référence au terme biblique Armageddon. 

Les autorités ont été très surprises de constater l'absence du fort trafic qu'elles redoutaient dans une large zone à cette occasion. 

C’est l’effet du paradoxe de Braess.

Le paradoxe

En mathématiques, et plus précisément en théorie des jeux, le paradoxe de Braess énonce que l'ajout d'une nouvelle route dans un réseau peut réduire la performance globale, lorsque les entités se déplaçant choisissent leur route individuellement. 

Ce paradoxe a été mis en évidence en 1968 par le mathématicien allemand Dietrich Braess.

Démonstration

Considérons le réseau décrit dans le diagramme ci-contre, sur lequel 4.000 conducteurs souhaitent aller du point "Start" au point "End".

Sur la voie "StartA" et la voie "BEnd", le temps de trajet est égal au nombre de voyageurs (T) divisé par 100, et sur la voie "StartB" et la voie "AEnd", il est constant à 45 minutes.

Si la voie en pointillé n'existe pas, le réseau possède alors 4 voies, le temps pour effectuer "StartAEnd" avec «a» véhicules devrait être :

a/100 + 45.

Et le temps pour effectuer "StartBEnd" avec «b» véhicules devrait être :

45 + b/100

Comme il y a 4.000 conducteurs, et que les deux trajets sont d’égale durée la répartition globale est uniforme de part et d’autre.

a + b = 4.000

a = b = 2000

Chaque trajet dure :

2000/100 + 45 = 65 mn

Ajoutons l'axe représenté par la ligne en pointillé, avec un temps de parcours tellement court qu'il en est négligeable, c'est-à-dire qu'il compte 0.

Dans cette situation, tous les conducteurs vont choisir "StartA" plutôt que "StartB", car "StartA" prendra seulement, au pire :

4000/100= 40 mn

alors que "StartB" prendra à coup sûr 45 minutes.

Une fois au point A, tout conducteur rationnel choisira la route «rapide» vers B, et de là continuera vers End, car là encore, "ABEnd" prendra au plus :

0 + 4000/100 = 40 mn

Mais comme les 4000 conducteurs font le même raisonnement, le temps de trajet de chaque conducteur est donc de :

4000/100 + 4000/100 = 80 mn,

un temps supérieur aux 65 minutes requises quand la ligne rapide "AB" n'existait pas.

Aucun conducteur n'a intérêt à changer, car les deux routes initiales, "StartAEnd" et "StartBEnd" prennent maintenant toutes les deux 85 minutes puisque les tronçons T/100 supportent potentiellement la totalité du trafic au lieu de se le partager.

Si tous les conducteurs se mettaient d'accord pour ne pas utiliser la liaison "AB", chacun en bénéficierait, par une réduction de son trajet de 15 minutes.

Toutefois, parce qu'un conducteur individuel aura toujours intérêt à prendre la voie "AB", la distribution socialement optimale n'est pas stable, et le paradoxe de Braess se produit.

Dans le cas du paradoxe de Braess, les conducteurs vont continuer à basculer d’un itinéraire à l’autre jusqu'à atteindre un équilibre, en dépit d'une réduction de la performance globale. 

aller voir

L'ajout d'une route au réseau crée un nouveau choix qu'on peut rapprocher au dilemme du prisonnier.

Pour plus de détail sur le dilemme du prisonnier allez voir l’article là. . . .

Moralité

Le fait qu'une voie soit préférable à une autre dépend non seulement de la qualité de la voie, mais également de la densité du flux. 

Si chaque conducteur emprunte le chemin qui lui paraît le plus favorable, les temps de trajet résultant ne sont pas nécessairement les plus faibles. 

Comme on l’a vu, une extension du réseau routier peut entraîner une redistribution du réseau qui résulte en des temps de trajet plus longs.

Comme beaucoup d’autres sujets, ce n’est pas toujours une question de moyens. . . 
 

paradoxebraess

Sources

https://fr.wikipedia.org/wiki/Paradoxe_de_Braess

https://fr.wikipedia.org/wiki/Interstate_405_(Californie)

Photos

Interstate 405

Par User:NE2 — Email me if you would like a copy of the GIS data I created for the highways., Domaine public, https://commons.wikimedia.org/w/index.php?curid=3229718

https://upload.wikimedia.org/wikipedia/commons/thumb/4/4e/California_Interstate_405.svg/langfr-1280px-California_Interstate_405.svg.png

Par BraessParadoxRoadsExample.png: Original téléversé par Reb42 sur Wikipédia anglais.derivative work: Rehua (talk) — Ce fichier est dérivé de : BraessParadoxRoadsExample.png:, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=18157386

https://upload.wikimedia.org/wikipedia/commons/thumb/0/01/Braess_paradox_road_example.svg/1920px-Braess_paradox_road_example.svg.png

prisonnier

https://images.pexels.com/photos/5369188/pexels-photo-5369188.jpeg

réseau

https://fr.freepik.com/photos/reseau

Réseau photo créé par natanaelginting – fr.freepik.com

https://img.freepik.com/photos-gratuite/groupe-personnes-reseau-circuit-board-connexion-connexion-technologie_1379-887.jpg