Complètement à l'ouest

Dans un récent article, on a abordé le sys­tème rou­tier en grille de Van­cou­ver, ainsi que les avan­tages que ça apporte. Un avan­tage que je n’ai pas men­tionné est la géné­ri­cité d’un tel sys­tème en ce qui concerne les déplacements.

Par exemple, le dépla­ce­ment suivant:

…est équi­valent au dépla­ce­ment suivant:

…si on consi­dère que l’important, c’est le point de départ et le point d’arrivée.

Il s’agit alors de trou­ver, parmi les nom­breuses pos­si­bi­li­tés de dépla­ce­ment, laquelle sera la plus rapide.

Contexte et postulats

Comme je me déplace prin­ci­pa­le­ment à pied per­so­nel­le­ment, je ne vais par­ler que de pié­tons ici. Ensuite, comme on se déplace sur une grille, la dis­tance est la même quelque soit la tra­jec­toire (si on ne prend évi­dem­ment en compte que les tra­jec­toires directes qui ne font pas de détour). Si on exclut les consi­dé­ra­tions telles que les varia­tions de vitesse en fonc­tion de la pente, le seul fac­teur réel­le­ment impac­tant dans le temps de tra­jet est le temps d’attente aux feux rouges.

J’ai écrit un petit pro­gramme per­met­tant de simu­ler le tra­jet d’un pie­ton à tra­vers une grille, duquel je tire les dia­grammes et les chiffres que je donne dans la suite de cet article. Les hypo­thèses de départ sont les suivantes:

• Du point de vue du pié­ton, les feux de cir­cu­la­tion sont aléa­toires. En vérité, ils sont plus ou moins syn­chro­ni­sés, mais comme cette syn­chro­ni­sa­tion est faite pour les voi­tures, qui se déplacent de manière signi­fi­ca­ti­ve­ment plus rapide que les pié­tons, elle est tota­le­ment per­due pour une vitesse moyenne de marche. De plus, une dif­fé­rence de quelques pour­cents dans la vitesse de marche amène une grande dif­fé­rence dans l’état des feux ren­con­trés pen­dant le tra­jet. Comme il s’agit ici de trou­ver un algo­rithme géné­rique qui ne dépend ni du lieu géo­gra­phique, ni du pié­ton, j’ai opté pour un modèle aléa­toire de feux de circulation.
• Le temps de feu vert et de feu rouge est de 30 secondes cha­cun. En bon fran­çais, on tra­verse en cou­rant comme un sagouin au feu orange cli­gno­tant, donc je compte ça comme un feu vert.
• La grille est uni­forme, et chaque inter­sec­tion est iden­tique. En pra­tique, il y a sûre­ment quelques endroits dans votre quar­tier où la grille est “cas­sée” d’une manière ou d’une autre. Sur mon tra­jet jour­na­lier pour aller au bureau, par exemple, je sais qu’en lon­geant le B.C. Sta­dium, j’avancerai de 3 pâtés de mai­son sans ren­con­trer d’intersection, et donc garanti sans feu rouge. J’optimise donc mon tra­jet mati­nal en don­nant un biais à mon algo­rithme de manière à pas­ser par là si cela semble bénéfique.

Le but du jeu est, par­tant d’une inter­sec­tion don­née, aller à une autre inter­sec­tion don­née. Disons que cette des­ti­na­tion est le croi­se­ment de la rue Lati­tude (qui est “hori­zon­tale”, orien­tée d’est en ouest) et de la rue Lon­gi­tude (qui est “ver­ti­cale”, orien­tée du nord au sud).

Quelques algo­rithmes simples

L’aglorithme le plus simple, voire le plus stu­pide, consiste à aller tout droit en par­tant de chez soi jusqu’à atteindre la rue Lati­tude, puis de remon­ter cette rue jusqu’à atteindre Lon­gi­tude.

Un algo­rithme tou­jours simple, mais un peu plus malin, consiste à tra­ver­ser sys­té­ma­ti­que­ment la rue du côté où on voit un feu vert. Une fois de l’autre côté, on conti­nue sur sa tra­jec­toire. Si on atteint l’une des deux rues ter­mi­nales (Lati­tude ou Lon­gi­tude), on se contente alors d’aller tout droit jusqu’à la des­ti­na­tion. J’ai appellé cet algo­rithme “algo­rithme opportuniste”.

Pour mes tests, j’ai consi­déré 4 types de tra­jets: 5x5, 5x10, 10x10 et 10x20, où les deux chiffres cor­res­pondent au nombre de pâtés de mai­son à tra­ver­ser res­pec­ti­ve­ment vers l’est et vers le nord (on démarre donc “en bas à gauche” et on va “en haut à droite”). Ces 4 tra­jets sont simu­lés 100.000 fois pour cha­cun des algo­rithmes, et le temps d’attente total de chaque tra­jet est enre­gis­tré (le temps d’attente total d’un tra­jet étant la somme de toutes les attentes à tous les feux rouges ren­con­trés). Je n’ai pas été au delà de 10x20 car j’estime qu’une dis­tance plus grande inci­tera à prendre son vélo ou les trans­ports en com­mun, à moins qu’on soit en train de se bala­der, auquel cas on est pas pressé. Pour infor­ma­tion, mon tra­jet pour aller au bureau est de 7x8.

On peut déjà consta­ter que l’algorithme oppor­tu­niste est non seule­ment net­te­ment plus effi­cace que l’algorithme stu­pide, mais aussi plus sûr.

On constate éga­le­ment que l’algorithme oppor­tu­niste ren­contre moins d’attente en moyenne pour un tra­jet 10x10 qu’un tra­jet 5x10, alors que c’est un tra­jet plus long. Mon inter­pré­ta­tion est que comme 5x10 est un tra­jet plus “étroit”, le pié­ton peut plus rapi­de­ment débou­cher sur la rue Lon­gi­tude, et se retrou­ver à devoir avan­cer bête­ment tout droit, sans aucun autre choix que d’attendre à chaque feu rouge. Le tra­jet 10x10, par contre, est “large”, et per­met au pié­ton d’avoir plus de “marge de manoeuvre” pour tour­ner à droite ou à gauche en fonc­tion des feux.

Un peu d’optimisation

On peut légè­re­ment amé­lio­rer l’algorithme oppor­tu­niste, de manière simple. Lorsqu’on se retrouve à un coin sud-ouest d’un pâté de mai­son (juste après avoir tra­versé la rue, donc), plu­tôt que de conti­nuer dans la direc­tion qu’on sui­vait pré­cé­dem­ment, on se diri­gera dans la direc­tion vers laquelle il nous reste le plus de che­min à par­cou­rir. Ainsi, si on est est plus près, en nombre de pâtés de mai­son, de la rue Lon­gi­tude que de la rue Lati­tude, on ira vers le nord. Sinon, on ira vers l’est. Cet algo­rithme est “l’opportuniste légè­re­ment malin”.

Cette opti­mi­sa­tion donne des résul­tats assez frappants:

Un peu plus d’optimisation (enfin, une tentative)

J’ai ensuite écrit deux nou­veaux algo­rithmes: “l’opportuniste malin”, et le “sacri­fi­ciel”. Ces deux algo­rithmes ont pour but de cor­ri­ger le pro­blème que j’ai men­tionné à pro­pos des tra­jets “étroits”, et de la situa­tion peu dési­rable d’aboutir sur une rue ter­mi­nale alors que l’autre rue ter­mi­nale est à plu­sieurs pâtés de mai­son de là. Il s’agit donc de lais­ser plus de “marge de manoeuvre” au pié­ton en essayant d’atteindre les deux rues ter­mi­nales le plus pos­sible en même temps, même s’il faut sacri­fier un peu de temps au milieu du trajet.

L’opportuniste malin reprend l’algorithme de l’opportuniste légè­re­ment malin, mais y ajoute la varia­tion suivante:

• Si on se trouve plus proche d’une des deux rues ter­mi­nales par rap­port à l’autre (par exemple on est à 2 pâtés de mai­son de Lon­gi­tude, et à 5 de Lati­tude), on peut igno­rer un feu vert et pré­fé­rer, si pos­sible, tour­ner en res­tant sur le même bloc afin de se diri­ger vers la rue ter­mi­nale la plus loin­taine. Par exemple, si on est au coin nord-ouest d’un bloc et que le feu vert nous per­met­trait de tra­ver­ser vers le nord, mais qu’on se trouve très proches de Lati­tude, on ne va pas tra­ver­ser, et plu­tôt lon­ger le bloc vers l’est afin de se rap­pro­cher de Lon­gi­tude.

L’algorithme sacri­fi­ciel, lui, va plus loin, accep­tant de faire des sacrifices:

• Si on se trouve vrai­ment très proche d’une des deux rues ter­mi­nales, on veut abso­lu­ment conti­nuer vers la rue ter­mi­nale la plus loin­taine, même si cela veut dire qu’on se tape un feu rouge.
• On n’accepte de se taper un feu rouge que si ce feu rouge est “bien mûr”, à savoir qu’on ne l’a pas vu pas­ser au rouge alors qu’on appro­chait. J’estime que si le feu dure 30 secondes, on peut rai­son­na­ble­ment savoir si un feu est rouge depuis au moins 20 secondes, car cela veut dire qu’il est ren­tré dans le champ de vision du pié­ton 30 mètres envi­ron avant que celui-ci l’atteigne. Le pié­ton peut en plus s’aider du feu per­pen­di­cu­laire, qui devrait cli­gno­ter en orange si le croi­se­ment va bien­tôt bas­cu­ler de sens. J’ai uti­lisé 2 ins­tances de cet algo­rithme: un qui accepte de se taper des feux rouges vieux d’au moins 20 secondes, et un qui accepte ceux vieux d’au moins 25 secondes (ce qui veut dire qu’on sacri­fie, au plus, 10 et 5 secondes respectivement).
• On n’accepte de se taper un feu rouge que si l’on est signi­fi­ca­ti­ve­ment plus proche d’une rue ter­mi­nale que d’une autre. Les 2 ins­tances de l’algorithme uti­lisent éga­le­ment 2 réglages dif­fé­rents pour cela: une qui accepte de sacri­fier du temps si on est 3 fois plus loin d’une rue ter­mi­nale que d’une autre, et une qui accepte lorsqu’on est 4 fois plus loin.
• Les 2 ins­tances sont nom­mées, dans les graphes ci-dessous, “Sacri­fi­cal 3/-10″ (3 fois plus loin, 10 secondes) et “Sacri­fi­cial 4/-5″ (4 fois plus loin, 5 secondes). Le pre­mier algo­rithme est donc plus prompt à sacri­fier du temps à un feu rouge que le deuxième.

D’abord, on constate que l’opportuniste malin est en fait moins effi­cace que l’opportuniste légè­re­ment malin. Je pense que c’est tout sim­ple­ment parce qu’on fait l’erreur de tro­quer un “gain cer­tain” (un feu vert) pour un “gain hypo­thé­ti­que­ment plus grand” (igno­rer le feu vert et aller à une autre inter­sec­tion pour se rap­pro­cher de la rue ter­mi­nale la plus loin­taine, mais s’exposer à la pos­si­bi­lité d’avoir un feu rouge mal placé). Cette erreur est un phé­no­mène assez clas­sique de psy­cho­lo­gie humaine, et est bien sou­vent peu béné­fique, comme on peut le voir éga­le­ment dans des jeux comme “Deal Or No Deal”, connu pen­dant un temps dans l’hexagone sous le titre “A prendre ou a lais­ser”, alias “La Boi­boite D’Arthur”.

L’algorithme sacri­fi­ciel, lui, per­met de gra­piller quelques secondes dans cer­tains cas, notam­ment les cas où, jus­te­ment, il y a peu de marge de manoeuvre dès le depart (tra­jets courts ou “étroits”), mais perd de son inté­rêt pour les voyages longs et “larges”. De plus, il est légè­re­ment moins sûr que la plu­part des autres algo­rithmes. N’oublions pas éga­le­ment que dans le monde réel l’évaluation de l’âge d’un feu rouge peut être gênée par divers phé­no­mènes, tel que l’obstruction de la vue du pié­ton, par exemple, ce qui rend l’application de cet algo­rithme plus délicat.

Conclu­sion

Il me semble que l’algorithme oppor­tu­niste légè­re­ment malin est le plus effi­cace, sur­tout si on le com­bine sub­ti­le­ment, ici et là, avec un peu d’algorithme sacri­fi­ciel, notam­ment quand on se retrouve à des dis­tances trop inégales des deux rues ter­mi­nales, et qu’on est rela­ti­ve­ment sûr de son éva­lua­tion de l’âge d’un feu rouge (la plu­part du temps parce que le feu per­pen­di­cu­laire cli­gnote depuis plu­sieurs secondes). Enfin, lorsqu’on com­bine le tout avec une cer­taine connais­sance du quar­tier, on peut faire des tra­jets sans aucun temps d’attente à aucun feu rouge dans la majo­rité des cas!

Si vous avez repéré des erreurs, ou que vous avez des sug­ges­tions, n’hésitez pas à pos­ter un com­men­taire. Et pour ceux qui vont inévi­ta­ble­ment me dire que c’est beau­coup s’embêter pour éco­no­mi­ser 23 secondes par jour, je leur dis “crotte”. En plus, ces gens là ne sont sans doute pas ingé­nieurs, donc ils ne peuvent pas com­prendre qu’être ingé­nieur c’est plus qu’une for­ma­tion, un métier, une pas­sion… c’est un véri­table mode vie! La quête du savoir! La soif d’optimisation! La joie de gas­piller du temps et de l’argent à tra­vailler sur des choses inutiles! Sans oublier la com­pul­sion à ache­ter plein de gad­gets hors de prix, et le plai­sir de chauf­fer son appar­te­ment uni­que­ment avec leur effet Joule! Rah la la, vous savez pas ce que vous ratez les gars.