A Computational Method for Solving the Stochastic Joint Replenishment Problem in High Dimensions

技術概要：高次元における確率的共同発注問題の解決のための計算手法

問題定式化
本論文は、古典的な在庫管理課題である確率的共同発注問題（SJRP）を取り扱っている。これは、一緒に注文された品目に共通して固定発注コストが発生する多品目在庫システムの調整を伴う課題である。検討されている離散時間定式化において、倉庫管理者は定期的に在庫レベルを点検し、$d$ 個の品目の部分集合に対して注文を行うかどうかを決定する。システムは、ランダムな需要、線形保有コスト、および遅延ペナルティに直面する。目的は、無限時間 horizon における総期待割引コストを最小化することである。

核心的な難しさは「次元の呪い」にある。非ゼロの固定発注コストの下では、品目レベルの決定が相互依存となり、関連するマルコフ決定過程（MDP）の状態空間と決定空間が品目数（$d$）とともに指数関数的に増大する。その結果、標準的な動的計画法手法は高次元設定（例えば $d \ge 50$）において計算的に扱い不可能となり、既存の文献は最適性に関する理論的保証が限定的なヒューリスティック方策に大きく依存してきた。

手法
これらの計算上の障壁を克服するため、著者らは離散時間在庫制御と連続時間インパルス制御理論および深層学習を橋渡しする、新規のシミュレーションベースの計算手法を提案する。

1. 連続時間近似: 離散時間 SJRP は、連続時間インパルス制御問題によって近似される。この定式化において、累積需要過程はガウス過程（ドリフト付きブラウン運動）としてモデル化され、管理者は任意の時点で介入して、固定コストを支払うことで在庫状態を即座に高いレベルへジャンプさせることができる。この近似により、高次元解法に適した値関数の確率的表現が可能となる。

2. 制約付き BSDE による確率的表現: ほぼ確定的な等式に依存する標準的な深層 Backward Stochastic Differential Equation（BSDE）手法とは異なり、このインパルス制御問題の値関数は、制約付き BSDE の最小解として特徴づけられる。これにより、等式ではなく、ほぼ確定的な不等式を含む確率的恒等式が導かれる。具体的には、値関数 $V(x)$ は、参照過程、進行コスト、およびジャンプコストを含む確率的ターゲット条件を満たす値 $v$ の上限（supremum）である。

3. 深層ニューラルネットワークソルバ: 著者らは、この制約付き BSDE を深層ニューラルネットワークを用いて解くための計算アルゴリズムを開発した。

   • 損失関数: 不等式制約を処理するための新規の損失関数が構築された。これには、確率的不等式の違反に対するペナルティ項が含まれ、調整可能なペナルティパラメータ $\beta$ によって重み付けられる。
   • 参照過程: 慎重に設計された参照方策（ポアソン過程によって駆動されるランダム化されたオーダーアップトゥ方策）が、サンプル経路を生成するために用いられる。この過程は、探索と利用のバランスを取るよう設計されており、ニューラルネットワークが状態空間の関連領域で訓練されることを保証する。
   • 訓練戦略: 安定性を確保するため、著者らはペナルティパラメータ $\beta$ と学習率の共同スケジュールを採用する。ペナルティは徐々に増加させ、学習率は減少させることで、ネットワークがまず一般的な構造を学習し、その後、不等式制約を厳密に実行できるようにする。

4. 方策の抽出: 値関数 $V$ とその勾配 $\nabla V$ がニューラルネットワークによって近似されると、実装可能な方策が導き出される。この方策は、ハミルトン・ヤコビ・ベルマン（HJB）方程式から導かれた「非行動」条件をチェックする。条件が違反された場合、注文が行われる。オーダーアップトゥベクトルは、近似された値関数と注文コストの和を最小化することで決定され、このステップは効率的に事前計算可能である。

主要な貢献

• 高次元スケーラビリティ: この手法は、少なくとも 50 次元（50 SKU）までの SJRP を成功裡に解決し、従来の MDP ベースの最適解が扱い不可能となる領域をカバーする。
• 新規損失設計: 本論文は、インパルス制御に必要な制約付き BSDE フレームワークに特化した特定の損失関数と訓練スケジュールを導入し、標準的な深層 BSDE 手法では処理できないほぼ確定的な不等式の課題に対処する。
• 参照過程の設計: 状態依存ジャンプを備えた参照過程の設計は、効率的な訓練と関連する状態空間のカバレッジを確保するための重要な革新として強調されている。
• 実装: 著者らは、問題の近似から方策の抽出までの完全なパイプラインを提供し、詳細なハイパーパラメータ調整戦略と計算結果を含んでいる。

結果
提案されたニューラルネットワーク（NN）方策は、次元 2、12、および 50 にまたがる 43 のテスト問題において、変動する需要変動性（低、中、高）およびコスト構造で評価された。

• 低次元（$d=2$）: NN 方策は、標準的な MDP 解法手法から導かれた真の最適方策と比較された。結果、NN 方策は最適コストの 1% 以内で動作し、最適決定境界の幾何学的特徴を密に追跡することが示された。
• 高次元（$d=12$ および $d=50$）: 最適解が扱い不可能であるため、NN 方策は最先端のヒューリスティック、すなわち定期レビュー $(R, S)$、$(Q, S)$、ハイブリッド $(R, Q, S)$、キャノンダー、および独立 $(s, S)$ 方策に対してベンチマークされた。
  • 12 次元では、NN 方策はすべてのケースで最良のベンチマークと同等かそれ以上の性能を示した。中程度および高変動性の設定では、最良のヒューリスティックを大幅に上回る場合が多く（例えば、特定の高変動性ケースにおいて $(R, S)$ に対して最大 28% の改善）、顕著な差を付けた。
  • 50 次元では、NN 方策はすべてのテストケースにおいて利用可能な最良のヒューリスティックを一貫して凌駕し、性能差は最大 5.59% に達した。
• 計算効率: 訓練時間は次元に対して穏やかにスケーリングする（例えば、単一 GPU 上で 50 次元で約 4 時間）ため、グリッドベースの手法に典型的な指数関数的増大を回避している。

意義と主張
本論文は、その手法がオペレーションズ・マネジメントにおける長年の課題である高次元確率的共同発注問題に対する準最適方策を計算的に実行可能に提供すると主張している。深層学習を活用して基礎となる高次元インパルス制御問題を解くことで、著者らは、制限的な構造的仮定に依存することなく、既存の最良のヒューリスティックと同等かそれ以上の性能を達成可能であることを実証している。著者らは、この手法が現在、線形コストおよび制約のない注文ベクトルを伴う SJRP に適用されているが、このフレームワークは財務工学（例えば、キャッシュフロー管理）やリードタイムや欠損販売を伴うサプライチェーンなど、他のインパルス制御問題にも一般化可能であると指摘している。ただし、これらの拡張は将来の課題として残されている。本論文は、提案された方策が単なるヒューリスティックではなく、厳密な確率的定式化から導かれた最適制御のデータ駆動型近似であることを強調している。