Algoritmos de despacho de elevadores

• A operação de elevadores não é uma simples resposta a chamadas, mas um problema de otimização de despacho que considera em conjunto o número de cabines, o fluxo de passageiros, a carga e a direção de deslocamento
• O SCAN para uma única cabine muda de direção no último andar, mas o LOOK retorna no andar mais alto onde há uma solicitação real, ficando mais próximo da operação que as pessoas normalmente esperam
• O RSR (Relative System Response), para várias cabines, atribui pontuações com base no tempo estimado de chegada, carga etc., e reotimiza o despacho a cada 5 segundos, podendo transferir passageiros de uma cabine atrasada para outra
• Se as cabines estão sempre lotadas, ou se o fluxo de passageiros é tão alto que elas param em todos os andares e há poucas cabines, o LOOK simples pode ser melhor que o RSR complexo
• O despacho por destino (Destination Dispatch), em que o andar de destino é informado antecipadamente, obtém mais informações, mas dificulta trocar a cabine designada; por isso, exceto em alguns casos como arranha-céus e grupos com 8 ou mais cabines, em geral resulta em tempos de espera maiores que os botões tradicionais de subir/descer

---

Onde uma única cabine muda de direção

• O SCAN, patenteado em 1961, parte do saguão, sobe até o último andar e então muda de direção para descer, pegando e deixando passageiros ao longo do percurso
• O LOOK não vai obrigatoriamente até o último andar; ele opera apenas até o andar mais alto solicitado e então retorna
• Em geral, o modo de operação de elevadores que as pessoas conhecem e esperam é mais próximo do LOOK

Despacho básico com várias cabines

• Quando há vários elevadores, é preciso coordenar qual cabine atenderá qual chamada
• Em um sistema básico, um agendador central define os andares de parada de cada cabine e atribui novas chamadas à cabine mais próxima
• Mas o despacho baseado apenas em distância tem dificuldade para refletir adequadamente situações como a de uma cabine próxima que já está lotada

Como avaliar o tempo de espera

• A métrica mais intuitiva para algoritmos de elevadores é o tempo de espera, do chamado até a chegada da cabine
• De forma simples, é possível medir a proporção de cabines que chegam em até 30 ou 90 segundos
• Para uma avaliação mais rigorosa, reúnem-se os tempos de espera de milhares de viagens e verificam-se a distribuição e o histograma
  • Se o p90 é de 2 minutos, significa que 90% dos passageiros esperaram até 2 minutos
  • Se o p50 é de 1 minuto, a cabine chegou em até 1 minuto em metade das chamadas
• Passageiros tendem a se lembrar com mais força dos casos p90, em que esperaram excepcionalmente muito, do que do tempo médio de espera

Como o fluxo de passageiros muda conforme o horário

• De manhã, em grandes edifícios comerciais, a maior parte dos deslocamentos vai do saguão para os andares superiores
• À noite, por causa da saída do trabalho, predomina o fluxo dos andares superiores para baixo
• Na hora do almoço, subidas e descidas se misturam; no restante do tempo, há muitos deslocamentos entre andares
• A distribuição dos tempos de espera varia bastante conforme o horário e o padrão de tráfego, e as estatísticas são especialmente ruins no horário de chegada ao trabalho pela manhã

Como o RSR escolhe uma cabine

• O RSR (Relative System Response) da Otis pontua o quanto cada cabine é adequada para pegar passageiros; quanto menor a pontuação, mais adequada ela é
• A pontuação de embarque é calculada combinando vários fatores
  • Tempo estimado de chegada até o andar da chamada
  • Penalidade de carga conforme o número de passageiros a bordo
  • Penalidade antiagrupamento aplicada quando já há uma cabine indo na mesma direção para o mesmo andar
  • Bônus por direção de deslocamento compatível
  • Bônus para cabine ociosa a até dois andares do andar da chamada
  • Bônus por baixa carga
• O antiagrupamento (anti-bunching) desencoraja atribuições adicionais se outra cabine já está indo na mesma direção para o mesmo andar
• O RSR reotimiza todo o despacho a cada 5 segundos
  • Se a cabine A se atrasa, passageiros que originalmente seriam pegos por A podem ser reatribuídos à cabine B
  • Essa reotimização contínua é a chave para tornar o fluxo de passageiros mais fluido

Diferenças de desempenho entre LOOK e RSR

• Com uma ferramenta de análise de tempos de espera, é possível comparar as taxas de chegada em até 30 e 90 segundos do LOOK e do RSR
• À medida que o fluxo de passageiros aumenta, o LOOK começa a superar o RSR
  • Quando as cabines estão sempre lotadas e param em todos os andares, o efeito das regras adicionais do RSR diminui
• Em edifícios menores, com poucos elevadores por grupo de cabines, o LOOK também tende a ser melhor que o RSR, de modo que uma abordagem simples pode ser mais adequada
• Além do tempo de espera, também é possível medir o tempo de viagem após o embarque até o andar de destino
  • LOOK e RSR apresentam características diferentes também nessa métrica, mas uma comparação específica não é abordada

Por que o despacho por destino é desvantajoso apesar de ter mais informações

• O despacho por destino é um método em que o passageiro primeiro informa o andar de destino em um quiosque em cada andar, e o sistema indica o elevador a embarcar
• O sistema de otimização consegue saber todos os destinos dos passageiros antes da chegada da cabine, mas o tempo de espera geralmente fica maior que no método tradicional com botões de subir/descer
• Há exceções em que o método com quiosque é vantajoso, como em edifícios muito altos com 8 ou mais elevadores por grupo de cabines
• A principal causa da queda de desempenho é a rigidez do despacho
  • No método tradicional, é possível reotimizar a rota das cabines e a atribuição de passageiros a cada 5 segundos
  • No despacho por destino, o passageiro precisa entrar na cabine inicialmente designada
  • Mesmo que a situação operacional mude 30 segundos após a chamada, não é possível trocar de forma flexível a cabine designada
• A perda de flexibilidade de realocação é maior que o benefício da informação adicional sobre o destino

Itens ajustáveis e escopo da simulação

• Na simulação completa, é possível ajustar o número de andares, o número de cabines e o fluxo de passageiros por minuto, e verificar as taxas de chegada em até 30 e 90 segundos
• Algoritmos reais de elevadores têm muitos outros fatores a considerar, e o escopo tratado aqui é apenas parte do domínio completo
• A entrada do botão de chamada é transmitida, mas como o elevador calcula várias condições de operação em conjunto, ele pode não chegar imediatamente

[GN⁺]

Opiniões no Hacker News

• Durante cerca de metade do último meio século, elevadores foram controlados apenas por relés, sem computadores, e algoritmos como esses também eram implementados com circuitos lógicos cabeados
  Detalhes interessantes, como diagramas de circuitos, podem ser vistos em patentes antigas da Otis

• Na aula de ciência da computação do ensino médio, implementei várias simulações de algoritmos de elevador como projeto individual
  Discos rígidos rotativos se parecem com um elevador muito longo enrolado em torno do spindle em vez de na vertical, e o SCAN é de fato um algoritmo de escalonamento de disco: https://en.wikipedia.org/wiki/Elevator_algorithm

  • Na faculdade também fiz um projeto parecido usando microcontrolador e LEDs, entre outras coisas, e foi muito divertido

• Fico me perguntando se a conclusão de que o despacho com reserva de destino é pior no geral saiu assim porque os andares de destino foram definidos aleatoriamente
  Em prédios reais, a maioria das pessoas que não está no térreo vai para o térreo, e no térreo as pessoas que trabalham no mesmo andar tendem a sair juntas para almoçar e depois voltar juntas ao mesmo andar. O despacho com reserva de destino é vantajoso para esse padrão, pois consegue agrupar grandes grupos com o mesmo destino

  • É uma premissa ainda menos adequada para hotéis. De manhã, as pessoas não se deslocam apenas do lobby para os quartos; elas descem para tomar café da manhã, sobem de novo e depois descem novamente, gerando tráfego bidirecional
    Em alguns hotéis, o sistema de quiosques até muda a interface do usuário conforme o horário de pico do café da manhã
  • Navios de cruzeiro que usam despacho com reserva de destino também foram muito mais agradáveis. Em navios com algoritmos antigos, a espera nos horários de pico é sofrida, embora isso acabe fazendo a gente usar mais as escadas
  • Uma pessoa em um andar alto tem probabilidade muito maior de voltar ao térreo do que de subir ou descer um ou dois andares, mas os passageiros em espera da simulação parecem não refletir isso direito
    O efeito de agrupamento de pessoas indo almoçar ou voltando do almoço também existe na prática e fica mais evidente no meio do dia do que de manhã ou à noite
  • Acho que o padrão de grandes grupos saindo do térreo para o mesmo destino é uma das maiores razões pelas quais o despacho com reserva de destino é melhor
    Há também artigos dizendo que, depois que escritórios ou hotéis migraram para esse método, o tempo de espera caiu bastante
  • Fico pensando se isso acontece porque a métrica de avaliação é tempo de espera, e não tempo de viagem. O despacho com reserva de destino reduz paradas desnecessárias durante o deslocamento
    Um prédio novo que visitei recentemente também usava esse método. Na faculdade, meu colega de quarto, que estudava engenharia elétrica, montou em uma protoboard um circuito de elevador com botões de chamada, motor e um disco transparente com quadrados pretos para detectar posição; provavelmente era um algoritmo simples

• Se você está tendo o primeiro contato com escalonamento de elevadores, recomendo este jogo: https://play.elevatorsaga.com/

  • A premissa é simples, mas os níveis ficam satisfatoriamente difíceis à medida que avançam, e há até algumas falhas aleatórias, o que aumenta o desafio. Queria que houvesse mais jogos assim
  • Parece bem acabado, mas ainda assim prefiro https://en.wikipedia.org/wiki/Elevator_Action
  • Excelente, mas para mim o melhor jogo de escalonamento de elevadores é SimTower
  • Sempre que espero elevador em um hotel onde acontece uma conferência, acabo voltando a esse jogo
  • Sempre me perguntei se seria divertido um jogo em que você programa diretamente o escalonador de elevadores, e achei que ninguém teria feito isso; fico feliz por estar errado

• Pensei muito nesse problema enquanto desenvolvia Sky Lobby, um jogo de controle e automação de elevadores para iOS e Android
  Adotei um algoritmo semelhante ao LOOK, por ser o mais próximo do movimento que os jogadores esperam, mas, quando a escolha era ambígua, dava prioridade ao andar que estava esperando há mais tempo para melhorar o p90, importante no jogo. Mas, ao adicionar elevadores de dois andares que atendem dois pisos ao mesmo tempo, andares de transferência entre poços e poços expressos, fica muito menos claro qual algoritmo é ótimo ou mais intuitivo. Como era um jogo, não um sistema real, encontrei heurísticas suficientemente boas e permiti que o jogador sobrescrevesse manualmente o plano de operação quando não gostasse; isso deixou a maioria satisfeita

• Toda vez que espero um elevador, penso em como deve ser complicado criar um algoritmo que minimize o tempo de espera até o passageiro embarcar e chegar ao destino
  Às vezes até imagino se as pessoas que implementaram isso não são sádicos malignos que nos fazem esperar mais de propósito

  • Seria bom se o elevador também levasse em conta a carga de passageiros
    Na manhã seguinte a uma grande conferência, todo mundo queria descer, mas a cabine lotada parava diligentemente em todos os andares. Se um elevador para 10 pessoas já pegou passageiros chamados em 10 andares, deveria poder ir direto ao térreo e economizar 5 minutos, em vez de repetir em cada andar “não tem espaço, vou pegar o próximo”. Isso é especialmente grave se uma pessoa com mobilidade reduzida no 2º andar precisa pegar um voo
  • Desenvolvi várias vezes software de integração externa que conecta elevadores a outros equipamentos
    Quando você vê a posição e o movimento de todos os elevadores, a agenda é surpreendentemente apertada. No lobby, a espera parece interminável, mas, do ponto de vista do despacho, a atividade é contínua; durante o horário de uso do prédio, os elevadores quase não ficam ociosos. Só observar o painel de status já é interessante. Além disso, quando um técnico de elevadores diz “vamos nos encontrar bem cedo”, normalmente quer dizer por volta das 4h da manhã, para terminar o trabalho antes de as pessoas chegarem
  • Não é que o software de escalonamento de elevadores seja tosco; já há uma enorme quantidade de reflexão envolvida nisso
    Elevadores são caros e proprietários de prédios não costumam investir em excesso por impulso, então normalmente instalam apenas o número mínimo de elevadores suficiente para a demanda prevista, às vezes até menos
  • Além do tempo de espera, eles podem estar otimizando funções-objetivo como desgaste e consumo de energia

• Há quatro elevadores, e acima de cada um aparece a lista de andares onde ele pretende parar; enquanto você espera, a atribuição entre elevador e andar também muda, com aviso sonoro. Parece um recurso feito para permitir despacho ideal

• O maior problema com elevadores não é o algoritmo, mas as pessoas que não entendem o conceito de apertar o botão de subir ou descer conforme a direção do destino
  Quando apertam os dois botões “para chegar mais rápido”, em metade das vezes vão primeiro na direção oposta e ainda adicionam paradas desnecessárias para quem já está dentro

  • Acho que nunca vi alguém fazendo isso de fato
  • Em situações assim, em vez de presumir que as pessoas não entendem, muitas vezes a resposta aparece se você pensar ao contrário: se elas entendem, por que isso seria racional?
    Talvez seja parecido com a psicologia das falsas telas de carregamento. Esperar sem saber quando vai chegar é entediante e frustrante, mas, se você entra em um elevador que se move mesmo na direção oposta, sente que há progresso. No fim, mesmo demorando mais, é menos frustrante quando algo está acontecendo
  • Quando a porta abre, também há quem pergunte às pessoas dentro se o elevador está subindo ou descendo. Há uma seta de direção bem na frente
  • Se você está em um andar baixo tentando descer em horário de pico de check-out, os elevadores descendo podem vir sempre lotados
    Por outro lado, se a demanda para subir é baixa, entrar primeiro para subir e fazer a volta até o fim pode ser uma estratégia mais racional do que esperar esperando que apareça espaço
  • Em horários de grande movimento em prédios cheios, a capacidade dos elevadores é insuficiente, então, para ir ao térreo, subir primeiro e depois descer pode reduzir o pior caso ou até ser mais rápido em média
    Nesse caso, apertar os botões de subir e descer ao mesmo tempo não é burrice; é lógico

• Independentemente do desempenho do algoritmo, a psicologia da percepção do tempo de espera também é importante
  Esperar sem fazer nada é muito irritante, mas fazer algo durante o mesmo período parece progresso e reduz a insatisfação. Em aeroportos, há um caso em que, em vez de fazer os passageiros irem direto do portão à esteira de bagagens e esperarem pela primeira mala, criaram deliberadamente um percurso mais longo e sinuoso; o tempo total era o mesmo, mas as pessoas ficaram mais satisfeitas

• Em vários algoritmos de elevadores, o desgaste e o custo de manutenção totais raramente entram na discussão
  Mais movimento pode acelerar a troca de óleo hidráulico e a falha de peças. Algoritmos eficientes também podem reposicionar elevadores previamente conforme o horário do dia ou a posição de outras cabines; por exemplo, quando uma cabine desce, outra pode ser enviada para cima. Algoritmos baseados em sinais de demanda minimizam esse tipo de movimento. É importante equilibrar a redução de manutenção mesmo que isso aumente o tempo de espera, e é possível que o proprietário do prédio, que arca com os custos, não dê tanta importância ao tempo de espera dos passageiros

  • Durante a manutenção, é preciso retirar um elevador de operação, então o tempo médio de espera nesse período também aumenta