엘리베이터 버튼을 누르고 층수 표시가 한 칸씩 바뀌는 것을 바라본다. 그저 운이 없다고 생각할 수도 있지만, 사실 이는 100년 넘게 연구되어 온 수학적 최적화 문제다.
어제(8월 1일), 웹 개발자 John Allsopp이 만든 인터랙티브 엘리베이터 알고리즘 설명서가 기술 커뮤니티 Hacker News 1위에 올랐으며, 오늘 Lobsters에서도 활발하게 논의되고 있다(추천 52개, 댓글 6개). 거창한 뉴스를 다루지 않고, 복잡한 엘리베이터 배차 로직을 직접 끌어다 쓸 수 있는 시뮬레이터로 만들었다. 이 글이 큰 관심을 끈 이유는 누구나 한 번쯤 던져본 질문에 답하기 때문일 것이다. “내가 버튼을 눌렀을 때, 엘리베이터는 과연 내 호출을 들었을까?”
들었다. 다만 고려할 것이 너무 많을 뿐이다.
엘리베이터가 최적화하는 것: 평균값의 함정
우선 질문을 하나 던져보자. 엘리베이터 배차가 잘 되고 있는지 어떻게 측정할 수 있을까?
직관적인 답은 ‘평균 대기 시간’이다. 하지만 수천 번의 탑승 대기 시간을 분포 그래프로 그려보면 평균값이라는 숫자가 착시를 일으킨다. John의 시뮬레이션은 두 가지 지표를 보여준다. p50은 1분, 즉 절반의 사람이 1분 이내에 엘리베이터에 탄다는 뜻이다. p90은 2분으로, 90%의 사람이 2분 넘게 기다리지 않는다는 의미다.
p50과 p90 사이의 단 1분 차이에 엘리베이터 산업의 핵심 비밀이 숨어 있다. 사람의 뇌는 평균을 기억하지 않고 가장 끔찍했던 순간만을 기억한다. 상위 10%의 긴 대기 시간은 기억 속에서 실제 비중보다 훨씬 큰 자리를 차지한다. 따라서 “엘리베이터가 항상 늦게 온다”는 느낌은 통계적 분포와 인지 편향이 함께 만들어낸 착각일 가능성이 높다. 실제로는 절반 이상 1분 안에 도착한다.
엔지니어링 차원의 절충점도 복잡하다. 평균 대기 시간, 최대 대기 시간, 에너지 소비라는 세 가지 목표가 서로 충돌한다. 가장 가까운 승객부터 데리러 가면 평균 대기 시간은 가장 짧아지지만, 극단적인 경우 다른 층의 누군가는 5분 동안 기다려야 한다. 평균 시간을 약간 희생하더라도 ‘영원히 오지 않는’ 극단적인 대기 시간을 없애는 것이 많은 오피스 빌딩이 선택한 현실적인 방식이다. 공짜 점심은 없다. 엘리베이터 회사는 사용자가 미처 생각하지 못한 절충안을 선택했을 뿐이다.
그림: 원문에서 수천 번의 시뮬레이션으로 그린 대기 시간 분포 시연. 출처: john.fun
가장 오래된 규칙: 끝까지 갔다가 돌아오기
알고리즘이 등장하기 전에는 엘리베이터 안에 사람이 직접 타고 있었다. ‘엘리베이터 안내원’이라는 직업은 20세기 중반까지 흔했다. 문을 열어주고 목적지를 물어본 뒤 수동으로 운전했다. 이후 엘리베이터가 자동화되면서 안내원은 사라졌고, 규칙은 기계에 맡겨졌으며, 배차 문제는 ‘사람’에서 ‘수학’으로 바뀌었다.
최초의 자동 규칙은 놀라울 정도로 단순했다. 1961년 특허를 받은 SCAN 알고리즘은 엘리베이터가 로비에서 출발해 맨 위층까지 올라가면서 승객을 태우고 내린 뒤, 정상에 도달하면 방향을 바꿔 내려오는 과정을 반복했다. 이후 승객이 없는데도 굳이 끝까지 갈 필요가 없다는 점 착안해 개선된 LOOK 알고리즘이 등장했다. 요청이 있는 가장 높은 층까지만 갔다가 방향을 바꾸는 방식이다. 오늘날 대부분의 사람들은 이 동작을 당연하게 받아들이며, 이것이 ‘알고리즘’이라는 사실조차 인지하지 못한다.
이 로직은 컴퓨터 과학에서도 유명한 친척을 가지고 있다. 바로 하드디스크 드라이브(HDD) 헤드 스케줄링이다. 디스크 헤드가 자기 디스크에서 데이터를 찾을 때 이동하는 방식이 거의 동일하다. 컴퓨터 과학에서는 이 알고리즘을 그대로 ‘엘리베이터 알고리즘(Elevator algorithm)‘이라고 불렀다. 60여 년 전의 특허가 오늘날 하드디스크와 엘리베이터 수로에서 동시에 작동하고 있는 셈이다. 단순한 규칙의 수명은 대부분의 현대 소프트웨어보다 길다.
하지만 단일 엘리베이터 규칙만으로는 아침 출근길 혼잡을 해결할 수 없다. 오전 9시 오피스 빌딩을 상상해보자. 수백 명이 동시에 1층 로비에서 상행 버튼을 누른다. 시스템이 미련하게 모든 엘리베이터를 로비로 보낸다면, 세 대가 동시에 문을 열고 빈 상태로 함께 올라가는 비효율이 발생한다. 배차 시스템은 때로는 ‘비합리적’으로 보이는 행동을 해야 한다. 빈 엘리베이터를 돌려서 다른 쪽 승객을 태우러 보내는 식이다. 15층에서 버튼을 눌렀는데 엘리베이터가 그냥 지나쳐 간다면, 내 호출을 못 들은 것이 아니라 나보다 더 큰 전체 최적화 계획을 수행하고 있는 중이다.
그림: 원문 메인 페이지의 인터랙티브 시연—4층 건물에서 엘리베이터 1대가 왕복하며, 25배속으로 시청 가능. 출처: john.fun
복수 엘리베이터의 분업: 5초마다 다시 점수 매기기
엘리베이터 수가 늘어나면 문제는 본격적으로 어려워진다. “누가 누구를 태우러 갈 것인가?”
현대 엘리베이터 군관리 시스템(예: 오티스의 RSR 알고리즘)은 점수 제도를 활용한다. 각 엘리베이터마다 예상 도착 시간, 현재 탑승 인원, 다른 엘리베이터와의 쏠림 현상, 진행 방향, 근처 대기 여부 등을 종합해 ‘배차 점수’를 산출하고, 비용이 가장 낮은 엘리베이터를 지정한다. 이 시스템의 묘미는 취소와 재계산에 있다. 5초마다 건물 전체 상황을 다시 계산하여, 지정된 엘리베이터가 도중에 지연되면 다른 엘리베이터로 요청을 넘긴다.
John의 시뮬레이션은 직관에 반하는 결론을 제시한다. 혼잡도가 매우 높을 때는 복잡한 RSR보다 단순한 LOOK 규칙이 오히려 더 뛰어난 성능을 발휘한다는 점이다. 건물이 작거나 엘리베이터 수가 적을 때도 단순한 규칙이 유리하다. “때로는 단순함을 유지하는 것이 가장 좋다”라는 명료한 진리가 이 글 전체에서 가장 가치 있는 통찰이다.
스마트 배차 시스템: 정보가 많을수록 오히려 더 느리다?
최근 고급 오피스 빌딩에서는 새로운 방식인 ‘목적층 등록 시스템(Destination Dispatch)‘이 유행하고 있다. 엘리베이터에 타기 전 로비 화면에서 가고자 하는 층을 먼저 선택하면 화면에 “3호기를 이용하세요”라고 안내해준다. 언뜻 들으면 훨씬 스마트해 보인다. 탑승 전에 모든 사람의 목적지를 알 수 있으니 더 완벽하게 배치할 수 있지 않을까?
하지만 시뮬레이션 결과는 반대였다. 대부분의 상황에서 목적층 등록 시스템의 평균 대기 시간은 기존의 ‘상하 버튼’ 방식보다 나빴다. 이 시스템이 이기는 유일한 조건은 초고층 건물에서 8대 이상의 엘리베이터가 그룹으로 작동할 때뿐이다. 이유는 명확하다. 기존 시스템이 가지고 있던 ‘5초마다 유연하게 재최적화하는 능력’이 화면에서 “지정된 호기를 타라”고 안내하는 순간 고정되어 버리기 때문이다. 버튼을 누른 지 30초 뒤 건물 내 상황이 바뀌어도 시스템은 할당을 변경할 수 없다.
Lobsters의 엔지니어들도 현장의 불만을 공유했다. vbernat이라는 사용자는 목적층 등록 시스템이 모든 사람이 화면에 층을 제대로 입력해야 작동하는데, 조급한 사용자가 여러 번 누르는 바람에 한 층에 엘리베이터 두 대가 동시에 배치되는 문제가 발생한다고 지적했다. Flask 프레임워크 작성자인 mitsuhiko는 실제로 엘리베이터를 잘못 타거나 놓치는 경우가 흔하다고 덧붙였다. 반면 출입 카드와 연동되어 카드를 대는 순간 탑승할 엘리베이터를 알려주어 아침 출근길이 매우 빨라진다는 긍정적 경험도 있다. 하지만 그 대가로 퇴근길 하행 엘리베이터를 몇 분씩 기다려야 한다. 시스템이 아침 출근길 최적화에 모든 자원을 쏟아부었기 때문이다.
여기서 깊이 생각해볼 점이 있다. 시스템에 더 많은 정보를 제공하는 것이 곧 그 정보를 제대로 활용할 수 있음을 의미하지는 않는다. 시스템 전체의 최적해는 “내 층에 엘리베이터가 먼저 오길 바라는” 개인의 욕구와 자주 충돌한다. 알고리즘의 계산서에서 개인의 1분과 건물 전체 승객들의 통합된 시간은 전혀 다른 가치를 지닌다.
왜 항상 늦게 느껴질까: 대기 시간의 심리학
마지막으로 흥미로운 사실 하나를 소개한다. 엘리베이터 회사는 오래전부터 ‘체감 대기 시간’을 연구해 왔다. 심리학에 따르면 기다리는 시간이 지루할수록 시간은 더 천천히 간다. 고전적인 해결책은 엘리베이터 승강장 옆에 대형 거울을 설치하는 것이었으며, 많은 건물 관리자가 이를 도입해 상당한 효과를 거두었다. 엘리베이터를 기다릴 때 느끼는 초조함의 절반은 알고리즘 탓이지만, 나머지 절반은 뇌가 스스로 만들어낸 것이다.
또한 해소되지 않는 의문이 하나 있다. 엘리베이터의 상행과 하행 횟수는 동일할 텐데, 왜 항상 반대 방향으로 가는 엘리베이터만 먼저 눈에 띌까? 답의 일부는 혼잡 시간에 있다. 사람이 가득 찬 엘리베이터는 정원 초과로 중간 층을 정차 없이 그냥 지나친다. 뇌가 기억하는 것은 항상 내 앞을 쌩하고 지나쳐 간 정원 초과 엘리베이터인 셈이다.
처음 질문으로 돌아가 보자. “엘리베이터가 내 버튼 소리를 들었을까?” 들었다. 다만 수백 명의 목적지, 탑승 정원, 에너지 소비, 공정성을 고려해 5초마다 다시 계산하느라 바쁠 뿐이다. 다음에 엘리베이터를 기다릴 때 다른 곳으로 먼저 가더라도, 건물 전체를 위해 전체 최적화를 수행 중인 분산 제어 시스템이라고 생각해보자. 그 알고리즘의 장부에는 나의 1분과 건물 전체 사람들의 시간이 함께 기록되어 있다.
참고 링크:
- John Allsopp: Elevators (인터랙티브 가이드)
- Lobsters 토론 (s/jxqf1w/elevators)
- 위키백과: Elevator algorithm
- Signal v. Noise: Defining the problem of elevator waiting times
- Scientific American: The reason why elevators feel slow
