- Le fonctionnement d’un ascenseur n’est pas une simple réponse à un appel, mais un problème d’optimisation d’affectation qui doit prendre en compte à la fois le nombre de cabines, le flux de passagers, la charge et le sens de déplacement
- Pour une seule cabine, SCAN inverse son sens au dernier étage, tandis que LOOK fait demi-tour au plus haut étage où il existe réellement une demande, ce qui se rapproche davantage du fonctionnement généralement attendu
- Pour plusieurs cabines, RSR (Relative System Response) attribue un score en fonction du temps d’arrivée estimé, de la charge, etc., puis réoptimise l’affectation toutes les 5 secondes afin de pouvoir réaffecter à une autre cabine les passagers d’une cabine retardée
- Si les cabines sont en permanence pleines, ou si le flux de passagers est si élevé et le nombre de cabines si faible qu’elles s’arrêtent à presque tous les étages, un LOOK simple peut être meilleur qu’un RSR plus complexe
- La destination dispatch, où l’on saisit à l’avance l’étage de destination, fournit davantage d’informations, mais rend le changement de cabine attribuée plus difficile ; sauf dans certains cas comme les très hauts immeubles ou les groupes de 8 cabines ou plus, elle entraîne en général un temps d’attente plus long que les boutons traditionnels montée/descente
Où une cabine unique change-t-elle de direction ?
- SCAN, breveté en 1961, part du hall, monte jusqu’au dernier étage, puis redescend en prenant et déposant les passagers sur son trajet
- LOOK ne va pas systématiquement jusqu’au dernier étage : il ne monte que jusqu’au plus haut étage demandé, puis repart dans l’autre sens
- Le mode de fonctionnement des ascenseurs que les gens connaissent et attendent en général ressemble davantage à LOOK
Affectation de base avec plusieurs cabines
- Lorsqu’il y a plusieurs ascenseurs, il faut décider quelle cabine prend en charge quel appel
- Dans un système de base, un ordonnanceur central attribue à chaque cabine ses étages d’arrêt et affecte chaque nouvel appel à la cabine la plus proche
- Mais une affectation basée uniquement sur la distance reflète mal des situations comme celle d’une cabine proche déjà pleine
Comment évaluer le temps d’attente
- Le critère d’évaluation le plus intuitif d’un algorithme d’ascenseur est le temps d’attente entre l’appel et l’arrivée de la cabine
- Dans une approche simple, on peut mesurer la proportion de cabines arrivées en 30 secondes ou en 90 secondes
- Pour une évaluation plus rigoureuse, on agrège les temps d’attente sur plusieurs milliers de trajets afin d’examiner la distribution et l’histogramme
- Si le p90 est de 2 minutes, cela signifie que 90 % des passagers ont attendu moins de 2 minutes
- Si le p50 est de 1 minute, cela signifie que pour la moitié des appels, une cabine est arrivée en moins d’1 minute
- Les passagers ont tendance à mieux se souvenir des cas de p90, où l’attente a été exceptionnellement longue, que du temps d’attente moyen
Des flux de passagers qui changent selon l’heure
- Le matin, dans les grands immeubles de bureaux, la majorité des déplacements se fait du hall vers les étages supérieurs
- Le soir, avec les départs, le flux descendant depuis les étages supérieurs devient dominant
- À l’heure du déjeuner, les flux montants et descendants se mélangent, et le reste du temps, les déplacements entre étages sont plus fréquents
- La distribution des temps d’attente varie fortement selon l’heure et le schéma de trafic, et les statistiques sont particulièrement mauvaises pendant la pointe du matin
Comment RSR choisit une cabine
- Le RSR (Relative System Response) d’Otis attribue un score à l’aptitude de chaque cabine à prendre en charge un passager, et plus le score est bas, plus la cabine est adaptée
- Le score d’embarquement est calculé en combinant plusieurs facteurs
- le temps d’arrivée estimé à l’étage de l’appel
- une pénalité de charge selon le nombre de passagers déjà à bord
- une pénalité anti-regroupement lorsqu’une autre cabine se dirige déjà vers le même étage dans la même direction
- un bonus de concordance de direction
- un bonus pour les cabines inactives situées à moins de deux étages de l’étage d’appel
- un bonus de faible charge
- L’anti-regroupement (anti-bunching) évite d’ajouter une affectation supplémentaire si une autre cabine se dirige déjà vers le même étage dans la même direction
- RSR réoptimise l’ensemble de l’affectation toutes les 5 secondes
- si la cabine A est retardée, les passagers qu’elle devait prendre peuvent être réaffectés à la cabine B
- cette réoptimisation continue est essentielle pour fluidifier le flux de passagers
Différences de performance entre LOOK et RSR
- Avec des outils d’analyse du temps d’attente, on peut comparer LOOK et RSR sur la proportion d’arrivées en moins de 30 ou 90 secondes
- Plus le flux de passagers augmente, plus LOOK commence à dépasser RSR
- si les cabines sont toujours pleines et s’arrêtent à tous les étages, l’effet des règles supplémentaires de RSR diminue
- Dans les petits immeubles avec peu d’ascenseurs par groupe, LOOK tend aussi à mieux fonctionner que RSR, ce qui suggère qu’une approche simple peut être plus adaptée
- Au-delà du temps d’attente, on peut aussi mesurer le temps de trajet entre l’embarquement et l’arrivée à destination
- LOOK et RSR présentent aussi des caractéristiques différentes sur cet indicateur, mais la comparaison détaillée n’est pas abordée ici
Pourquoi la destination dispatch reste désavantagée malgré plus d’informations
- La destination dispatch consiste à saisir d’abord l’étage de destination sur une borne à chaque étage, qui indique ensuite quel ascenseur prendre
- Le système d’optimisation connaît alors à l’avance la destination de chaque passager avant l’arrivée de la cabine, mais le temps d’attente devient généralement plus long que dans le système traditionnel à boutons montée/descente
- Il existe des exceptions où le système par borne est avantageux, par exemple dans les immeubles très hauts avec 8 ascenseurs ou plus par groupe
- La principale cause de cette baisse de performance est la rigidité de l’affectation
- dans le système traditionnel, il est possible de réoptimiser toutes les 5 secondes les trajets des cabines et l’affectation des passagers
- avec la destination dispatch, les passagers doivent monter dans la cabine qui leur a été attribuée au départ
- même si la situation d’exploitation change 30 secondes après l’appel, il est difficile de changer de cabine attribuée avec souplesse
- Le coût de la perte de flexibilité de réaffectation est plus important que le bénéfice des informations supplémentaires sur la destination
Paramètres ajustables et portée de la simulation
- Dans la simulation complète, on peut ajuster le nombre d’étages, le nombre de cabines et le flux de passagers par minute, puis observer la proportion d’arrivées en moins de 30 ou 90 secondes
- Les algorithmes d’ascenseur réels prennent en compte davantage d’éléments, et le périmètre traité ici ne couvre qu’une partie du sujet
- Les appels sur les boutons sont bien transmis, mais comme l’ascenseur calcule plusieurs conditions d’exploitation en même temps, il peut ne pas arriver immédiatement
1 commentaires
Avis sur Hacker News
Pendant environ la moitié du dernier demi-siècle, les ascenseurs ont été contrôlés uniquement par des relais, sans ordinateur, et ce type d’algorithme était lui aussi implémenté sous forme de circuits logiques câblés.
On trouve des détails intéressants, comme les schémas, dans d’anciens brevets d’Otis.
En cours d’informatique au lycée, j’avais implémenté plusieurs simulations d’algorithmes d’ascenseur comme projet personnel.
Un disque dur rotatif ressemble à un très long ascenseur enroulé autour d’une broche plutôt que vertical, et SCAN est effectivement un algorithme d’ordonnancement de disque : https://en.wikipedia.org/wiki/Elevator_algorithm
Je me demande si le résultat selon lequel la répartition par réservation de destination est globalement mauvaise vient du fait que les étages de destination ont été définis aléatoirement.
Dans un vrai bâtiment, la plupart des gens qui ne sont pas au rez-de-chaussée vont au rez-de-chaussée, et au rez-de-chaussée, les personnes qui travaillent au même étage ont tendance à sortir ensemble à l’heure du déjeuner puis à revenir ensemble au même étage. La répartition par réservation de destination est adaptée à ce type de schéma, car elle peut regrouper de grands groupes allant vers la même destination.
Dans certains hôtels, les systèmes à kiosque modifient aussi leur interface utilisateur selon l’affluence au petit-déjeuner.
L’effet de regroupement des personnes qui partent déjeuner ou en reviennent existe aussi réellement, et il est plus marqué en milieu de journée que le matin ou le soir.
Il existe aussi des articles indiquant que des bureaux ou des hôtels ayant adopté ce système ont vu leurs temps d’attente fortement diminuer.
Un immeuble neuf que j’ai visité récemment utilisait aussi ce système. À l’université, mon colocataire en génie électrique avait construit un circuit d’ascenseur sur breadboard avec des boutons d’appel, un moteur et un disque transparent marqué de carrés noirs pour la détection de position ; l’algorithme était probablement simple.
Si vous découvrez l’ordonnancement des ascenseurs, je recommande ce jeu : https://play.elevatorsaga.com/
J’ai beaucoup réfléchi à ce problème en développant Sky Lobby, un jeu de contrôle et d’automatisation d’ascenseurs pour iOS et Android.
Nous avons adopté un algorithme proche de LOOK, qui correspond le mieux aux mouvements attendus par les joueurs, tout en donnant la priorité aux étages qui attendaient depuis longtemps lorsque le choix était ambigu, afin d’améliorer le p90, important dans le jeu. Mais si l’on ajoute des ascenseurs à deux niveaux desservant deux étages à la fois, des étages de correspondance entre gaines et des gaines express, l’algorithme optimal ou le plus intuitif devient beaucoup moins évident. Comme il s’agissait d’un jeu et non d’un vrai système, nous avons trouvé des heuristiques suffisamment bonnes, et le fait de permettre aux joueurs de remplacer manuellement le plan de circulation lorsqu’il ne leur convenait pas a satisfait la plupart d’entre eux.
Chaque fois que j’attends un ascenseur, je pense à quel point il doit être pénible de concevoir un algorithme qui minimise le temps d’attente jusqu’à l’embarquement des passagers et leur arrivée à destination.
Parfois, je me demande même si ceux qui l’ont implémenté ne sont pas des sadiques malveillants qui nous font attendre plus longtemps exprès.
Le lendemain matin d’une grande conférence, tout le monde voulait descendre, mais une cabine pleine s’arrêtait scrupuleusement à chaque étage. Si un ascenseur de 10 personnes a déjà pris des passagers appelés depuis 10 étages, il devrait pouvoir aller directement au rez-de-chaussée et gagner 5 minutes, au lieu de répéter à chaque étage « il n’y a pas de place, je prendrai le suivant ». C’est particulièrement problématique si une personne à mobilité réduite au 2e étage doit prendre un avion.
Quand on voit la position et les mouvements de toutes les cabines, le planning est étonnamment dense. Dans le hall, l’attente semble interminable, mais du point de vue de la répartition, l’activité est continue, et pendant les heures d’utilisation du bâtiment, les ascenseurs ne restent presque jamais inactifs. Rien que regarder le panneau d’état est intéressant. Et quand un technicien d’ascenseurs dit « retrouvons-nous tôt le matin », cela veut généralement dire vers 4 h, afin de terminer avant l’arrivée des gens au travail.
Les ascenseurs coûtent cher et les propriétaires d’immeubles n’investissent pas impulsivement à l’excès ; ils installent donc généralement le nombre minimal d’ascenseurs permettant de répondre à la demande prévue, parfois même moins.
Au-dessus de chacun des quatre ascenseurs, les étages d’arrêt prévus sont affichés, et pendant l’attente, l’affectation entre ascenseurs et étages peut changer, avec une notification sonore. Cela semble être une fonction conçue pour permettre une répartition optimale.
Le plus gros problème avec les ascenseurs n’est pas l’algorithme, mais les gens qui ne comprennent pas le concept consistant à appuyer sur le bouton haut ou bas selon la direction de leur destination.
Quand ils appuient sur les deux boutons parce que « ça arrive plus vite », la moitié du temps ils partent d’abord dans la direction opposée, et ajoutent même des arrêts inutiles pour les personnes déjà à bord.
C’est probablement similaire à la psychologie des faux indicateurs de chargement. Attendre sans savoir quand cela arrivera est ennuyeux et frustrant, mais monter dans un ascenseur qui bouge, même dans la direction opposée, donne l’impression de progresser. Au final, même si cela prend plus de temps, le fait qu’il se passe quelque chose est moins frustrant.
En revanche, si la demande vers le haut est faible, il peut être rationnel de monter d’abord puis faire l’aller-retour complet, plutôt que d’attendre en espérant qu’une place se libère.
Dans ce cas, appuyer sur les boutons haut et bas n’est pas idiot, c’est logique.
Indépendamment des performances de l’algorithme, la psychologie de la perception du temps d’attente est aussi importante.
Attendre sans rien faire est très agaçant, mais faire quelque chose pendant le même laps de temps donne une impression de progression et réduit l’insatisfaction. On cite aussi le cas d’aéroports où, au lieu de laisser les passagers aller directement de la porte au tapis à bagages et attendre le premier bagage, on a volontairement créé un trajet plus long et détourné : même si la durée totale était la même, les passagers étaient plus satisfaits.
Dans les différents algorithmes d’ascenseurs, l’usure et les coûts de maintenance globaux sont rarement évoqués.
Davantage de mouvements peut accélérer le remplacement de l’huile hydraulique et les pannes de pièces. Les algorithmes efficaces peuvent aussi repositionner les cabines à l’avance selon l’heure ou la position des autres ascenseurs ; par exemple, si l’un descend, un autre peut être envoyé vers le haut. Les algorithmes fondés sur les signaux de demande minimisent ce type de mouvements. Il est important de trouver un équilibre qui réduit la maintenance même si cela augmente le temps d’attente, et il est possible que les propriétaires d’immeubles qui supportent ces coûts n’accordent pas autant d’importance au temps d’attente des passagers.