Constant-Factor Algorithms for Revenue Management with Consecutive Stays

あなたは、賑わう駅や人気のホテルチェーンのマネージャーだと想像してください。毎日、何千人もの人々がやってきて、特定の期間、座席や客室を予約したいと考えています。行程のすべてを希望する人もいれば、数駅分だけを希望する人もいます。問題は、利用可能な座席や客室には限りがあり、一度誰かに割り当てると、その特定の時間枠ではもう使えなくなるということです。これが「ネットワーク収益管理（Network Revenue Management）」の本質です。つまり、後から来る高額な顧客のために在庫を使い果たさないように、「イエス」と言うべきか「ノー」と言うべきかを判断する技術です。

数学やコンピュータサイエンスの世界において、これは古典的なパズルです。通常、これを解く最善の方法は、将来のすべてを見渡し、誰がいつ来るかを正確に把握した上で、完璧なスケジュールを計画することです。しかし、現実世界では未来を見通すことはできません。目の前に現れる顧客一人ひとりに対応しながら、即座に判断を下さなければなりません。これは「オンライン問題」と呼ばれます。長年、数学者たちは、たとえ将来が分からなくても、一定の利益を確実に確保できるシンプルで高速なルールを見つけ出そうと苦心してきました。大きな疑問は、「予約の期間がどれほど長くても、あるいは顧客がいかにトリッキーであっても、常に『十分に良い（最適解の一定割合となる）』結果を保証できる戦略を見つけられるか？」という点でした。

ミン・フー（Ming Hu）とトンウェン・ウー（Tongwen Wu）によるこの論文は、まさにその問いに取り組んでいます。彼らは、顧客の振る舞いにおける2つの異なるシナリオを検討しています。最初のシナリオは電車のチケットのようなものです。乗客を受け入れて特定の座席を割り当てるか、あるいは拒否するか、どちらかです。2つ目のより複雑なシナリオは、ブティックホテルやAirbnbのようなものです。あなたは顧客に利用可能な客室のメニューを提示し、顧客は自分の好みに基づいて最も気に入ったものを選びます。著者らは、これらの状況に対処するための新しい高速なコンピュータ・アルゴリズムを開発しました。彼らは、単純な電車のチケット形式の場合、彼らの手法が「完璧な未来を知るプランナー」が得る収益の少なくとも**63.2%を数学的に保証することを証明しました。顧客が選択肢を持つ場合、その保証は27.1%**に下がります。滞在期間がランダムで予測不可能な場合でも、彼らのアルゴリズムは依然として堅実な収益の塊を確保することができ、未来を予知できなくても、適切な数学さえあれば収益性の高いビジネスを運営できることを証明しています。

失われた座席のパズル

この問題を、形が変わり続ける巨大な動的なジグソーパズルのようなものだと考えてください。「受諾または拒絶（Accept-or-Reject）」の世界（電車の例）では、乗客が駅から駅までの座席を求めてくるたびに、あなたは即座に決断を下さなければなりません。「座席101を割り当てるべきか？ それとも、後で来るかもしれない人のために取っておくべきか？」もし早すぎる段階で渡してしまえば、団体予約を逃してしまうかもしれません。逆に、抱え込みすぎれば、座席を永遠に空席にしてしまうかもしれません。

著者らは、未来を予測しようとする代わりに、「流体緩和（fluid relaxation）」と呼ばれる巧妙なトリックを使うことができると気づきました。座席を固形ブロックではなく、流れる液体としてイメージしてみてください。確率に基づいて、異なるタイプの旅行者のためにどれだけの「液体の」座席を予約すべきかを計算します。そして、彼らは「プロポーザル・ディスカーディング（提案・破棄）」アルゴリズムを構築しました。その仕組みを平易な言葉で説明すると、以下の通りです。

顧客がカウンターにやってくる前に、コンピュータは「もしも」のシナリオをシミュレーションします。「もしこのタイプの顧客が現れたら、あなたはその席を受け入れますか？」と、利用可能なすべての座席に問いかけます。各座席は、数学的根拠に基づいたコイン投げを行い、手を挙げるかどうかを決めます。複数の座席が手を挙げた場合、コンピュータは最も利益を生む座席を選びます。もし誰も手を挙げなかった場合、その顧客は丁寧に断られます。

しかし、ここには魔法のような仕掛けがあります。たとえある座席が実際の顧客に対して選ばれなかったとしても、コンピュータはそれが「使用された」と仮定します。つまり、内部シミュレーションにおいて、その座席を「使用中」としてマークするのです。これにより、計算の整合性を保ち、システムが強欲になりすぎるのを防ぎます。この「仮想的な使用中」ステータスにより、アルゴリズムが計算上で座席を二重予約してしまうミスを防ぎ、確率の独立性と計算の解決可能性を維持します。

顧客が選択する場合

論文の後半部分は、そこに「人間の選択」が加わるため、さらに面白くなります。客室を単に割り当てるのではなく、ゲストに3つの選択肢（景色の良い部屋、バルコニー付きの部屋、安価な部屋）を提示するホテルを想像してください。ゲストは、自分が最も好むものを選びます。これが「BAMベース（基本吸引モデル：Basic Attraction Model）」のシナリオです。

これは、ゲストの選択が提示されたリスト全体に依存するため、より困難です。豪華な部屋を見せれば、彼らはそれを選ぶかもしれません。豪華な部屋と安い部屋の両方を見せれば、安い方を選ぶかもしれません。著者らは、コンピュータの「仮想的な」選択と、ゲストの「現実の」選択を結びつける新しい方法を考案する必要がありました。彼らは「ランダム化結合（randomized coupling）」という手法を用いました。これは手品のようなものです。コンピュータは、ゲストの選択がコンピュータの計画と数学的に一致することを保証するように、提示する部屋のランダムなリストを生成しますが、ゲスト自身は自由な意思で選択を行います。

彼らは、この選択が複雑さを増すものの、アルゴリズムは依然として機能することを見出しました。「メニュー」形式のシナリオでは、彼らのポリシーが最適収益の少なくとも27.1%を確保することを証明しました。滞在期間もランダムである場合（例えば、ゲストが「2日間かもしれないし、5日間かもしれない」と言う場合）、保証は少し下がりますが、依然としてプラスの値を維持しています。メニュー形式では17.1%、単純な電車のケースでは**39.9%**となります。

なぜこれが重要なのか

この論文が登場する前、この種の課題に対する保証は非常に弱いものでした。それらは予約の長さに依存していました。もし人々が長期旅行を予約する場合、その保証はほぼゼロにまで縮小してしまいます。それは、「私たちの戦略は素晴らしいですが、1ヶ月間の滞在になると使い物になりません」と言っているようなものです。

著者らは、これは事実ではないことを示しました。彼らは「定数倍（constant-factor）」の保証が可能であることを証明しました。これは、滞在期間がどれほど長くても、リソースがどれほど多くても、あなたの戦略は常に、最適解の一定の健全な割合を確実に捉えられることを意味します。また、単純なケースにおいては**63.2%**以上に到達することは難しいことも示しており（これは100%に近づけることが「困難」であることを証明しています）、彼らの解決策が、私たちが期待しうる最善の答えに極めて近いものであることを示しています。

要約すれば、彼らは、乱雑で予測不可能な現実世界の課題を取り上げ、それに強固な数学的基盤を与えました。適切なアルゴリズムがあれば、完璧である必要はなく、単に「イエス」と言うべき時、「ノー」と言うべき時、そして損失を出さずに顧客に選択させる方法を知っていれば、利益を上げられるのだということを彼らは示したのです。