Dans un récent article, on a abordé le système routier en grille de Vancouver, ainsi que les avantages que ça apporte. Un avantage que je n’ai pas mentionné est la généricité d’un tel système en ce qui concerne les déplacements.
Par exemple, le déplacement suivant:
…est équivalent au déplacement suivant:
…si on considère que l’important, c’est le point de départ et le point d’arrivée.
Il s’agit alors de trouver, parmi les nombreuses possibilités de déplacement, laquelle sera la plus rapide.
Contexte et postulats
Comme je me déplace principalement à pied personellement, je ne vais parler que de piétons ici. Ensuite, comme on se déplace sur une grille, la distance est la même quelque soit la trajectoire (si on ne prend évidemment en compte que les trajectoires directes qui ne font pas de détour). Si on exclut les considérations telles que les variations de vitesse en fonction de la pente, le seul facteur réellement impactant dans le temps de trajet est le temps d’attente aux feux rouges.
J’ai écrit un petit programme permettant de simuler le trajet d’un pieton à travers une grille, duquel je tire les diagrammes et les chiffres que je donne dans la suite de cet article. Les hypothèses de départ sont les suivantes:
- Du point de vue du piéton, les feux de circulation sont aléatoires. En vérité, ils sont plus ou moins synchronisés, mais comme cette synchronisation est faite pour les voitures, qui se déplacent de manière significativement plus rapide que les piétons, elle est totalement perdue pour une vitesse moyenne de marche. De plus, une différence de quelques pourcents dans la vitesse de marche amène une grande différence dans l’état des feux rencontrés pendant le trajet. Comme il s’agit ici de trouver un algorithme générique qui ne dépend ni du lieu géographique, ni du piéton, j’ai opté pour un modèle aléatoire de feux de circulation.
- Le temps de feu vert et de feu rouge est de 30 secondes chacun. En bon français, on traverse en courant comme un sagouin au feu orange clignotant, donc je compte ça comme un feu vert.
- La grille est uniforme, et chaque intersection est identique. En pratique, il y a sûrement quelques endroits dans votre quartier où la grille est “cassée” d’une manière ou d’une autre. Sur mon trajet journalier pour aller au bureau, par exemple, je sais qu’en longeant le B.C. Stadium, j’avancerai de 3 pâtés de maison sans rencontrer d’intersection, et donc garanti sans feu rouge. J’optimise donc mon trajet matinal en donnant un biais à mon algorithme de manière à passer par là si cela semble bénéfique.
Le but du jeu est, partant d’une intersection donnée, aller à une autre intersection donnée. Disons que cette destination est le croisement de la rue Latitude (qui est “horizontale”, orientée d’est en ouest) et de la rue Longitude (qui est “verticale”, orientée du nord au sud).
Quelques algorithmes simples
L’aglorithme le plus simple, voire le plus stupide, consiste à aller tout droit en partant de chez soi jusqu’à atteindre la rue Latitude, puis de remonter cette rue jusqu’à atteindre Longitude.
Un algorithme toujours simple, mais un peu plus malin, consiste à traverser systématiquement la rue du côté où on voit un feu vert. Une fois de l’autre côté, on continue sur sa trajectoire. Si on atteint l’une des deux rues terminales (Latitude ou Longitude), on se contente alors d’aller tout droit jusqu’à la destination. J’ai appellé cet algorithme “algorithme opportuniste”.
Pour mes tests, j’ai considéré 4 types de trajets: 5x5, 5x10, 10x10 et 10x20, où les deux chiffres correspondent au nombre de pâtés de maison à traverser respectivement vers l’est et vers le nord (on démarre donc “en bas à gauche” et on va “en haut à droite”). Ces 4 trajets sont simulés 100.000 fois pour chacun des algorithmes, et le temps d’attente total de chaque trajet est enregistré (le temps d’attente total d’un trajet étant la somme de toutes les attentes à tous les feux rouges rencontrés). Je n’ai pas été au delà de 10x20 car j’estime qu’une distance plus grande incitera à prendre son vélo ou les transports en commun, à moins qu’on soit en train de se balader, auquel cas on est pas pressé. Pour information, mon trajet pour aller au bureau est de 7x8.
On peut déjà constater que l’algorithme opportuniste est non seulement nettement plus efficace que l’algorithme stupide, mais aussi plus sûr.
On constate également que l’algorithme opportuniste rencontre moins d’attente en moyenne pour un trajet 10x10 qu’un trajet 5x10, alors que c’est un trajet plus long. Mon interprétation est que comme 5x10 est un trajet plus “étroit”, le piéton peut plus rapidement déboucher sur la rue Longitude, et se retrouver à devoir avancer bêtement tout droit, sans aucun autre choix que d’attendre à chaque feu rouge. Le trajet 10x10, par contre, est “large”, et permet au piéton d’avoir plus de “marge de manoeuvre” pour tourner à droite ou à gauche en fonction des feux.
Un peu d’optimisation
On peut légèrement améliorer l’algorithme opportuniste, de manière simple. Lorsqu’on se retrouve à un coin sud-ouest d’un pâté de maison (juste après avoir traversé la rue, donc), plutôt que de continuer dans la direction qu’on suivait précédemment, on se dirigera dans la direction vers laquelle il nous reste le plus de chemin à parcourir. Ainsi, si on est est plus près, en nombre de pâtés de maison, de la rue Longitude que de la rue Latitude, on ira vers le nord. Sinon, on ira vers l’est. Cet algorithme est “l’opportuniste légèrement malin”.
Cette optimisation donne des résultats assez frappants:
Un peu plus d’optimisation (enfin, une tentative)
J’ai ensuite écrit deux nouveaux algorithmes: “l’opportuniste malin”, et le “sacrificiel”. Ces deux algorithmes ont pour but de corriger le problème que j’ai mentionné à propos des trajets “étroits”, et de la situation peu désirable d’aboutir sur une rue terminale alors que l’autre rue terminale est à plusieurs pâtés de maison de là. Il s’agit donc de laisser plus de “marge de manoeuvre” au piéton en essayant d’atteindre les deux rues terminales le plus possible en même temps, même s’il faut sacrifier un peu de temps au milieu du trajet.
L’opportuniste malin reprend l’algorithme de l’opportuniste légèrement malin, mais y ajoute la variation suivante:
- Si on se trouve plus proche d’une des deux rues terminales par rapport à l’autre (par exemple on est à 2 pâtés de maison de Longitude, et à 5 de Latitude), on peut ignorer un feu vert et préférer, si possible, tourner en restant sur le même bloc afin de se diriger vers la rue terminale la plus lointaine. Par exemple, si on est au coin nord-ouest d’un bloc et que le feu vert nous permettrait de traverser vers le nord, mais qu’on se trouve très proches de Latitude, on ne va pas traverser, et plutôt longer le bloc vers l’est afin de se rapprocher de Longitude.
L’algorithme sacrificiel, lui, va plus loin, acceptant de faire des sacrifices:
- Si on se trouve vraiment très proche d’une des deux rues terminales, on veut absolument continuer vers la rue terminale la plus lointaine, 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 passer au rouge alors qu’on approchait. J’estime que si le feu dure 30 secondes, on peut raisonnablement savoir si un feu est rouge depuis au moins 20 secondes, car cela veut dire qu’il est rentré dans le champ de vision du piéton 30 mètres environ avant que celui-ci l’atteigne. Le piéton peut en plus s’aider du feu perpendiculaire, qui devrait clignoter en orange si le croisement va bientôt basculer de sens. J’ai utilisé 2 instances de cet algorithme: 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 sacrifie, au plus, 10 et 5 secondes respectivement).
- On n’accepte de se taper un feu rouge que si l’on est significativement plus proche d’une rue terminale que d’une autre. Les 2 instances de l’algorithme utilisent également 2 réglages différents pour cela: une qui accepte de sacrifier du temps si on est 3 fois plus loin d’une rue terminale que d’une autre, et une qui accepte lorsqu’on est 4 fois plus loin.
- Les 2 instances sont nommées, dans les graphes ci-dessous, “Sacrifical 3/-10″ (3 fois plus loin, 10 secondes) et “Sacrificial 4/-5″ (4 fois plus loin, 5 secondes). Le premier algorithme est donc plus prompt à sacrifier du temps à un feu rouge que le deuxième.
D’abord, on constate que l’opportuniste malin est en fait moins efficace que l’opportuniste légèrement malin. Je pense que c’est tout simplement parce qu’on fait l’erreur de troquer un “gain certain” (un feu vert) pour un “gain hypothétiquement plus grand” (ignorer le feu vert et aller à une autre intersection pour se rapprocher de la rue terminale la plus lointaine, mais s’exposer à la possibilité d’avoir un feu rouge mal placé). Cette erreur est un phénomène assez classique de psychologie humaine, et est bien souvent peu bénéfique, comme on peut le voir également dans des jeux comme “Deal Or No Deal”, connu pendant un temps dans l’hexagone sous le titre “A prendre ou a laisser”, alias “La Boiboite D’Arthur”.
L’algorithme sacrificiel, lui, permet de grapiller quelques secondes dans certains cas, notamment les cas où, justement, il y a peu de marge de manoeuvre dès le depart (trajets courts ou “étroits”), mais perd de son intérêt pour les voyages longs et “larges”. De plus, il est légèrement moins sûr que la plupart des autres algorithmes. N’oublions pas également que dans le monde réel l’évaluation de l’âge d’un feu rouge peut être gênée par divers phénomènes, tel que l’obstruction de la vue du piéton, par exemple, ce qui rend l’application de cet algorithme plus délicat.
Conclusion
Il me semble que l’algorithme opportuniste légèrement malin est le plus efficace, surtout si on le combine subtilement, ici et là, avec un peu d’algorithme sacrificiel, notamment quand on se retrouve à des distances trop inégales des deux rues terminales, et qu’on est relativement sûr de son évaluation de l’âge d’un feu rouge (la plupart du temps parce que le feu perpendiculaire clignote depuis plusieurs secondes). Enfin, lorsqu’on combine le tout avec une certaine connaissance du quartier, on peut faire des trajets sans aucun temps d’attente à aucun feu rouge dans la majorité des cas!
Si vous avez repéré des erreurs, ou que vous avez des suggestions, n’hésitez pas à poster un commentaire. Et pour ceux qui vont inévitablement me dire que c’est beaucoup s’embêter pour économiser 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 comprendre qu’être ingénieur c’est plus qu’une formation, un métier, une passion… c’est un véritable mode vie! La quête du savoir! La soif d’optimisation! La joie de gaspiller du temps et de l’argent à travailler sur des choses inutiles! Sans oublier la compulsion à acheter plein de gadgets hors de prix, et le plaisir de chauffer son appartement uniquement avec leur effet Joule! Rah la la, vous savez pas ce que vous ratez les gars.
