엘리베이터 배차 알고리듬

• 엘리베이터 운행은 단순한 호출 응답이 아니라 차량 수, 승객 흐름, 적재량, 이동 방향을 함께 고려하는 배차 최적화 문제임
• 단일 차량용 SCAN은 최상층에서 방향을 바꾸지만, LOOK은 실제 요청이 있는 가장 높은 층에서 되돌아가 일반적인 운행 기대에 더 가까움
• 여러 차량을 다루는 RSR(Relative System Response) 은 도착 예상 시간과 적재량 등을 점수화하고, 5초마다 배차를 재최적화해 지연된 차량의 승객을 다른 차량으로 돌릴 수 있음
• 차량이 계속 만원이거나 층마다 정차할 정도로 승객 유량이 많고 차량 수가 적다면, 복잡한 RSR보다 단순한 LOOK이 더 나을 수 있음
• 목적층을 미리 입력하는 목적지 배차(Destination Dispatch) 는 더 많은 정보를 확보하지만 지정 차량을 바꾸기 어려워, 초고층·차량 8대 이상 같은 일부 사례를 제외하면 전통적인 상·하 버튼보다 대기 시간이 대체로 길어짐

---

단일 차량은 어디에서 방향을 바꾸는가

• 1961년 특허를 받은 SCAN은 로비에서 출발해 최상층까지 올라간 뒤 방향을 바꿔 내려오며, 이동 경로에 있는 승객을 태우고 내려줌
• LOOK은 최상층까지 무조건 가지 않고 요청된 가장 높은 층까지만 운행한 뒤 되돌아감
• 일반적으로 사람들이 알고 있고 기대하는 엘리베이터 운행 방식은 LOOK에 가까움

여러 차량의 기본 배차

• 엘리베이터가 여러 대라면 어떤 차량이 어느 호출을 맡을지 조정해야 함
• 기본 시스템에서는 중앙 스케줄러가 각 차량의 정차 층을 지정하고 새 호출을 가장 가까운 차량에 배정함
• 하지만 단순 거리 기반 배차만으로는 가까운 차량이 만원인 상황 등을 충분히 반영하기 어려움

대기 시간을 평가하는 방법

• 엘리베이터 알고리듬의 가장 직관적인 평가지표는 호출부터 차량 도착까지의 대기 시간임
• 간단하게는 차량이 30초 또는 90초 안에 도착한 비율을 측정할 수 있음
• 더 엄밀하게 평가하려면 수천 회 운행의 대기 시간을 모아 분포와 히스토그램을 확인함
  • p90이 2분이면 승객의 90%가 2분 이내로 기다렸다는 뜻임
  • p50이 1분이면 절반의 호출에서 차량이 1분 이내에 도착함
• 승객은 평균 대기 시간보다 유난히 오래 기다린 p90 사례를 더 강하게 기억하는 경향이 있음

시간대에 따라 달라지는 승객 흐름

• 대형 사무용 건물의 아침에는 로비에서 상층으로 올라가는 이동이 대부분을 차지함
• 저녁에는 퇴근 인원으로 인해 상층에서 아래로 내려오는 흐름이 우세해짐
• 점심시간에는 상행과 하행이 섞이고, 나머지 시간에는 층과 층 사이의 이동이 많음
• 대기 시간 분포는 시간대와 교통 패턴에 따라 크게 달라지며, 특히 아침 출근 시간의 통계가 나쁨

RSR은 어떤 차량을 선택하는가

• Otis의 RSR(Relative System Response) 은 각 차량이 승객을 태우기에 얼마나 적합한지 점수화하며, 점수가 낮을수록 적합함
• 승차 점수는 여러 요소를 조합해 계산함
  • 호출 층까지의 도착 예상 시간
  • 탑승 중인 승객 수에 따른 적재 페널티
  • 같은 방향으로 같은 층을 향하는 차량이 이미 있을 때 적용하는 군집 방지 페널티
  • 이동 방향 일치 보너스
  • 호출 층에서 두 개 층 이내에 있는 유휴 차량 보너스
  • 낮은 적재량 보너스
• 군집 방지(anti-bunching) 는 다른 차량이 이미 같은 방향으로 같은 층을 향하고 있다면 추가 배정을 억제함
• RSR은 5초마다 전체 배차를 다시 최적화함
  • 차량 A가 지연되면 원래 A가 태울 예정이던 승객을 차량 B로 재배정할 수 있음
  • 이러한 지속적 재최적화가 승객 흐름을 원활하게 만드는 핵심임

LOOK과 RSR의 성능 차이

• 대기 시간 분석 도구를 이용하면 LOOK과 RSR의 30초·90초 이내 도착 비율을 비교할 수 있음
• 승객 유량이 높아질수록 LOOK이 RSR을 앞서기 시작함
  • 차량이 항상 만원이고 모든 층에 정차하면 RSR의 추가 규칙이 주는 효과가 줄어듦
• 차량 묶음당 엘리베이터 수가 적은 소형 건물에서도 LOOK이 RSR보다 나은 경향이 있어, 단순한 방식이 더 적합할 수 있음
• 대기 시간뿐 아니라 탑승 후 목적층까지 걸리는 이동 시간도 측정 가능함
  • LOOK과 RSR은 이 지표에서도 서로 다른 특성을 보이지만 구체적인 비교는 다루지 않음

목적지 배차가 더 많은 정보에도 불리한 이유

• 목적지 배차는 각 층의 키오스크에서 목적층을 먼저 입력하면 탑승할 엘리베이터를 지정하는 방식임
• 최적화 시스템이 차량 도착 전에 승객별 목적지를 모두 알 수 있지만, 대기 시간은 일반적으로 전통적인 상·하 버튼 방식보다 길어짐
• 매우 높은 건물에서 차량 묶음당 엘리베이터가 8대 이상인 경우처럼 키오스크 방식이 유리한 예외도 있음
• 성능 저하의 핵심 원인은 배차의 경직성임
  • 전통적인 방식은 5초마다 차량 경로와 승객 배정을 다시 최적화할 수 있음
  • 목적지 배차에서는 승객이 처음 지정된 차량에 타야 함
  • 호출 30초 뒤 운행 상황이 달라져도 지정 차량을 유연하게 바꾸지 못함
• 목적지라는 추가 정보의 이점보다 재배치 유연성을 잃는 손해가 더 큼

시뮬레이션의 조정 항목과 범위

• 전체 시뮬레이션에서는 층수, 차량 수, 분당 승객 유량을 조절하며 30초·90초 이내 도착 비율을 확인할 수 있음
• 실제 엘리베이터 알고리듬에는 더 많은 고려 사항이 있으며, 여기서 다룬 범위는 전체 영역의 일부임
• 호출 버튼 입력은 전달되지만 엘리베이터가 여러 운행 조건을 함께 계산하므로 즉시 도착하지 않을 수 있음

[GN⁺]

Hacker News 의견들

• 지난 반세기 중 대략 절반 동안 엘리베이터는 컴퓨터 없이 릴레이만으로 제어됐으며, 이런 알고리즘도 배선된 논리 회로로 구현했음
  회로도 등 흥미로운 세부 사항은 Otis의 옛 특허에서 볼 수 있음

• 고등학교 컴퓨터 과학 수업 때 여러 엘리베이터 알고리즘 시뮬레이션을 개인 프로젝트로 구현했음
  회전식 하드디스크는 수직 대신 스핀들 주위를 감싼 아주 긴 엘리베이터와 비슷하며, SCAN은 실제로 디스크 스케줄링 알고리즘임: https://en.wikipedia.org/wiki/Elevator_algorithm

  • 대학에서도 마이크로컨트롤러와 LED 등을 이용해 비슷한 프로젝트를 했는데 매우 재미있었음

• 목적지 층을 무작위로 설정했기 때문에 목적지 예약 배차가 전반적으로 나쁘다는 결과가 나온 것인지 궁금함
  실제 건물에서는 지상층이 아닌 사람 대부분이 지상층으로 가고, 지상층에서는 같은 층에서 일하는 사람들이 점심시간에 함께 나갔다가 같은 층으로 함께 돌아가는 경향이 있음. 목적지 예약 배차는 같은 목적지의 큰 무리를 묶어 태울 수 있어 이런 패턴에 유리함

  • 호텔에는 더욱 맞지 않는 가정임. 아침에는 로비에서 객실로만 이동하는 게 아니라 아침 식사를 하러 내려갔다가 다시 올라오고 또 내려가므로 양방향 통행이 발생함
    일부 호텔의 키오스크 방식은 아침 식사 혼잡 시간에 따라 사용자 인터페이스도 바꿈
  • 목적지 예약 배차를 쓰는 크루즈선도 훨씬 쾌적했음. 구형 알고리즘을 쓰는 배는 혼잡 시간의 대기가 고통스럽지만 덕분에 계단을 더 쓰게 되긴 함
  • 위층에 있는 개인은 한두 층 위나 아래보다 지상층으로 돌아갈 확률이 훨씬 높지만, 시뮬레이션의 대기 승객은 이를 제대로 반영하지 않는 듯함
    점심을 먹으러 가거나 돌아오는 사람들의 군집 효과도 실제로 존재하며, 아침이나 저녁보다 한낮에 두드러짐
  • 지상층에서 같은 목적지로 큰 무리가 이동하는 패턴이 목적지 예약 배차가 더 나은 가장 큰 이유 중 하나라고 봄
    사무실이나 호텔이 이 방식으로 전환한 뒤 대기 시간이 크게 줄었다는 기사도 있음
  • 평가 기준이 이동 시간이 아니라 대기 시간이어서 그런 것인지 궁금함. 목적지 예약 배차는 이동 중 불필요한 정차를 줄여줌
    최근 방문한 신축 건물에서도 이 방식을 사용했음. 대학 시절 전기공학을 전공한 룸메이트는 호출 버튼, 모터, 위치 감지용 검은 사각형이 표시된 투명 원판을 브레드보드에 연결해 엘리베이터 회로를 만들었는데, 아마 단순 알고리즘이었음

• 엘리베이터 스케줄링을 처음 접한다면 이 게임을 추천함: https://play.elevatorsaga.com/

  • 전제가 단순하지만 레벨이 올라갈수록 만족스럽게 어려워지고, 약간의 무작위 고장까지 있어 도전성이 커짐. 이런 게임이 더 많으면 좋겠음
  • 완성도는 높아 보이지만 그래도 https://en.wikipedia.org/wiki/Elevator_Action을 더 좋아함
  • 훌륭하지만 내게 최고의 엘리베이터 스케줄링 게임은 SimTower임
  • 콘퍼런스가 열리는 호텔에서 엘리베이터를 기다릴 때마다 이 게임을 다시 찾게 됨
  • 엘리베이터 스케줄러를 직접 프로그래밍하는 게임이 재미있을지 늘 궁금했고 아무도 만들지 않았으리라 생각했는데, 틀려서 기쁨

• iOS·Android용 엘리베이터 제어·자동화 게임 Sky Lobby를 개발하며 이 문제를 많이 고민했음
  플레이어가 기대하는 움직임에 가장 가까운 LOOK과 유사한 알고리즘을 채택하되, 선택이 모호할 때는 오래 기다린 층을 우선해 게임에서 중요한 p90을 개선했음. 하지만 두 층을 동시에 담당하는 이층 승강기, 승강로 사이 환승층, 급행 승강로까지 더하면 최적이거나 가장 직관적인 알고리즘이 훨씬 불명확해짐. 실제 시스템이 아닌 게임이어서 충분히 괜찮은 휴리스틱을 찾고, 마음에 들지 않을 때 플레이어가 운행 계획을 수동으로 덮어쓸 수 있게 했더니 대부분 만족했음

• 엘리베이터를 기다릴 때마다 승객 탑승과 목적지 도착까지의 대기 시간을 최소화하는 알고리즘을 만드는 일이 얼마나 골치 아플지 생각함
  가끔은 이를 구현한 사람들이 일부러 더 오래 기다리게 하는 사악한 가학주의자가 아닐까 싶기도 함

  • 엘리베이터가 탑승 하중도 고려하면 좋겠음
    대형 콘퍼런스 다음 날 아침에는 모두 내려가려는데, 만원인 승강기가 모든 층에 꼬박꼬박 정차했음. 10인승 엘리베이터가 이미 10개 층의 호출 승객을 태웠다면, 매 층에서 “자리가 없네요, 다음 것을 탈게요”를 반복하는 대신 곧장 지상층으로 가서 5분을 절약할 수 있어야 함. 특히 2층의 이동 약자가 비행기를 타야 한다면 심각한 문제가 됨
  • 다른 장비와 엘리베이터를 연동하는 외부 통합 소프트웨어를 여러 번 개발했음
    모든 승강기의 위치와 움직임을 보면 스케줄이 놀랄 만큼 빽빽함. 로비에서는 기다림이 끝없이 느껴지지만 배차 관점에서는 활동이 쉴 새 없이 이어지고, 건물 이용 시간에는 승강기가 거의 놀지 않음. 상태 패널만 지켜봐도 흥미로움. 또 엘리베이터 정비사가 “아침 일찍 만나자”고 하면 대개 오전 4시쯤을 뜻하며, 사람들이 출근하기 전에 작업을 마치려 함
  • 엘리베이터 스케줄링 소프트웨어가 둔해서가 아니라 여기에 이미 엄청난 고민이 들어감
    엘리베이터는 비싸고 건물주는 충동적으로 과잉 투자하지 않으므로, 보통 예상 수요를 처리할 만큼만, 때로는 그보다 적은 최소 승강기 수를 설치함
  • 대기 시간 외에도 마모와 에너지 소비 같은 목적 함수를 최적화하고 있을 수 있음

• 승강기 4대 위에 각각 예정 정차 층이 표시되고, 기다리는 중에도 승강기와 층의 배정을 바꾸며 소리로 알려줌. 최적 배차가 가능하도록 만든 기능으로 보임

• 엘리베이터에서 가장 큰 문제는 알고리즘보다 목적지 방향에 맞춰 위·아래 호출 버튼을 누르는 개념을 이해하지 못하는 사람들임
  “더 빨리 온다”며 두 버튼을 모두 누르면 절반은 반대 방향으로 먼저 가고, 이미 탄 사람들에게 불필요한 정차까지 추가함

  • 실제로 그렇게 하는 사람을 본 적이 없는 듯함
  • 이런 상황에서는 사람들이 이해하지 못한다고 가정하기보다, 이해하고 있다면 왜 합리적인지를 거꾸로 생각해 보면 답이 나오는 경우가 많음
    아마 가짜 로딩 표시의 심리와 비슷함. 도착 시간을 모른 채 기다리면 지루하고 답답하지만, 반대 방향이라도 움직이는 엘리베이터에 타면 진행 중이라고 느껴짐. 결국 더 오래 걸려도 무언가 일어나는 상태가 덜 답답함
  • 문이 열리면 안에 탄 사람에게 위로 가는지 아래로 가는지 묻기도 함. 바로 앞에 방향 화살표가 표시돼 있음
  • 아래층에서 내려가려는데 퇴실 혼잡 시간이라면 하행 엘리베이터가 계속 만원일 수 있음
    반면 상행 수요가 적다면 위로 먼저 탄 뒤 끝까지 왕복하는 편이 자리가 날지 기대하며 기다리는 것보다 합리적인 전략이 될 수 있음
  • 혼잡한 건물의 바쁜 시간에는 엘리베이터 용량이 부족해, 지상층으로 갈 때 먼저 올라갔다 내려오는 편이 최악의 결과를 줄이거나 평균적으로 더 빠를 수 있음
    이때는 위·아래 버튼을 모두 누르는 행동이 어리석은 게 아니라 논리적임

• 알고리즘의 성능과 별개로 사람들이 대기 시간을 인식하는 심리도 중요함
  아무것도 하지 않고 기다리면 매우 짜증 나지만, 같은 시간 동안 무언가를 하면 진전으로 느껴져 불만이 줄어듦. 공항에서도 승객이 게이트에서 수하물 벨트로 곧장 가서 첫 가방이 나올 때까지 기다리게 하는 대신, 일부러 길고 돌아가는 동선을 만들자 총 소요 시간은 같아도 더 만족했다는 사례가 있음

• 여러 엘리베이터 알고리즘에서 전체 마모와 유지보수 비용은 흔히 논의되지 않음
  움직임이 많아지면 유압유 교체와 부품 고장이 빨라질 수 있음. 효율적인 알고리즘은 시간대나 다른 승강기의 위치에 따라 미리 재배치하기도 하는데, 예를 들어 한 대가 내려오면 다른 한 대를 올려 보낼 수 있음. 수요 신호 기반 알고리즘은 이런 움직임을 최소화함. 대기 시간을 늘리더라도 유지보수를 줄이는 균형이 중요하며, 비용을 부담하는 건물주는 승객의 대기 시간을 그만큼 중시하지 않을 가능성이 큼

  • 유지보수 중에는 엘리베이터 한 대를 운행에서 빼야 하므로 그 기간의 평균 대기 시간도 늘어남