Vous appuyez sur le bouton de l’ascenseur et vous regardez les numéros d’étage défiler un par un. Vous pensez peut-être qu’il s’agit d’une question de poisse – en réalité, vous faites face à un problème d’optimisation mathématique étudié par les chercheurs depuis plus d’un siècle.
Hier (1er août), une explication interactive des algorithmes d’ascenseurs créée par le développeur web John Allsopp s’est hissée au sommet de Hacker News et continue d’alimenter les discussions aujourd’hui sur Lobsters (52 points, 6 commentaires). Sans révéler de grande actualité fracassante, l’article transforme la logique complexe de répartition des ascenseurs en un simulateur interactif manipulable. Son succès vient du fait qu’il répond à une question que tout le monde s’est posée dans un hall : Quand j’appuie sur le bouton, l’ascenseur m’a-t-il vraiment entendu ?
Oui, il vous a entendu. C’est simplement qu’il a énormément de choses à gérer.
Ce que les ascenseurs optimisent : pourquoi les moyennes sont trompeuses
Posons-nous d’abord une question fondamentale : comment évaluer si un algorithme d’ascenseur est performant ?
La réponse intuitive est « le temps d’attente moyen ». Pourtant, lorsque l’on trace la distribution des temps d’attente sur des milliers de trajets simulés, les moyennes se révèlent profondément trompeuses. La simulation de John met en avant deux chiffres clés : un temps p50 de 1 minute (ce qui signifie que la moitié des personnes embarquent en moins d’une minute) et un temps p90 de 2 minutes (soit 90 % des utilisateurs qui n’attendent pas plus de deux minutes).
Cette minute d’écart entre p50 et p90 contient le grand secret de l’industrie des ascenseurs : le cerveau humain ne retient pas les moyennes, il ne se souvient que du pire cas. Ces 10 % d’attentes interminables occupent dans notre mémoire une place sans commune mesure avec leur réalité statistique. La sensation que « l’ascenseur n’arrive jamais » est donc en grande partie une illusion produite conjointement par les distributions statistiques et nos biais cognitifs. En réalité, dans la moitié des cas, l’ascenseur arrive en moins d’une minute.
Les compromis d’ingénierie sont tout aussi complexes : le temps d’attente moyen, l’attente maximale et la consommation d’énergie s’opposent directement. Envoyer les ascenseurs chercher uniquement le passager le plus proche réduit le temps moyen, mais dans des cas extrêmes, un utilisateur à un autre étage peut attendre jusqu’à 5 minutes. Sacrifier un peu de la moyenne pour éliminer les valeurs extrêmes « d’attente infinie » est le choix pragmatique fait par la plupart des tours de bureaux. Il n’y a pas de repas gratuit : les constructeurs choisissent simplement une grille de compromis à laquelle on pense rarement.
Fig. : Démonstration de la distribution du temps d’attente tracée à partir de milliers de simulations dans l’article original. Source : john.fun
La règle la plus ancienne : aller jusqu’au bout, puis faire demi-tour
Avant que les algorithmes ne prennent le relais, il y avait un humain dans l’ascenseur. Le métier de machiniste d’ascenseur était très courant jusqu’au milieu du XXe siècle : ouvrir les portes, demander l’étage souhaité et piloter manuellement la cabine vers sa destination. Lors de l’automatisation, le machiniste a disparu, les règles ont été confiées aux machines et le problème de répartition est passé de l’humain aux mathématiques.
Les premières règles automatisées étaient d’une simplicité désarmante. Breveté en 1961, l’algorithme SCAN prévoit que l’ascenseur parte du hall, monte continuellement en prenant et déposant des passagers sur son chemin jusqu’au dernier étage, puis fasse demi-tour vers le bas, répétant ce cycle indéfiniment. Plus tard, des ingénieurs ont réalisé qu’il était inutile de monter jusqu’en haut si plus personne ne le demandait, d’où l’apparition de la version améliorée LOOK : la cabine ne monte que jusqu’à l’étage le plus élevé demandé avant de repartir dans l’autre sens. Aujourd’hui, la plupart des gens considèrent ce comportement comme allant de soi, sans réaliser qu’il s’agit d’un algorithme formel.
Cette logique possède d’ailleurs un cousin célèbre en informatique : l’ordonnancement des têtes de lecture de disques durs mécaniques. Lorsqu’une tête de disque cherche des données sur des plateaux magnétiques, elle se déplace exactement selon le même schéma. L’informatique a directement repris ce terme en l’appelant « Algorithme de l’ascenseur » (Elevator Algorithm). Un brevet vieux de plus de 60 ans fonctionne ainsi encore aujourd’hui dans votre disque dur comme dans les cages d’ascenseur de votre immeuble – prouvant que les règles simples survivent souvent à la majorité des logiciels modernes.
Cependant, les règles pour un seul ascenseur s’effondrent lors des heures de pointe du matin. Imaginez un immeuble de bureaux à 9h00 : des centaines d’employés appuient simultanément sur le bouton de montée dans le hall. Si un système naïf envoyait toutes les cabines dans le hall, trois ascenseurs ouvriraient leurs portes en même temps et remonteraient à moitié vides ensemble. L’ordonnanceur doit donc effectuer des actions en apparence illogiques : dévier une cabine vide pour aller chercher des passagers à un autre étage. Si vous attendez au 15e étage et qu’un ascenseur passe devant vous sans s’arrêter, il n’a pas ignoré votre appel : il exécute simplement un plan d’optimisation globale qui le dépasse.
Fig. : Démonstration interactive sur la page d’accueil — un ascenseur faisant des allers-retours dans un immeuble de 4 étages, visionnable en vitesse 25x. Source : john.fun
La coordination multi-ascenseurs : réévaluation toutes les 5 secondes
Quand plusieurs ascenseurs fonctionnent en parallèle, le problème devient exponentiellement plus complexe : qui doit chercher qui ?
Les systèmes modernes de contrôle de groupe (comme l’algorithme RSR d’Otis) utilisent un système de notation dynamique. Chaque ascenseur se voit attribuer en continu un score d’attribution calculé selon le temps d’arrivée estimé, la charge actuelle, la proximité avec d’autres cabines, le sens de déplacement et la disponibilité aux alentours. L’ascenseur avec le coût le plus faible reçoit la course. La subtilité de ce système réside dans sa capacité de rétractation : toutes les 5 secondes, l’algorithme réévalue l’ensemble du bâtiment. Si l’ascenseur qui vous a été attribué est bloqué par des portes retenues, votre demande peut être automatiquement transférée à une autre cabine.
La simulation de John révèle une conclusion contre-intuitive : en cas de trafic extrêmement dense, la règle classique et simple LOOK commence en réalité à surpasser des algorithmes complexes comme RSR. Dans les petits bâtiments avec peu de cabines, les règles simples s’imposent également. « Parfois, rester simple est la meilleure option » – cette vérité toute simple est l’une des leçons les plus précieuses de toute l’analyse.
La sélection de destination : plus d’informations, mais plus lent ?
Ces dernières années, les immeubles de bureaux haut de gamme ont popularisé la sélection de destination (Destination Dispatch) : avant d’entrer dans la zone des ascenseurs, les passagers choisissent leur étage sur un écran tactile dans le hall, qui leur indique « Veuillez attendre l’ascenseur 3 ». Cela semble plus intelligent : si le système connaît la destination de chacun à l’avance, il devrait théoriquement mieux organiser les trajets ?
Les résultats de la simulation ont montré exactement l’inverse : dans la grande majorité des scénarios, le temps d’attente moyen de ce système est pire que celui des boutons « haut/bas » traditionnels. Le seul cas de figure où la sélection de destination l’emporte concerne les gratte-ciels très hauts équipés d’au moins 8 ascenseurs en groupe. La raison ? La flexibilité de réoptimiser toutes les 5 secondes est verrouillée dès l’instant où l’écran vous ordonne d’attendre une cabine précise. 30 secondes après votre choix sur l’écran, la situation globale de l’immeuble a pu changer, mais le système ne peut plus revenir sur sa décision.
Des ingénieurs sur Lobsters ont apporté des retours du monde réel. L’utilisateur vbernat note que la sélection de destination suppose que chaque utilisateur indique sagement son étage sur l’écran. Or, des personnes impatientes réappuient fréquemment sur l’écran, entraînant la venue de deux cabines distinctes pour le même étage. mitsuhiko (créateur du framework Flask) ajoute qu’en pratique, se tromper d’ascenseur ou rater sa cabine est très courant. Certains soulignent néanmoins une bonne expérience lorsqu’il est couplé à un badge d’accès : le passage du badge attribue instantanément une cabine, ce qui fluidifie la pointe du matin. Mais le prix à payer est souvent une attente de plusieurs minutes pour descendre le soir, le système ayant concentré toutes ses ressources sur la pointe matinale des bureaux.
Un point mérite réflexion : donner plus d’informations à un système ne garantit pas qu’il saura bien les exploiter. L’optimum global du système entre fréquemment en conflit direct avec le désir individuel que « l’ascenseur vienne d’abord à mon étage ». Dans les comptes de l’ordonnanceur, votre minute personnelle et la somme des minutes de centaines d’occupants ne représentent pas la même valeur.
Pourquoi l’attente semble toujours si longue : la psychologie de l’attente
Terminons par un élément de psychologie : les fabricants d’ascenseurs étudient depuis longtemps « l’attente perçue ». La psychologie montre que plus une personne s’ennuie en attendant, plus le temps semble passer lentement. Une astuce architecturale classique a consisté à installer de grands miroirs près des portes d’ascenseur – une idée adoptée avec succès par de nombreux gestionnaires d’immeubles. Votre impatience en attendant l’ascenseur provient pour moitié de l’algorithme, et pour l’autre moitié de votre propre cerveau.
Un autre phénomène demeure mystérieux : puisque les ascenseurs effectuent autant de trajets vers le haut que vers le bas, pourquoi a-t-on toujours l’impression qu’ils vont dans le sens inverse ? Une partie de la réponse réside dans les heures de pointe : les ascenseurs bondés dépassent les étages intmédiaires sans s’arrêter une fois leur capacité maximale atteinte. Notre mémoire ne conserve de manière sélective que les souvenirs de ces cabines pleines passant devant nous à toute vitesse.
Revenons à la question initiale : l’ascenseur a-t-il entendu votre bouton ? Oui, il l’a entendu. Il est simplement occupé à réévaluer toutes les 5 secondes des centaines de destinations, de capacités, de dépenses énergétiques et de critères d’équité. La prochaine fois que vous attendez un ascenseur et qu’il part ailleurs d’abord, voyez-le comme un gestionnaire effectuant une optimisaton globale : sur son registre, il équilibre votre minute individuelle avec le temps collectif de tout l’immeuble.
Liens de référence :
- John Allsopp : Elevators (Guide interactif)
- Discussion sur Lobsters (s/jxqf1w/elevators)
- Wikipédia : Elevator algorithm
- Signal v. Noise : Defining the problem of elevator waiting times
- Scientific American : The reason why elevators feel slow
