⏱️ Lectura: 14 min
El problema de los algoritmos de ascensores tiene más de 60 años: la primera solución formal, SCAN, se patentó en 1961 y todavía es la base de buena parte de los sistemas que corren hoy en edificios de todo el mundo. Un artículo interactivo publicado en john.fun desarma paso a paso cómo funcionan estos algoritmos de ascensores, desde el más simple hasta el sistema propietario RSR de Otis, y deja un dato incómodo: los kioscos que te piden el piso de destino antes de subir suelen dar peores tiempos de espera que los botones de toda la vida.
📑 En este artículo
Para cualquier desarrollador que haya lidiado con balanceo de carga, colas de trabajos o schedulers de procesos, el problema es el mismo con otro disfraz: varios workers (las cabinas), una cola de solicitudes que llega en ráfagas desiguales y una métrica de éxito que no es el promedio, sino la cola de la distribución.
TL;DR
- El algoritmo SCAN se patentó en 1961 y todavía sirve de base a muchos sistemas de ascensores.
- LOOK, la variante más usada hoy, evita subir hasta el último piso si nadie lo pidió.
- El algoritmo RSR (Relative System Response) de Otis puntúa cada cabina y reasigna pasajeros cada 5 segundos.
- La métrica clave no es el promedio: es el p90, el tiempo que espera el 90% de los pasajeros.
- En flujos de tráfico altos, LOOK termina superando a RSR porque las cabinas van siempre llenas.
- Los kioscos de destino suelen dar peores tiempos de espera que los botones simples, salvo en edificios con 8 o más cabinas por núcleo.
- La hora de mayor congestión es la mañana, cuando casi todo el tráfico va del lobby a los pisos altos.
- RSR penaliza el amontonamiento de cabinas en la misma dirección y premia a las que están ociosas a menos de dos pisos del llamado.
Qué pasó
El artículo de john.fun no es un paper académico ni un anuncio de producto: es una simulación interactiva que deja mover los sliders de tráfico y ver, en tiempo real, cómo cambian los tiempos de espera según el algoritmo elegido. Compara cuatro enfoques: SCAN, LOOK, RSR (el algoritmo propietario de Otis) y destination dispatch, el sistema de kioscos que reemplaza los botones de subir y bajar por un teclado que pide el piso de destino.
La pieza usa dos métricas concretas para comparar estos algoritmos de ascensores: el porcentaje de viajes con espera menor a 30 segundos y el porcentaje con espera menor a 90 segundos. Con esas dos cifras alcanza para mostrar algo que la intuición no anticipa: el sistema más sofisticado (RSR) no siempre gana, y el kiosco de destino, que en papel tiene más información, tampoco.
Contexto e historia
El problema de los algoritmos de ascensores es viejo. La primera solución formal, SCAN, se patentó en 1961. La idea es simple: la cabina arranca en el lobby, sube hasta el último piso recogiendo y dejando gente en el camino, y recién ahí invierte el sentido y baja. Es fácil de implementar y predecible, pero tiene un defecto obvio: casi nunca hace falta llegar hasta el piso más alto.
La corrección a ese defecto se llama algoritmo LOOK: la cabina sube solo hasta el piso más alto que alguien pidió, no hasta el techo del edificio, y ahí invierte. Es el comportamiento que la mayoría de la gente da por sentado cuando piensa en cómo funciona un ascensor. Durante décadas, LOOK (o variantes cercanas) fue el estándar de facto en edificios con una sola cabina.
El problema se vuelve más interesante con varias cabinas. La solución más básica es un programador central que asigna cada llamado a la cabina más cercana. Funciona, pero deja margen de mejora: no considera si esa cabina ya va llena, si otra cabina va a pasar por el mismo piso en la misma dirección, o si conviene reservar una cabina ociosa cerca del llamado para la próxima solicitud.
Detalles técnicos y rendimiento de los algoritmos de ascensores
Acá es donde el algoritmo RSR de Otis mete la mano. RSR (Relative System Response) le asigna un puntaje a cada cabina candidata para atender un llamado, y elige la que tiene el puntaje más bajo. La fórmula, según describe el artículo, combina varios factores:
Score = ETA_hasta_recogida
+ penalizacion_por_carga_actual
+ penalizacion_por_anti_amontonamiento
- bonus_por_coincidencia_de_direccion
- bonus_por_cabina_ociosa_cercana
- bonus_por_carga_bajaDos detalles del diseño valen la pena remarcar. Primero, la penalización anti amontonamiento: si otra cabina ya va camino al mismo piso en la misma dirección, RSR castiga a la segunda cabina para evitar que dos ascensores lleguen juntos y dejen sin servicio al resto del edificio por un rato. Segundo, el bonus por cabina ociosa cercana: una cabina parada a menos de dos pisos del llamado suma puntos a favor, para tener siempre capacidad de reserva cerca de las zonas activas.
El otro elemento clave es que RSR no asigna una sola vez y listo: recalcula cada 5 segundos. Si la cabina A, que iba a recoger a un pasajero, se atrasa por otras paradas, el sistema puede reasignar ese llamado a la cabina B en tiempo real. Esa re-optimización constante es, según el artículo, la pieza que más mejora el flujo de tráfico frente a una asignación fija al momento del llamado.
La forma correcta de medir qué tan bueno es un algoritmo no es el tiempo de espera promedio. Un promedio esconde a la gente que espera mucho mientras la mayoría espera poco. La métrica que importa es la distribución completa: el p50 (mediana) y sobre todo el p90. Un p90 de 2 minutos significa que el 90% de los pasajeros espera 2 minutos o menos, pero también que 1 de cada 10 espera más. Esa cola larga es la que la gente recuerda cuando dice que el ascensor tarda una eternidad.
El tráfico tampoco es constante durante el día. En un edificio corporativo típico, la mañana está dominada por viajes del lobby a los pisos altos; la tarde invierte el patrón; el mediodía mezcla ambos sentidos; y el resto del día es sobre todo tráfico piso a piso. La franja con peores estadísticas de espera es, de forma consistente, la mañana: todo el mundo entra al mismo tiempo y en la misma dirección, así que no hay margen para combinar viajes.
| Algoritmo | Cuándo conviene | Ventaja | Limitación |
|---|---|---|---|
| SCAN | Sistemas simples de una sola cabina | Predecible, fácil de implementar | Sube hasta el último piso aunque nadie lo pidió ahí |
| LOOK | Estándar por defecto en la mayoría de edificios | No desperdicia viajes al techo del edificio | No coordina bien con otras cabinas en edificios grandes |
| RSR | Edificios con varias cabinas y tráfico moderado | Reasigna cada 5 segundos y evita el amontonamiento | Pierde ventaja cuando el flujo es tan alto que todas las cabinas van llenas |
| Destination Dispatch | Torres muy altas con 8 o más cabinas por núcleo | Conoce el destino de cada pasajero antes de asignar | En la mayoría de los edificios da peores tiempos de espera que los botones simples |
El cruce entre LOOK y RSR es uno de los hallazgos más contraintuitivos del análisis. A medida que sube el flujo de llamados, LOOK empieza a superar a RSR. La explicación es mecánica: cuando las cabinas van siempre llenas y paran en casi todos los pisos de todas formas, las reglas extra de RSR (anti amontonamiento, bonus por cabina ociosa) dejan de tener margen para marcar diferencia. Lo mismo pasa en edificios chicos con pocas cabinas por núcleo: hay tan pocas opciones para elegir que la sofisticación del puntaje no cambia el resultado.
💭 Clave: destination dispatch tiene toda la información (sabe a qué piso vas antes de que subas), pero en la mayoría de los edificios da peores tiempos de espera que un simple botón de subir o bajar. Solo gana en torres muy altas con 8 o más cabinas por núcleo.
La razón, según describe el artículo, tiene que ver con la rigidez de la asignación: una vez que el kiosco te asigna una cabina específica, quedás atado a ella aunque otra cabina pase antes por tu piso. Los botones tradicionales, en cambio, dejan que cualquier cabina disponible responda al llamado, lo que le da más flexibilidad al optimizador en el momento de decidir.
flowchart TD
A["Llamado nuevo en un piso"] --> B["Calcular ETA de cada cabina"]
B --> C["Sumar penalizacion por carga y amontonamiento"]
C --> D["Restar bonus por direccion e idle cercano"]
D --> E["Elegir cabina con puntaje mas bajo"]
E --> F["Reevaluar todo cada 5 segundos"]
F --> BCómo probarlo
No hace falta instalar nada para ver los algoritmos en acción: el simulador interactivo de john.fun/elevators corre en el navegador y deja mover el flujo de llegadas y comparar en vivo el porcentaje de esperas menores a 30 y 90 segundos entre LOOK y RSR.
Si querés meterle mano al código, una simulación simplificada del algoritmo LOOK cabe en pocas líneas de JavaScript. Este ejemplo mueve una sola cabina entre pisos y atiende los llamados en el orden en que la ruta los va cruzando:
function simularLook(pisos, llamados) {
let piso = 0;
let direccion = 1;
const log = [];
while (llamados.length > 0) {
const enEstePiso = llamados.filter(l => l.piso === piso);
enEstePiso.forEach(l => log.push({ piso, evento: "recogida" }));
llamados = llamados.filter(l => l.piso !== piso);
const quedanArriba = llamados.some(l => l.piso > piso);
const quedanAbajo = llamados.some(l => l.piso < piso);
if (direccion === 1 && !quedanArriba) direccion = -1;
if (direccion === -1 && !quedanAbajo) direccion = 1;
piso += direccion;
piso = Math.max(0, Math.min(pisos - 1, piso));
}
return log;
}Para medir el p50 y el p90 de esa simulación (la métrica que de verdad importa, como vimos arriba), basta con guardar el tiempo de espera de cada llamado y ordenarlos:
function percentil(tiempos, p) {
const ordenados = [...tiempos].sort((a, b) => a - b);
const idx = Math.floor((p / 100) * (ordenados.length - 1));
return ordenados[idx];
}
// tiempos = [12, 45, 8, 90, 23] segundos de espera por llamado
console.log("p50:", percentil(tiempos, 50));
console.log("p90:", percentil(tiempos, 90));Correr esa misma simulación con distintas tasas de llegada de llamados es la forma más directa de reproducir, a pequeña escala, el cruce entre LOOK y RSR que muestra el artículo original.
💡 Tip: si vas a comparar algoritmos en tu propia simulación, corré cada configuración con miles de llamados aleatorios antes de comparar el p90: con pocas muestras la cola de la distribución varía demasiado para sacar conclusiones.
Impacto y análisis
El interés de este problema para un desarrollador no es solo curiosidad. Es el mismo patrón que aparece en un load balancer que reparte requests entre réplicas, en un scheduler que decide en qué nodo poner un proceso, o en una cola de trabajos que reparte jobs entre workers. En los cuatro casos hay recursos limitados (cabinas, réplicas, nodos, workers), una demanda que llega en ráfagas desiguales, y la tentación de agregar reglas cada vez más sofisticadas para optimizar mejor.
Lo que muestra el cruce entre RSR y LOOK es una lección que se repite en sistemas distribuidos: agregar reglas de puntaje no siempre mejora el resultado, y en condiciones de carga alta, un algoritmo simple y predecible puede rendir igual o mejor que uno sofisticado. El mismo patrón de los algoritmos de ascensores aparece, por ejemplo, cuando un balanceador de carga usa round robin en vez de reglas de menor conexión bajo ciertos niveles de tráfico.
El caso de destination dispatch también tiene un paralelo directo: es tentador pensar que más información de entrada (saber el destino exacto antes de asignar) siempre mejora la asignación. El resultado del artículo dice lo contrario en la mayoría de los casos: la rigidez de atar un pasajero a una cabina específica desde el principio le quita margen de maniobra al optimizador. En sistemas de colas, el equivalente sería fijar de antemano qué worker va a procesar cada tarea en vez de dejar que el primero que se libera la tome.
Qué sigue
El artículo de john.fun no menciona planes de expandir el simulador, pero deja abierta una pregunta que el propio texto reconoce como fuera de alcance: cómo se comparan estos algoritmos en tiempo de viaje dentro de la cabina, no solo en tiempo de espera antes de subir. RSR y LOOK tienen comportamientos distintos ahí también, según adelanta el autor, aunque sin entrar en detalle.
Para quien quiera seguir explorando, simular ascensores es un ejercicio clásico de ciencias de la computación: SCAN y LOOK se enseñan en cursos de sistemas operativos como algoritmos de planificación de disco (no solo de ascensores), y en cursos de investigación operativa aparecen como caso de estudio de colas con servidores múltiples.
📖 Resumen en Telegram: Ver resumen
Probalo vos: abrí el simulador en john.fun/elevators, subí el flujo de llamados por minuto y mirá en vivo cómo LOOK le empieza a ganar a RSR.
Preguntas frecuentes
¿Qué diferencia hay entre SCAN y LOOK?
SCAN siempre viaja hasta el último piso del edificio antes de invertir el sentido, incluso si nadie pidió ese piso. LOOK corrige eso: la cabina solo sube o baja hasta el piso más alto o más bajo que alguien pidió, y ahí invierte. LOOK es la variante que la mayoría de los edificios usa hoy.
¿Qué es el algoritmo RSR de Otis?
RSR (Relative System Response) es un algoritmo propietario de Otis que asigna un puntaje a cada cabina disponible para atender un llamado, combinando el tiempo estimado de llegada, la carga actual, penalizaciones por amontonamiento con otras cabinas y bonus por cercanía o inactividad. Elige siempre la cabina con el puntaje más bajo y recalcula todo cada 5 segundos.
¿Por qué los kioscos de destino no son siempre mejores?
Porque atan al pasajero a una cabina específica desde el momento en que ingresa el piso de destino, incluso si después otra cabina queda mejor posicionada. Los botones tradicionales dejan que cualquier cabina disponible responda, lo que le da más flexibilidad al sistema de asignación.
¿Qué significa que el p90 de espera sea de 2 minutos?
Significa que el 90% de los pasajeros esperó 2 minutos o menos por el ascensor, y que el 10% restante esperó más. Es una métrica más honesta que el promedio porque muestra la cola larga de esperas incómodas que la gente realmente recuerda.
¿Por qué la mañana tiene las peores esperas?
Porque casi todo el tráfico va en la misma dirección, del lobby a los pisos altos, así que no hay viajes mixtos que un algoritmo pueda combinar para ahorrar paradas. En la tarde el patrón se invierte, y al mediodía se mezcla con tráfico piso a piso.
¿En qué edificios conviene destination dispatch?
El artículo señala que gana, aunque como excepción, en edificios muy altos con 8 o más cabinas por núcleo. Fuera de ese caso, los botones simples de subir y bajar suelen dar mejores tiempos de espera.
Referencias
- john.fun/elevators: el artículo interactivo original con los simuladores de SCAN, LOOK, RSR y destination dispatch.
- Wikipedia: Elevator algorithm: descripción general del algoritmo SCAN y sus variantes.
- Wikipedia: Destination dispatch: contexto sobre los sistemas de kioscos de destino.
- Otis Elevator Company: fabricante que desarrolló el algoritmo RSR (Relative System Response) mencionado en el artículo.
📱 ¿Te gusta este contenido? Únete a nuestro canal de Telegram @programacion donde publicamos a diario lo más relevante de tecnología, IA y desarrollo. Resúmenes rápidos, contenido fresco todos los días.
Imagen destacada: Foto de Julia Taubitz en Unsplash
0 Comentarios