Walk-In Multi-Stage Patient Flow Scheduling: An ASP Model with DES-Based Evaluation

技術要約：ウォークイン型多段階患者フロー・スケジューリング

問題の定式化
本論文は、ベトナムのような発展途上国で一般的なマルチデパートメント（多部門）設定における、ウォークイン型の病院環境を対象としたリアクティブ・スケジューリング問題を扱っている。予約制のシステムとは異なり、患者は事前に予約されたスロットを持たずに到着し、一度の受診中に異なる部門にわたる一連の複数の検査を受ける必要がある。核心となる課題は、各到着患者に対して、検査の順序と検査室の割り当ての両方を決定する実行可能な検査経路を動的に計算することである。

この問題は以下の制約を受ける：

1. 医学的前置関係： 特定の検査は他の検査の前に行われなければならない。
2. 部屋の容量： 検査室における限定されたスロット。
3. 移動時間： 部門間を移動するために必要な時間。
4. 動的な状態： スケジューラーは、現在の待ち行列の長さおよび過去にスケジュールされた患者の活動を考慮しなければならない。

目的は、2部構成のコスト関数、すなわち待ち時間（検査時間によって重み付けされたキューによる遅延）と、連続する場所間の移動時間を最小化することである。最適化は、移動時間よりも待ち時間の削減を優先するレキシコグラフィック（辞書式）なものである。

手法
著者らは、宣言的最適化と確率的シミュレーションを組み合わせたハイブリッド・フレームワークを提案している。

1. 回答集合プログラミング（ASP）モデル：

   • 問題は clingo を用いて宣言的にモデル化されている。
   • ハード制約： すべての必須検査が正確に一度だけ割り当てられ、部屋が検査タイプと一致し、医学的前置関係が遵守されることをモデルが強制する。
   • 最適化： 弱い制約（weak constraints）を用いて、待ち時間（第一優先）と移動コスト（第二優先）を最小化する。
   • リアクティブ・メカニズム： ソルバーは各患者の到着時にトリガーされる。現在の病院の状態（推定される待ち行列や過去のスケジュールを含む）を入力として受け取り、最適な経路を計算し、システムの状態（具体的には hist パラメータ）を次の到着に向けて更新する。
   • 待ち行列の推定： 求解ステップにおいて完全なシミュレーションを行わずに動的な待ち行列を扱うため、ASPモデルはスループットに基づく公式を用いて、将来の時間 $t$ における待ち行列を近似する：$Queue(t) \approx \max(0, \text{InitialQueue} + \text{ScheduledArrivals}(t) - \text{Capacity} \times t / \text{AvgDuration})$。

2. 離散イベントシミュレーション（DES）による評価：

   • ASPモデルは決定論的な仮定と推定された待ち行列に依存しているため、著者らは生成されたスケジュールの頑健性を、確率的なサービス時間および到着の下で評価するためにDESレイヤーを採用している。
   • DESは、患者の実際のフローをシミュレートし、「到着（Arrival）」や「開始（Start）」といったイベントを処理し、スロットが利用不可能な場合にはイベントを再キューイングすることで、総滞在時間や待ち時間ゼロ率などのパフォーマンス指標の現実的な評価を提供する。

3. ベースライン：

   • DES (Greedy/貪欲法)： 現在の状態に基づき、将来の混雑を予測することなく、最も早い利用可能スロットに患者を割り当てるリアクティブ戦略。
   • DES-F (Future Estimation/将来推定)： ASPモデルと同様に、可用性を予測するために将来の待ち行列推定を組み込んだ、貪欲法ベースラインの拡張版であり、最適化コンポーネントに対してより公平な比較を提供するためのものである。

主な貢献

• 新規の定式化： 検査の順序付けと部屋の割り当てを共同で最適化し、検査経路をリアクティブに決定するマルチステージ・ウォークイン経路のための新しい定式化を提供した。これは、これらを別々に扱うか、あるいは予約制システムに焦点を当てることが多い既存の文献におけるギャップを埋めるものである。
• レキシコグラフィック最適化を備えたASPエンコーディング： 待ち時間の最小化を移動コストよりも優先する効率的なASPモデルであり、大規模なグラウンディングサイズに対しても0.1秒未満で問題を解くことができる。
• DESベースの評価フレームワーク： 宣言的最適化をシミュレーションと統合し、確率的な条件下でのパフォーマンスを評価する手法を提供することで、理論的な最適性と運用の現実との間の溝を埋めている。
• 実証的検証： ベトナムの病院パラメータから派生した合成データセットを用いた大規模な実験により、様々な容量レジームおよび患者負荷における本アプローチの有効性を実証した。

実験結果
著者らは、100人から650人の患者と、20%から72%の変動する利用率をテストする合成データセットを用いて、本アプローチを評価した。

• ベースラインとの比較： ASPアプローチは、中央値患者滞在時間および待ち時間ゼロの患者の割合の両方において、DESおよびDES-Fベースラインを一貫して上回った。
• 負荷の影響： 改善は高利用率（重負荷）の条件下で最も顕著であった。例えば、400人の患者がいる低容量シナリオでは、ASPはベースラインと比較して中央値滞在時間を大幅に短縮し、待ち時間ゼロ率を（DESの5.0%、DES-Fの6.0%に対し）6.5%に向上させた。
• スケーラビリティ： ソルバーは、患者数が増加しても計算効率を維持した（平均実行時間 < 0.1秒）。高容量シナリオでは、リソースの制約が緩和されるためパフォーマンスの差は縮まったが、ASPは依然として優れた、あるいは同等の指標を維持しており、特に「未完了」の患者（10時間のウィンドウ内に検査を完了できなかった患者）の数を減らすことに貢献した。
• 安定性： ASPアプローチは、ルーティングの柔軟性により、固定順序のDES-Fと比較して滞在時間の四分位範囲（IQR）がわずかに広くなる傾向があったが、標準的な貪欲法DESよりも予測可能な体験を提供し、一貫して総滞在時間を最適化した。

意義と主張
本論文の主な意義は、リアルタイムの意思決定支援が欠如していることが多いウォークイン型のヘルスケア環境に対し、柔軟な意思決定支援フレームワークを提供することにある。シーケンシング、リソース配分、および空間的ルーティングをリアクティブなフレームワーク内で統一することにより、本アプローチは、従来の予約制モデルが見落としがちなマルチステージの患者フローの複雑さに対処している。

著者らは、ASPモデルが決定論的な仮定の下で最適化を行っていることを控えめに述べているが、DESとの統合により、運用のパフォーマンスに関する現実的な評価が可能になっている。また、制限事項として、合成データ（マイクロレベルの病院ログのプライバシー制限による）の使用、部屋内での先着順（First-Come-First-Served）サービスの仮定（患者の緊急度や重症度を無視）、および各検査完了後の再最適化の欠如を挙げている。しかし、結果は、宣言的最適化（ASP）が、動的なウォークイン環境における病院のリソース管理と患者フローを改善するための、実行可能かつ効果的な手法であることを示唆している。