Le paradoxe de Braess

L’enfer (des routes) est pavé de bonnes intentions…

« Abondance de biens ne nuit pas ». La prochaine fois que vous vous retrouverez dans un embouteillage, un jour de grand week-end, je vous suggère de penser très fort à cette maxime pleine de (faux) bon sens! Il y a en effet fort à parier que le bouchon dans lequel vous êtes coincé soit dû soit à un accident, soit à un rétrécissement de la chaussée un peu plus loin devant vous, quand la route passe de trois à deux voies. Les tronçons à trois voies sont les cauchemars de bison futés!

C’est qu’en matière de circulation routière le mieux est souvent l’ennemi du bien: dès 1968, Dietrich Braess (qui n’a même pas sa page sur Wikipedia en français, quel scandale!) a montré comment ajouter un itinéraire de délestage peut provoquer des congestions et allonger les temps de parcours au lieu de les raccourcir. Un petit modèle explique mieux qu’un long discours ce paradoxe de Braess.

Un petit modèle pour comprendre
Supposez que vous cherchiez à vous déplacer d’une ville (A) à une autre (D) plus vite possible. Deux itinéraires s’offrent à vous, l’un passant par B, l’autre passant par C, chacun composé d’un bout de nationale et d’une route départementale. Le temps de parcours sur les nationales est de 45 minutes quelque soit la circulation. Par contre, comme il y a des feux sur les départementales, le temps de parcours dépend du nombre de voitures X qui l’emprunte: il vaut par exemple X/100 minutes.

Supposons qu’il y ait 4000 voitures souhaitant passer de A à D. Si elles prennent toutes le trajet du haut (ABD) elles mettront 85 minutes. Idem si elles prennent toutes le trajet du bas. La situation optimale sera celle où le trafic s’équilibre entre les deux trajets. Le temps de parcours sera alors de 45 +2000/100 = 65 minutes.

Pour désengorger la circulation, on construit une voie ultra-rapide reliant B et C, dont le temps de parcours est négligeable quelque soit le nombre de véhicules qui l’emprunte (pas très réaliste mais bon c’est un modèle!). Avec cette voie rapide, le temps de parcours entre A et B devrait raccourcir, or c’est l’inverse qui se produit:

Le meilleur trajet pour les 4000 voitures est maintenant (ABCD): départementale – voie rapide – départementale et le temps de trajet passe ainsi de 65 minutes à 80 minutes! Essayez vous même: si une des voitures prenait un autre itinéraire, son trajet serait rallongé de 5 minutes (45+40=85).

Bien que pas n’étant pas la meilleure, cette situation est un équilibre parfaitement stable (« équilibre de Nash » pour les familiers de la théorie des Jeux) où personne n’a intérêt à changer de stratégie une fois qu’il connaît les choix des autres. Et si dans un monde utopique, la circulation s’établissait comme s’il n’y avait pas de voie rapide et se répartissait comme avant, entre les deux itinéraires ABD et ACD? A ce moment-là, un petit malin serait tenté de gagner du temps en « coupant » par ABCD (son trajet ne lui prendrait que 40 minutes s’il était le seul à tricher): il serait donc rapidement imité par d’autres… et la situation dériverait assez vite jusqu’à ce que tout le monde prenne finalement le parcours ACBD et se retrouve avec un temps de parcours de 80 minutes.

Un mécanisme bien connu en théorie des jeux
Pour les habitués de la théorie des jeux ce paradoxe n’est pas vraiment nouveau: Offrir plus de choix aux joueurs peut parfaitement faire perdre tout le monde! Voici une petite matrice de gains où chaque joueur (A et B) a deux stratégies possibles qu’on appellera « maximiser » ou « minimiser », vous allez voir pourquoi:

Gain de B
Gain de A
A
« maximise »
A
« minimise »
B « maximise »
4

4
5

1
B « minimise »
1

5
3

3

On lit ça comme ça: si A et B « maximisent » ils gagnent tous les deux 4€. Si A « maximise » alors que B « minimise », A gagne 5€ et B gagne 1€. On voit que si A « maximise », B a toujours intérêt à « maximiser ». Si A « minimise », B a aussi intérêt à « maximiser » (gain: 5€ plutôt que 3€ s’il « minimise »). Bref,dans tous les cas B a intérêt à « maximiser », et comme la matrice est symétrique, A aussi. Les deux joueurs ont intérêt à « maximiser » dans tous les cas (d’où le nom de cette stratégie ;-).

Maintenant supposons qu’on introduise une troisième stratégie possible, qu’on appellera « ruser », avec la matrice des gains suivants:

Gain de B
Gain de A
A
« maximise »
A
« minimise »
A

« ruse »
B « maximise »
4

4
5

1
-10

10
B « minimise »
1

5
3

3
-10

10
B « ruse »
10

-10
10

-10
-9

-9

Désormais que A « maximise » ou « minimise », B a toujours intérêt à « ruser » (il gagne 10€), et si A « ruse », B a aussi intérêt à le faire (il ne perd que 9€ au lieu d’en perdre 10). B a donc toujours intérêt à « ruser ». A aussi car notre matrice est symétrique. L’équilibre s’est maintenant déplacé vers la situation où les deux joueurs « rusent ». Avec beaucoup de guillemets car le bilan c’est qu’ils perdent chacun 9€! Voilà comment un choix supplémentaire donné aux joueurs s’avère néfaste pour tout le monde, comme la route .

Et dans la vraie vie?

Théoriques, tous ces modèles? Pas du tout! A New York, par exemple la fermeture provisoire de la 42eme avenue en 1990 a réduit les embouteillages dans cette zone, contrairement à toute attente. A l’inverse, à Stuttgart, le nouvel axe routier censé désengorger le centre-ville a créé tellement d’embouteillages à sa création, qu’il a fallu le fermer pour retrouver un trafic plus fluide. Pareil à Séoul: la méthode la plus efficace pour alléger le trafic a été d’investir près de 400 millions de dollars pour détruire une des voies rapides à la périphérie de la ville.

Il est très difficile de savoir si un axe routier supplémentaire améliore ou dégrade la qualité de la circulation, car les mécanismes du trafic urbain sont affreusement compliqués. La théorie prévoit qu’au pire on multiplie par deux (pas plus) les embouteillages: nous voilà rassurés!

Et à Paris au fait? Je n’ai rien trouvé l’impact de la fermeture des quais les dimanches et lors des opérations Paris-Plage en été. Sauf bien sûr les plaintes des riverains et des automobilistes avant

Plus fort que la mécanique des fluides
Ce qui rend le paradoxe de Braess… paradoxal, c’est qu’on associe instinctivement la circulation routière à un « flot » de voitures, donc soumis aux mêmes principes d’écoulements que les liquides ou les gaz. Or dans un écoulement fluide, plus il y a de chemins possibles, plus l’écoulement est facile: aucun plombier n’a encore vu de système dans lequel ajouter un tuyau d’évacuation boucherait des éviers.

La raison profonde de cette différence entre nous et les molécules d’eau, implicite dans nos modèles, me semble venir du fait que nous cherchons à rejoindre notre but le plus vite possible, compte de ce que les autres font (ou ont intérêt à faire). Dès qu’on spécule de la sorte, nos déplacements collectifs échappent aux règles de la mécanique des fluides et fabriquent des problèmes inédits. Autrement dit notre intelligence est la source de nos embouteillages. Il faut bien que réfléchir ait aussi des petits inconvénients…

Sources (en anglais):
L’article de Wikipedia
Le cours de « science of the Web » sur le sujet (oct 2008)
Ce cours du Californian Institute of Technology (Julian Romero, Caltech, janv 2008)

Billets connexes:
Psychologie de l’incivilité au volant
Le mieux en pire, pour un autre petit exemple d’améliorer les choses en les empirant

5 comments for “Le paradoxe de Braess

  1. jid
    14/05/2009 at 14:35

    >et si tout le monde suivait les indications de son GPS sans réfléchir?

  2. Xochipilli
    14/05/2009 at 18:02

    >En l’occurrence ça risquerait d’être encore pire, car le GPS calcule les meilleurs trajets lorsque la circulation est fluide! Et dans l’exemple du paradoxe, il enverrait tout le monde prendre le chemin ABCD, assumant que X est petit… C’est bien l’objectif de minimiser le temps de parcours qui est la cause de tous nos petits malheurs.

  3. @gor
    15/05/2009 at 11:31

    >Hé bien ce n’est pas si sûr!Avec les informations sur la circulation (TMC je crois, à vérifier), on arriverait plutôt à un système qui varie selon une fréquence: Le GPS sait que le trajet ABCD est le plus court, mais il y a déjà trop de monde, il fait donc prendre le trajet ACD où il y a le moins de monde, et ce pour pas mal de personnes.Une fois qu’il y a plus de monde sur le trajet ACD que sur celui ABD, il fait passer par ce dernier.Puis quand les 2 précédents sont plus engorgés que le 3eme, il fait passé par le 3eme.Comme les flux de voitures varient, cela ferait que la circulation varierait selon une fréquence.Enfin, voilà comment je vois les choses. Cependant, je pars du principe que tout le monde a un GPS, ce qui n’est pas le cas et ne le sera pas (pour aller au travail, je doute qu’on prenne un GPS ^^).Sinon il reste le système utilisé par toyota au japon: un service surveille la circulation en temps réel et informe les utilisateur. Cela permet, si c’est bien gérer, de pouvoir en plus prévoir la répartition des flux de voiture. Ceci si tout le monde suit les indications (ce qui là pourrait être plus probable déjà)Qu’en pensez-vous?

  4. Xochipilli
    15/05/2009 at 13:19

    >@gor: je ne suis pas sûr que plus d’intelligence dans les GPS permette d’échapper au paradoxe de Baess. Je m’explique:Un GPS aide à éviter les embouteillages en général. Mais ce qui caractérise les embouteillages « paradoxaux » décrits dans ce billet, c’est qu’ils ne sont pas dûs à un déficit d’information ou d’intelligence de la part des conducteurs (au contraire), mais à leur recherche du meilleur trajet individuel. Or c’est précisément ce que vise un GPS classique.Pour éviter le phénomène, il faudrait donc que l’on programme l’algorithme du GPS différemment, afin qu’il recherchent le trajet optimal collectivement, même si ce trajet n’optimise pas celui de son propriétaire: pas gagné, à mon avis!

  5. Anonymous
    30/09/2010 at 15:03

    >je ne suis pas totalement sur de ce que j'avance, mais en electricité on aurait le même problème :dans un circuit avec 2 resistance en paralèlle, ajouter un troisième resitance en paralèlle, même inférieur à la resistance des deux première, multiplie la resitance globale du système.Il serait intéressant de voir le problème en mécanique des fluides comme suggérer dans l'article.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *