- La operación de elevadores no es solo responder llamadas, sino un problema de optimización de asignación que considera al mismo tiempo la cantidad de cabinas, el flujo de pasajeros, la carga y la dirección de movimiento
- SCAN para una sola cabina cambia de dirección en el piso más alto, pero LOOK regresa desde el piso más alto donde realmente hay una solicitud, por lo que se parece más a la operación que la gente suele esperar
- RSR (Relative System Response), que maneja varias cabinas, puntúa factores como el tiempo estimado de llegada y la carga, y vuelve a optimizar la asignación cada 5 segundos, por lo que puede reasignar a otra cabina a los pasajeros de una cabina retrasada
- Si las cabinas van siempre llenas o hay tanto flujo de pasajeros y tan pocas cabinas que se detienen en cada piso, LOOK puede ser mejor que un RSR complejo
- La asignación por destino (Destination Dispatch), donde se ingresa el piso de destino por adelantado, obtiene más información, pero como es difícil cambiar la cabina asignada, salvo en algunos casos como rascacielos con 8 o más cabinas, por lo general produce tiempos de espera más largos que los botones tradicionales de subir y bajar
En una sola cabina, ¿dónde cambia de dirección?
- SCAN, patentado en 1961, sale del lobby, sube hasta el piso más alto y luego cambia de dirección para bajar, recogiendo y dejando pasajeros en su trayectoria
- LOOK no sube obligatoriamente hasta el último piso, sino que opera solo hasta el piso solicitado más alto y luego regresa
- En general, la forma de operación de los elevadores que la gente conoce y espera se parece más a LOOK
Asignación básica con varias cabinas
- Si hay varios elevadores, hay que decidir qué cabina atiende cada llamada
- En un sistema básico, un scheduler central asigna las paradas de cada cabina y asigna las nuevas llamadas a la cabina más cercana
- Pero una asignación basada solo en distancia refleja mal situaciones como una cabina cercana que ya va llena
Cómo evaluar el tiempo de espera
- La métrica más intuitiva para evaluar algoritmos de elevadores es el tiempo de espera desde la llamada hasta la llegada de la cabina
- De forma simple, se puede medir la proporción de veces que la cabina llegó en 30 o 90 segundos
- Para una evaluación más rigurosa, se reúnen los tiempos de espera de miles de recorridos y se revisan la distribución y el histograma
- Si el p90 es de 2 minutos, significa que el 90% de los pasajeros esperó 2 minutos o menos
- Si el p50 es de 1 minuto, en la mitad de las llamadas la cabina llegó en 1 minuto o menos
- Los pasajeros tienden a recordar con más fuerza los casos de p90, donde esperaron inusualmente mucho, más que el tiempo promedio
Cómo cambia el flujo de pasajeros según la hora
- En la mañana, en un gran edificio de oficinas, la mayoría de los desplazamientos van del lobby hacia los pisos superiores
- En la tarde-noche, por la salida del trabajo, predomina el flujo que baja desde los pisos altos
- A la hora de comida se mezclan viajes de subida y bajada, y el resto del tiempo abundan los desplazamientos entre pisos
- La distribución del tiempo de espera cambia mucho según la hora y el patrón de tráfico, y en especial las estadísticas de la hora pico de entrada por la mañana son malas
¿Qué cabina elige RSR?
- RSR (Relative System Response) de Otis puntúa qué tan adecuada es cada cabina para recoger pasajeros, y cuanto menor el puntaje, más adecuada es
- El puntaje de recogida se calcula combinando varios factores
- Tiempo estimado de llegada al piso de la llamada
- Penalización de carga según la cantidad de pasajeros a bordo
- Penalización para evitar agrupamiento cuando ya hay una cabina yendo al mismo piso en la misma dirección
- Bono por coincidencia de dirección de movimiento
- Bono para cabinas inactivas que estén a no más de dos pisos del piso de la llamada
- Bono por baja carga
- La prevención de agrupamiento (anti-bunching) inhibe asignaciones adicionales si otra cabina ya se dirige al mismo piso en la misma dirección
- RSR vuelve a optimizar toda la asignación cada 5 segundos
- Si la cabina A se retrasa, los pasajeros que originalmente iba a recoger A pueden reasignarse a la cabina B
- Esta reoptimización continua es la clave para suavizar el flujo de pasajeros
Diferencia de rendimiento entre LOOK y RSR
- Con herramientas de análisis de tiempo de espera se puede comparar entre LOOK y RSR la proporción de llegadas dentro de 30 y 90 segundos
- A medida que aumenta el flujo de pasajeros, LOOK empieza a superar a RSR
- Si las cabinas siempre van llenas y paran en todos los pisos, el efecto de las reglas adicionales de RSR se reduce
- En edificios pequeños con pocas cabinas por grupo, LOOK también tiende a rendir mejor que RSR, por lo que un método simple puede ser más adecuado
- Además del tiempo de espera, también se puede medir el tiempo de viaje desde que el pasajero sube hasta llegar a su piso de destino
- LOOK y RSR muestran características distintas también en esta métrica, pero aquí no se entra en una comparación detallada
Por qué la asignación por destino sale perdiendo pese a tener más información
- La asignación por destino funciona haciendo que el pasajero ingrese primero su piso de destino en un kiosco de cada piso, y entonces se le asigna qué elevador abordar
- Aunque el sistema de optimización puede conocer todos los destinos antes de que llegue la cabina, el tiempo de espera normalmente es mayor que con el método tradicional de botones de subir y bajar
- Hay excepciones en las que el sistema con kiosco resulta ventajoso, como edificios muy altos donde hay 8 o más cabinas por grupo
- La causa principal de la caída de rendimiento es la rigidez de la asignación
- En el método tradicional, cada 5 segundos se pueden volver a optimizar la ruta de las cabinas y la asignación de pasajeros
- En la asignación por destino, el pasajero debe subir a la cabina que se le asignó al principio
- Aunque la situación operativa cambie 30 segundos después de la llamada, no se puede cambiar con flexibilidad la cabina asignada
- La pérdida de flexibilidad de reasignación pesa más que la ventaja de tener la información extra del destino
Parámetros y alcance de la simulación
- En la simulación completa se pueden ajustar la cantidad de pisos, la cantidad de cabinas y el flujo de pasajeros por minuto, y revisar la proporción de llegadas dentro de 30 y 90 segundos
- Los algoritmos reales de elevadores consideran muchos más factores, y lo que se trata aquí es solo una parte del panorama completo
- La entrada de los botones de llamada sí se transmite, pero como el elevador calcula al mismo tiempo varias condiciones operativas, puede que no llegue de inmediato
1 comentarios
Comentarios en Hacker News
Durante aproximadamente la mitad del último medio siglo, los elevadores se controlaban solo con relevadores y sin computadoras, y este tipo de algoritmos también se implementaba con lógica cableada
Se pueden ver detalles interesantes, como diagramas de circuitos, en patentes antiguas de Otis
En una clase de ciencias de la computación de preparatoria implementé varias simulaciones de algoritmos de elevadores como proyecto personal
Los discos duros giratorios se parecen a un elevador muy largo envuelto alrededor de un eje en vez de ir en vertical, y SCAN es de hecho un algoritmo de planificación de discos: https://en.wikipedia.org/wiki/Elevator_algorithm
Me pregunto si el resultado de que la asignación por destino es mala en general se debe a que los pisos de destino se fijaron al azar
En edificios reales, la mayoría de la gente va a la planta baja en vez de a un piso cualquiera, y desde la planta baja, las personas que trabajan en el mismo piso tienden a salir juntas a la hora del almuerzo y regresar juntas al mismo piso. La asignación por destino puede agrupar a grandes grupos con el mismo destino, así que favorece este tipo de patrones
El sistema tipo kiosco de algunos hoteles incluso cambia la interfaz de usuario según la hora pico del desayuno
El efecto de agrupamiento de la gente que va a comer o regresa también existe en la práctica, y se nota más al mediodía que por la mañana o por la noche
También hay artículos que dicen que, después de que oficinas u hoteles cambiaron a este sistema, los tiempos de espera se redujeron mucho
Un edificio nuevo que visité recientemente también usaba este sistema. En la universidad, un roommate que estudiaba ingeniería eléctrica conectó botones de llamada, motores y un disco transparente con rectángulos negros para detectar posición a una protoboard e hizo un circuito de elevador; probablemente era un algoritmo simple
Si es tu primera vez viendo planificación de elevadores, recomiendo este juego: https://play.elevatorsaga.com/
Mientras desarrollaba Sky Lobby, un juego de control y automatización de elevadores para iOS y Android, pensé mucho en este problema
Adopté un algoritmo parecido a LOOK, que era el más cercano a lo que los jugadores esperaban del movimiento, pero cuando la elección era ambigua daba prioridad a los pisos que llevaban más tiempo esperando para mejorar el p90, que era importante en el juego. Pero si además metes elevadores de dos pisos que atienden dos niveles a la vez, pisos de transferencia entre cubos y cubos exprés, deja de estar claro cuál es el algoritmo óptimo o incluso el más intuitivo. Como era un juego y no un sistema real, encontré una heurística suficientemente buena y, cuando no les gustaba, permití que los jugadores sobrescribieran manualmente el plan de operación, y con eso la mayoría quedó satisfecha
Cada vez que espero un elevador pienso en lo complicado que debe ser crear un algoritmo que minimice el tiempo de espera hasta que el pasajero sube y llega a su destino
A veces hasta pienso que quienes implementaron esto quizá sean sádicos malvados que te hacen esperar más a propósito
La mañana después de una gran conferencia, todos querían bajar, pero un elevador lleno se detenía religiosamente en todos los pisos. Si un elevador para 10 personas ya recogió a los pasajeros que llamaron desde 10 pisos, debería poder ir directo a la planta baja y ahorrar 5 minutos, en vez de repetir en cada piso “ya no hay espacio, me espero al siguiente”. Sobre todo si en el segundo piso hay una persona con movilidad reducida que necesita tomar un vuelo, esto puede ser un problema serio
Cuando ves la posición y el movimiento de todos los elevadores, el programa está sorprendentemente apretado. Desde el lobby la espera se siente eterna, pero desde la perspectiva de la asignación la actividad es constante, y durante el horario de uso del edificio los elevadores casi nunca están inactivos. Solo mirar el panel de estado ya es interesante. Además, cuando un técnico de elevadores te dice “veámonos temprano en la mañana”, normalmente quiere decir como a las 4 a. m., porque intentan terminar el trabajo antes de que llegue la gente
Los elevadores son caros y los dueños de edificios no suelen sobredimensionar por impulso, así que normalmente instalan solo la cantidad mínima de elevadores necesaria para manejar la demanda esperada, y a veces incluso menos
Encima de cada uno de los 4 elevadores se muestran los pisos donde se detendrán, y mientras esperas también cambian la asignación entre elevador y piso y lo anuncian con sonido. Parece una función diseñada para permitir una asignación óptima
Más que el algoritmo, el mayor problema en los elevadores es la gente que no entiende el concepto de presionar el botón de subir o bajar según la dirección a la que va
Si oprimen ambos botones porque “así llega más rápido”, la mitad de las veces primero irá en la dirección contraria y además añade paradas innecesarias para quienes ya van dentro
Probablemente sea algo parecido a la psicología de las barras de carga falsas. Esperar sin saber cuándo llegará es aburrido y desesperante, pero si subes a un elevador aunque vaya en la dirección contraria, sientes que al menos ya estás avanzando. Aunque al final tome más tiempo, estar en un estado donde pasa algo se siente menos frustrante
En cambio, si la demanda para subir es baja, subir primero y luego dar toda la vuelta puede ser una estrategia más racional que esperar con la esperanza de que se desocupe un espacio
En ese caso, presionar tanto subir como bajar no es una tontería, sino algo lógico
Independientemente del rendimiento del algoritmo, también importa la psicología con la que la gente percibe el tiempo de espera
Esperar sin hacer nada es muy irritante, pero si haces algo durante ese mismo tiempo lo sientes como progreso y te molesta menos. En aeropuertos también hubo un caso donde, en vez de hacer que los pasajeros fueran directo de la puerta a la banda de equipaje y esperaran ahí hasta que saliera la primera maleta, diseñaron a propósito un recorrido más largo y con desvíos; aunque el tiempo total era el mismo, la satisfacción fue mayor
En muchos algoritmos de elevadores no se suele discutir el desgaste total y el costo de mantenimiento
Más movimiento puede acelerar los cambios de aceite hidráulico y las fallas de piezas. Los algoritmos eficientes a veces también hacen reposicionamiento preventivo según la hora o la ubicación de otros elevadores; por ejemplo, cuando uno baja, pueden mandar otro hacia arriba. Los algoritmos basados en señales de demanda minimizan este tipo de movimientos. Es importante el equilibrio entre aumentar el tiempo de espera y reducir el mantenimiento, y es probable que el dueño del edificio, que es quien paga, no valore el tiempo de espera de los pasajeros en la misma medida