Hier, un article de vulgarisation interactive décortiquant le fonctionnement des ascenseurs s’est hissé en tête de Hacker News, la plus grande communauté de développeurs au monde, accumulant 771 points et 198 commentaires. Les ingénieurs y ont débattu toute la journée de la logique de planification des cabines.
Le point de départ de la discussion repose sur une observation contre-intuitive : dans de nombreux immeubles de bureaux récents, les boutons d’étage ont été retirés de l’intérieur des cabines et déplacés dans le hall d’entrée. L’usager sélectionne son étage de destination avant d’entrer et le système lui attribue une cabine précise. Pourtant, dans la plupart des scénarios simulés, ce système dit « à sélection de destination » (Destination Dispatch) s’avère plus lent que les boutons traditionnels Haut/Bas. La section des commentaires s’est rapidement remplie de témoignages d’ingénieurs en ascenseurs, de développeurs de pilotes de disque et de gestionnaires hôteliers.
L’ascenseur est un équipement que chacun utilise quotidiennement, mais dont bien peu soupçonnent la complexité sous-jacente. L’article original explicite ces mécanismes à l’aide de simulations interactives : chaque algorithme est accompagné d’une animation à vitesse réglable, permettant au lecteur d’ajouter des étages et des cabines pour observer en direct l’évolution de la distribution des temps d’attente. Nous en avons synthétisé ici les éléments clés.
Pourquoi l’ordonnancement d’ascenseurs est si complexe
Il faut d’abord prendre en compte les contraintes physiques. Une cabine d’ascenseur ne peut se déplacer que dans une seule direction à la fois ; sa capacité d’accueil est limitée ; et plus le nombre d’étages augmente, plus les combinaisons possibles se multiplient. Lorsque plusieurs cabines fonctionnent en parallèle, décider qui prendre en charge et dans quel ordre devient un problème d’ordonnancement complexe.
Le flux de voyageurs fait également preuve d’une forte dissymétrie. Lors du pic matinal dans un immeuble de bureaux, la quasi-totalité des usagers monte depuis le hall vers les étages supérieurs ; en fin de journée, le mouvement s’inverse ; le midi présente un flux mixte. Un même jeu de règles produit des performances radicalement différentes selon le moment de la journée. L’optimisation des temps d’attente au cours du rush du matin figure parmi les défis les plus ardus.
La gestion de groupe (Group Control) ajoute une difficulté supplémentaire : dans les immeubles tertiaires, une batterie de cinq ou six cabines partage généralement un panneau d’appel unique. Lorsqu’un usager appuie sur le bouton Haut, le système doit déterminer quelle cabine envoyer. Cette décision est recalculée en permanence au fil du déplacement des cabines, des entrées de passagers et des nouvelles requêtes. C’est là toute la difficulté : les règles pour une seule cabine sont simples, mais la coordination d’un groupe s’avère extrêmement complexe.
Comment fonctionnent les ascenseurs traditionnels
L’algorithme de base le plus répandu est nommé SCAN, breveté dès 1961. L’ascenseur monte du hall jusqu’au dernier étage, puis fait demi-tour pour redescendre, en s’arrêtant au passage pour prendre les personnes allant dans le même sens — à la manière d’un bus de ligne. Les informaticiens ont rapidement remarqué que les têtes de lecture/écriture des disques durs se déplaçaient exactement selon le même schéma, et ont emprunté l’expression « algorithme de l’ascenseur » (Elevator Algorithm).
Comme les usagers ont rarement tous besoin d’aller au dernier étage, une version améliorée appelée LOOK a vu le jour. Avec LOOK, la cabine ne monte que jusqu’à la requête la plus éloignée dans sa direction actuelle avant de faire demi-tour. C’est le comportement auquel la plupart d’entre nous sommes habitués : conserver sa direction, prendre les passagers sur le trajet et n’inverser le sens qu’en l’absence de requête supplémentaire en amont.
Figure : Démonstration de la simulation interactive de John.fun. Source : john.fun/elevators
Le critère d’évaluation d’un ascenseur reste le temps d’attente, analysé précisément à travers sa distribution statistique : p50 indique la durée d’attente pour la moitié des passagers, tandis que p90 définit le seuil pour 90 % d’entre eux. Personne ne se souvient du temps d’attente moyen ; ce qui marque les esprits, ce sont ces rares fois où l’on a eu l’impression d’attendre « une éternité ». L’optimisation des algorithmes vise donc en priorité à réduire la latence extrême du p90.
Figure : Démonstration de la distribution des temps d’attente sur John.fun. Source : john.fun/elevators
Il existe également un arbitrage fondamental : un temps d’attente court ne garantit pas un trajet rapide. Pour prendre davantage de personnes en chemin, l’ascenseur multiplie les arrêts, ce qui rallonge le temps passé dans la cabine. Réduire le temps d’attente se fait souvent au détriment de la durée du trajet, et l’algorithme d’ordonnancement doit constamment équilibrer ces deux facteurs.
Plus intelligent ne veut pas toujours dire meilleur
Pour gérer plusieurs cabines, l’approche la plus basique consiste en une centralisation simple : attribuer chaque nouvel appel à l’ascenseur le plus proche. Les ingénieurs ont toutefois cherché à aller plus loin. Otis a ainsi conçu l’algorithme RSR (Relative System Response), qui attribue un score dynamique à chaque cabine en fonction de son heure d’arrivée estimée, de sa charge actuelle, de la prévention du regroupement (anti-clustering), de l’alignement de direction et de la présence de véhicules vides à proximité. La cabine obtenant le meilleur score reçoit l’appel. Le système réévalue l’attribution toutes les 5 secondes ; si la cabine A prend du retard, la tâche peut être réattribuée à la cabine B.
RSR inclut une règle anti-regroupement : si une cabine fait déjà route vers un étage, une autre ne viendra pas doubler l’appel. Lorsque deux ascenseurs arrivent simultanément dans un hall et ouvrent leurs portes ensemble, c’est le signe d’un échec de cette règle. L’évaluation s’effectue en temps réel et évolue à chaque étage franchi par une cabine.
Pourtant, les résultats de la simulation se révèlent déconcertants : lorsque le trafic augmente, l’algorithme basique LOOK surpasse fréquemment le complexe RSR. Dans les petits immeubles ou avec peu de cabines, LOOK l’emporte également très souvent. Multiplier les règles ne garantit pas de meilleurs résultats ; la simplicité s’avère parfois préférable. C’est un rappel salutaire pour l’ingénierie : entre la complexité algorithmique et le gain réel de performance s’interpose la réalité du terrain.
Le débat sur les systèmes à sélection de destination
La logique des systèmes à sélection de destination (Destination Dispatch) semble lumineuse : sachant à l’avance où se rend chaque passager, le système regroupe les personnes allant au même étage dans une même cabine, réduisant ainsi le nombre d’arrêts intermédiaires. Disposant d’une information complète, l’efficacité théorique devrait être supérieure. Ces bornes interactives se multiplient dans les hôtels, hôpitaux et gratte-ciels.
Pourtant, la simulation présentée dans l’article aboutit à la conclusion inverse : dans la majorité des cas, la sélection de destination se montre plus lente que les traditionnels boutons Haut/Bas. La cause réside dans la perte de flexibilité. Les ascenseurs classiques peuvent réoptimiser leur itinéraire toutes les 5 secondes. À l’inverse, la sélection de destination verrouille l’usager dans une cabine donnée dès sa saisie sur la borne. Si les conditions de trafic évoluent 30 secondes plus tard, le système ne peut plus modifier l’affectation. Le gain apporté par l’information préalable ne compense pas la perte d’adaptabilité en temps réel.
Plusieurs ingénieurs ont apporté un bémol à ce constat dans les commentaires. Ils ont souligné que lors de la pause déjeuner dans les véritables immeubles de bureaux, une foule importante se dirige simultanément vers l’étage du restaurant — un scénario dans lequel la sélection de destination excelle grâce au traitement par lots (batching). De même, dans les hôtels, le trafic matinal bascule sur des modes dédiés au petit-déjeuner. N’ayant pas modélisé ces profils de trafic spécifiques, la simulation a naturellement favorisé les algorithmes anciens. Les deux analyses se tiennent : l’intérêt de la sélection de destination dépend entièrement du profil de trafic considéré. S’il demeure très prisé dans les bâtiments modernes, affirmer que « le plus récent est toujours le plus rapide » ne se vérifie pas systématiquement.
Figure : Démonstration du système à sélection de destination de John.fun. Source : john.fun/elevators
Un disque dur est un ascenseur enroulé sur lui-même
Un détail frappant relevé dans les commentaires a particulièrement retenu l’attention : l’algorithme SCAN est rigoureusement identique à celui utilisé pour l’ordonnancement des têtes de lecture des disques durs d’ordinateurs. Sur Wikipédia, l’article est d’ailleurs répertorié sous les deux intitulés : « Elevator algorithm » et « SCAN ». Il a été conçu à l’origine pour planifier les requêtes de lecture et d’écriture sur les disques magnétiques.
Dans un disque dur mécanique, la tête de lecture/écriture se déplace au-dessus des pistes du plateau tout comme une cabine d’ascenseur se déplace entre les étages pour transporter des passagers. Les requêtes de lecture et d’écriture étant réparties sur la surface du disque, la tête balaye dans une direction en traitant les demandes au passage, puis fait demi-tour une fois arrivée au bout. Le déplacement (seek) de la tête constitue l’une des opérations mécaniques les plus lentes de l’ordinateur, et le temps gagné par l’ordonnancement est précisément ce temps mécanique. Comme l’a résumé un développeur : « Un disque dur n’est rien d’autre qu’un ascenseur enroulé sur lui-même ».
Dans les manuels d’informatique, SCAN constitue le chapitre classique de l’ordonnancement des E/S disque. Le brevet d’ascenseur de 1961 et les cours de systèmes d’exploitation partagent exactement le même principe. Lorsque Donald Knuth étudiait les coroutines dans The Art of Computer Programming, son exemple de référence était la simulation d’un ascenseur. L’un transporte des personnes, l’autre des données, mais la logique de planification reste identique.
Cet algorithme s’efface aujourd’hui progressivement des disques durs avec l’avènement des SSD (Solid State Drives), dont le temps de recherche est quasi nul. Il continue en revanche de tourner chaque jour dans les cages d’ascenseurs du monde entier. Un même concept a ainsi traversé plus de soixante ans d’histoire à la croisée du génie mécanique et de l’informatique.
Conclusion
Quand votre ascenseur tarde à arriver, ce n’est pas qu’il vous ignore : il doit simplement jongler avec de très nombreuses variables. La prochaine fois que vous attendrez une cabine, rappelez-vous que derrière chaque pression sur un bouton, des générations d’ingénieurs ont débattu de la meilleure façon d’optimiser l’algorithme — et que certains de ces débats ne sont toujours pas tranchés.
Liens de référence :
- John.fun : Explication interactive sur les ascenseurs
- Discussion HN (item?id=49124218)
