Constant-Factor Algorithms for Revenue Management with Consecutive Stays

당신이 북적이는 기차역이나 유명한 호텔 체인의 매니저라고 상상해 보십시오. 매일 수천 명의 사람들이 나타나 특정 시간 동안 좌석이나 객실을 예약하고 싶어 합니다. 어떤 이들은 전체 여정을 원하고, 어떤 이들은 단 몇 정거장만을 원합니다. 문제는 당신이 가진 좌석이나 객실의 수가 한정되어 있다는 것입니다. 일단 하나를 내주면, 그 특정 시간대에는 더 이상 사용할 수 없습니다. 이것이 바로 **네트워크 수익 관리(Network Revenue Management)**의 핵심입니다. 즉, 나중에 도착할 큰 손들을 위해 재고를 남겨두면서도 최대한의 수익을 올리기 위해, 누구에게 "예"라고 말하고 누구에게 "아니오"라고 말할지를 결정하는 기술입니다.

수학과 컴퓨터 과학의 세계에서 이것은 고전적인 퍼즐입니다. 보통 이를 해결하는 가장 좋은 방법은 미래 전체를 들여다보고, 누가 언제 도착할지 정확히 알며, 그 후에 완벽한 일정을 계획하는 것입니다. 하지만 현실 세계에서는 미래를 볼 수 없습니다. 당신은 고객이 올 때마다, 즉 다음에 누가 올지 모르는 상태에서 즉각적으로 결정을 내려야 합니다. 이를 "온라인(online)" 문제라고 부릅니다. 오랫동안 수학자들은 미래를 알지 못하더라도 당신이 꽤 괜찮은 수익을 올릴 수 있도록 보장하는 간단하고 빠른 규칙을 찾는 데 어려움을 겪어 왔습니다. 핵심 질문은 이것이었습니다. "예약 기간이 얼마나 길든, 혹은 고객들이 얼마나 까다롭든 상관없이, 우리가 '충분히 좋은'(최적의 결과 대비 일정한 비율을 달하는) 성과를 낼 수 있는 전략을 찾을 수 있을까?"

Ming Hu와 Tongwen Wu의 이 논문은 바로 그 문제를 다룹니다. 저자들은 두 가지 서로 다른 고객 행동 시나리오를 살펴봅니다. 첫 번째 시나리오는 기차표와 같습니다. 승객을 받아들여 특정 좌석을 배정하거나, 아니면 거절해야 합니다. 두 번째는 더 복합적인 시나리오로, 부티크 호텔이나 에어비앤비와 같습니다. 고객에게 이용 가능한 객실 목록(메뉴)을 보여주면, 고객은 자신의 선호도에 따라 가장 마음에 드는 것을 선택합니다. 저자들은 이러한 상황들을 처리하기 위한 새로운, 빠른 컴퓨터 알고리즘을 개발했습니다. 그들은 자신들의 방식이 단순한 기차표 사례의 경우, 미래를 아는 완벽한 기획자가 벌어들일 수익의 최소 **63.2%**를 보장한다는 것을 수학적으로 증명했습니다. 고객이 메뉴를 보고 선택하는 경우, 이 보장 수치는 **27.1%**로 떨어집니다. 숙박 기간이 무작위적이고 예측 불가능할 때조차도, 그들의 알고리즘은 여전히 견고한 수익의 일부를 확보해 냄으로써, 수익성 있는 사업을 운영하기 위해 예지력이 필요한 것이 아니라 적절한 수학이 필요하다는 것을 입증했습니다.

사라진 좌석의 퍼즐

이 문제를 형태가 계속 변하는 거대한 조각 맞추기 퍼즐이라고 생각해 보십시오. "수락 또는 거절(Accept-or-Reject)"의 세계(기차 예시)에서는, 승객이 A 역에서 F 역까지의 좌석을 요청할 때마다 당신은 즉시 결정해야 합니다. "좌석 101호를 줄 것인가? 아니면 나중에 올지도 모를 누군가를 위해 아껴둘 것인가?" 만약 너무 빨리 좌석을 내준다면, 나중에 올 큰 규모의 단체 예약을 놓칠 수 있습니다. 반대로 너무 꽉 쥐고 있다면, 좌석을 영원히 비워둔 채로 있게 될 수도 있습니다.

저자들은 미래를 예측하는 대신, "유체 완화(fluid relaxation)"라는 영리한 트릭을 사용할 수 있다는 점을 깨달았습니다. 좌석이 딱딱한 블록이 아니라 흐르는 액체라고 상상해 보십시오. 확률에 기반하여 서로 다른 유형의 여행객들을 위해 얼마나 많은 "액체" 좌석을 예약해야 하는지 계산합니다. 그런 다음, 그들은 "제안-폐기(Proposal-Discarding)" 알고리즘을 구축했습니다. 이것이 영어로 어떻게 작동하는지 쉽게 설명하자면 다음과 같습니다.

고객이 카운터에 오기도 전에, 컴퓨터는 "만약의 상황"을 시뮬레이션합니다. 컴퓨터는 사용 가능한 모든 좌석에 대고 묻습니다. "만약 이 유형의 고객이 나타난다면, 당신은 그들을 받아들일 용의가 있습니까?" 각 좌석은 수학적 계산에 따라 동전을 던져 손을 들지 여부를 결정합니다. 만약 여러 좌석이 손을 든다면, 컴퓨터는 가장 많은 돈을 벌어다 줄 좌석을 선택합니다. 만약 아무도 손을 들지 않는다면, 고객은 정중하게 거절됩니다.

하지만 여기 마법 같은 반전이 있습니다. 설령 어떤 좌석이 실제 고객을 위해 선택되지 않았더라도, 컴퓨터는 그 좌석이 "사용된 것"처럼 간주합니다. 이는 내부 시뮬레이션에서 해당 좌석을 "사용 중(busy)"으로 표시하는 것입니다. 이는 계산의 정직함을 유지하고 시스템이 지나치게 탐욕스러워지는 것을 방지합니다. 이 "가상 사용 중(virtual busy)" 상태는 알고리즘이 계산 과정에서 실수로 좌석을 중복 예약하지 않도록 하여, 확률의 독립성을 유지하고 수학적 해결이 가능하도록 만듭니다.

고객이 직접 선택할 때

논문의 두 번째 부분은 인간의 선택이라는 요소가 추가되어 훨씬 더 흥えます. 당신이 단순히 방을 배정하는 것이 아니라, 투숙객에게 전망이 좋은 방, 발코니가 있는 방, 혹은 더 저렴한 방 등 세 가지 옵션을 보여주는 호텔을 상상해 보십시오. 투숙객은 그중 자신이 가장 좋아하는 것을 고릅니다. 이것이 "BAM 기반(Basic Attraction Model)" 시나리오입니다.

이것이 더 어려운 이유는 투숙객의 선택이 당신이 보여주는 전체 목록에 달려 있기 때문입니다. 만약 당신이 화려한 방을 보여준다면, 그들은 그것을 선택할 수 있습니다. 하지만 화려한 방과 저렴한 방을 함께 보여준다면, 그들은 저렴한 방을 선택할 수도 있습니다. 저자들은 컴퓨터의 "가상" 선택과 고객의 실제 선택을 연결하는 새로운 방법을 고안해야 했습니다. 그들은 "무작위 결합(randomized coupling)"이라는 기술을 사용했습니다. 이것은 마치 마술사의 기술와 같습니다. 컴퓨터는 고객에게 제안할 무작위 목록을 생성하지만, 고객이 자유로운 선택을 하더라도 그 선택이 컴퓨터의 계획과 수학적으로 일치하도록 보장하는 방식으로 수행합니다.

그들은 이러한 선택이 복잡성을 더하지만, 그럼에도 불구하고 알고리즘이 작동한다는 것을 발견했습니다. "메뉴" 시나리오에서, 그들의 정책이 최적 수익의 최소 **27.1%**를 벌어들인다는 것을 증명했습니다. 숙박 기간 또한 무작위라면(예를 들어, "2일 머물 수도 있고, 5일 머물 수도 있다"라고 말하는 경우), 보장 수치는 조금 더 낮아지지만 여전히 양수 값을 유지합니다. 메뉴 시나리오에서는 17.1%, 단순한 기차 시나리오에서는 **39.9%**입니다.

이것이 왜 중요한가

이 논문이 나오기 전, 이러한 종류의 문제에 대한 최선의 보장 수치는 매우 취약했습니다. 그것들은 예약 기간에 따라 달라졌습니다. 만약 사람들이 매우 긴 여행을 예약한다면, 그 보장 수치는 거의 0에 가깝게 줄어들었습니다. 이는 마치 "우리의 전략은 훌륭합니다. 다만 당신이 한 달 동안 머문다면, 그 전략은 쓸모없어집니다"라고 말하는 것과 같았습니다.

저자들은 이것이 사실이 아님을 보여주었습니다. 그들은 "상수 인자(constant-factor)" 보장이 가능하다는 것을 증명했습니다. 이는 숙박 기간이 얼마나 길든, 자원이 얼마나 많든 상관없이, 당신의 전략이 항상 최적의 수익 중 일정하고 건강한 비율을 확보할 수 있음을 의미합니다. 또한 그들은 단순한 사례의 경우 63.크보다 더 높게 도달하는 것이 어렵다는 점을 보여줌으로써(즉, 100%에 가깝게 만드는 것이 "어렵다"는 것을 증명함), 자신들의 솔루션이 우리가 기대할 수 있는 최선의 답에 매우 근접해 있다는 것을 입증했습니다.

요약하자면, 그들은 무질서하고 예측 불가능한 현실 세계의 문제를 견고한 수학적 토대로 바꾸어 놓았습니다. 그들은 적절한 알고리즘이 있다면 완벽할 필요는 없으며, 단지 언제 "예"라고 하고, 언제 "아니오"라고 할지, 그리고 고객이 스스로 선택하게 하면서도 손해를 보지 않는 법을 아는 것이 중요하다는 것을 보여주었습니다.