2021/3/4 Paul Brown / Emily Murphy 共著
（本記事はOptaPlannerに投稿された記事の日本語訳になります。オリジナルはこちら） https://www.optaplanner.org/blog/2021/03/04/OptimizingCovid19VaccinationScheduling.html
COVID-19の予防接種の予約は世界的な課題となっています。予防接種の対象となる人々は、何度も予約を試みているにもかかわらず予約を確保できていません。予防接種を受ける予定の人が予防接種センターに到着して初めて、予約がキャンセルされたことを知ることもあります。また、同じ時間帯に何百人もの人が並んでいて何時間も待たされることもあります。しかし、そのようなことにならないようにすることができます。OptaPlannerの予防接種予約スケジューラークイックスタートを使えば、効率的かつ公平なスケジュールを組むことができます。予防接種予約スケジューラーは人工知能（AI）を使用して、複数の制約や優先順位に基づいて人々に優先順位を付け、時間枠を割り当てます。これは、GitHubで公開されているOptaPlannerのクイックスタート・コレクションの一部です。
OptaPlannerの予防接種予約スケジューリングのビデオもあります。続きをお読みください。
予約計画システムの自動化の利点
予約の計画には、大きく分けて2つのアプローチがあります。システムがユーザーに予約の枠を選択させる方法（ユーザーが選択）と、システムが枠を割り当て、ユーザーにいつどこに行けばいいかを伝える方法（システムが自動的に割り当てる）です。
この2つのアプローチを簡単に比較してみましょう。
ユーザーが選択する場合
この方法は、Ticketmaster™などのコンサートチケットサイトで採用されている方法と似ています。ほとんどのコンサートチケットは、この方法で販売されています。人々は、一定の数のチケットや予約をめぐって互いに競い合います。
このアプローチの特徴
- 先着順に受け付けます。
- 予約可能な時間帯と場所の中から希望のものを選択します。
このアプローチの課題
- 先着順では公平ではないかもしれません。
- システムが過負荷になると、インターネットの速度が遅い人を何度もシャットアウトされてしまいます。
- 同じ時間に多くの人が予約をしようとすると、1人を除いて予約が取れないことがあり、ユーザーエクスペリエンスが低下します。予約を諦めてしまう人もいるかもしれません。一方で、望ましくない予約枠は埋まらないかもしれません。
- 優先順位、年齢、2回目の接種の有無などの基準に基づいて優先順位を決めるのは厄介です。
- 希望するワクチンの種類（Pfizer™、Moderna™、AstraZeneca™）がないかもしれません。
ユーザーが選択する方法は、予防接種のスケジュールを立てる上で最も効率的な方法ではないと言えるでしょう。人々は最も近い予防接種センターを選ぶことができますが、そのセンターが最大の収容力を持っているとは限りません。１人の人間にとって良いことが、集団全体にとって良いこととは限らないのです。個人のニーズに合った予防接種センターに誘導し、同時に人口全体にとってもキャパシティの関係で効率的な予防接種センターに誘導する方法が、このシステムにはありません。また、システムは簡単に過負荷になります。
システムが自動的にアサインする場合
このプッシュ型のアプローチでは、人々がシステムに情報を提供すると、システムが予約枠を割り当てます。
このアプローチの特徴
- 予約枠は優先順位に基づいて割り当てられます。
- 事前に設定された計画制約に基づいて、最適な予約時間と場所を割り当てます。
このアプローチの課題
- 割り当てられた時間帯は都合が悪いかもしれません。
- 人々は予定を変更する可能性が高いかもしれません。
システムが自動的に割り当てる方法は、ユーザーが選択する方法に比べて、人々にとって使いやすく、公平で、予防接種の予約スケジュールをより効率的に立てることができます。
2回目の接種に関する課題
ほとんどのCOVID-19ワクチンは、2回の接種が必要です。最適な効果を得るためには、同じ種類のワクチンを用いて、2回目の接種を1回目の接種に関連した特定の時間内に行う必要があります。それに加えて、ワクチンによって2回目の接種の時間枠が異なります。そして、その時間枠の中には、準備が整った日（2回目の接種が可能な最初の日）、理想的な日（2回目の接種に最適な日）、そして終了日（2回目の接種が有効であると考えられる最後の日）があります。例えば、ファイザー社の2回目の服用の理想的な日付は1回目の服用から21日後ですが、モデルナ社の2回目の服用の理想的な日付は1回目の服用から28日後です。
あなたが接種管理者であると仮定します。モデルナ社のワクチンの接種を開始したとします。4週間後、あなたはまだ1回目の接種を行っている間に、今度はすでに1回目の接種を受けた人が2回目の接種を受ける時期になります。あなたは、2回目の接種が必要な人に予約を入れるか、1回目の接種を受ける人に予約を入れるかを決めなければなりません。それは当然のことのように思えるかもしれませんが、このシナリオには潜在的な複雑さがあります。ワクチン接種の最初の週に、優先順位の高い人にワクチンを接種したものの、1日の終わりにワクチンが余っていることに気づき、それを無駄にしたくなかったため他の人にもワクチンを接種したとします。4週間後の今、あなたは1回目の接種の優先順位が高い人に予約を入れるか、2回目の接種が必要な優先順位の低い人に予約を入れるかを選択しなければなりません。
1回目と2回目の予約を均等にするという方法もありますが、そうすると2回目を必要としている人の予約が滞ってしまう可能性があります。2回目の接種が必要な人に優先順位をつけずに1回目の接種を続けると、最終的に2回目の接種が必要な人の滞留が雪だるま式に増えていきます。2回目の接種日は、理想的な接種日から非常に離れてしまい、予定日を超えてしまう可能性もあり、1回目のワクチン接種の効果が大幅に低下してしまいます。
したがって、初回接種者の優先順位にかかわらず、2回目の予約を初回接種者よりも優先する必要があるのです。
ワクチン接種予約スケジューリング問題の解決
ワクチン接種予約スケジューラーを構成できるOptaPlannerは、システム自動割り当て法を用いて、できるだけ多くの人にワクチンを接種するという問題を解決するために、計画制約を用いて各人のスコアを作成します。その人のスコアによって、いつ予約が取れるかが決まります。スコアが高ければ高いほど、早く予約が取れる可能性が高くなります。制約条件には、ハード、ミディアム、ソフトの3種類があります。
ハードな制約は必須条件です。いずれかのハード制約が破られた場合、そのプランは実現不可能であり、実行することはできません。
- ワクチンの容量：どのような場所でも、いつでもワクチンの容量に対してオーバーブッキングしてはいけません。
- ワクチンの最大年齢：ワクチンに最大年齢が設定されている場合、初回接種時にワクチンの最大年齢を超えている人には接種しません。年齢に適した種類のワクチンを確実に接種してください。例えば、最大年齢制限が65歳のワクチンの予約を、75歳の人に割り当てないようにします。
- 必要なワクチンの種類：必要なワクチンの種類を使用してください。例えば、2回目の接種には1回目と同じ種類のワクチンを使用しなければなりません。
- 準備完了日：指定された日以降にワクチンを接種します。例えば、2回目の接種を受ける人は、特定の種類のワクチンで推奨される最も早い接種可能日（1回目の接種から26日後など）より前に接種してはいけません。
- 期日：指定された期日までにワクチンを接種する。例えば、2回目の接種を受ける場合は、特定のワクチンの推奨接種最終期限（1回目の接種から3ヶ月後など）より前に接種する。
- 最大移動距離を制限：各人を最寄りの予防接種センターのグループの1つに割り当てます。これは通常、3つある接種センターのうちの1つです。この制限は距離ではなく移動時間によって計算されるため、都市部に住む人は農村部に住む人よりも最大移動距離が短くなるのが普通です。
ミディアム制約は、全員にアポイントメントを割り当てるだけの十分な容量がない場合に、誰がアポイントメントを取れないかを決めるものです。これを過制約計画といいます。
2回目のワクチン接種の予定：2回目のワクチン接種の予約は、理想的な日にちが計画の枠外になる場合を除き、割り当てられないままにしないでください。
優先度に基づいて人をスケジュール：各人には優先度が設定されています。これは通常は年齢ですが、例えば医療従事者の場合はもっと高くなる可能性があります。最も低い優先度の人だけを未割り当てにしておきます。それらは次の実行時に抽出されます。この制約は、前の制約よりもソフトです。というのも、2回目の接種は常に優先度の評価よりも優先されるからです。
- ソフト制約はなるべく破らないようにします。
- 希望する予防接種センター：希望する予防接種センターがある場合は、そのセンターに予約を入れます。
- 距離：指定された接種会場までの移動距離をできるだけ短くする。
- 理想的な接種日：指定された接種日にできるだけ近い日に接種します。例えば、2回目の接種を受ける人は、そのワクチンの理想的な接種日（1回目の接種から28日後など）に接種します。この制約は理想的な日付に1日でも近づくために、人々を国の反対側に送ることを避けるために、距離の制約よりも緩やかなものになっています。
- 優先度評価：優先度の高い人を計画ウィンドウの早い段階でスケジュールします。この制約は、国の反対側に人を送ることを避けるために、距離の制約よりもソフトになっています。また、優先度よりも2回目の服用が優先されるため、この制約は理想日の制約よりもソフトです。
ハード制約は、他のハード制約に対して重み付けされます。ソフト制約は、他のソフト制約に対して重み付けされます。しかし、それぞれの重みにかかわらず、ハードな制約は常にミディアムとソフトな制約を上回ります。予約枠よりも多くの人がいるため、厳しい決断を下す必要があります。 2回目の予約は、後になって予約が殺到するのを避けるため、常に最初に割り当てられます。その後、優先度に基づいて予約を入れていきます。最初の優先順位は年齢で決められます。これにより、若い人よりも年配の人が優先されることになります。その後、特定の優先順位の人には、数百点の追加ポイントが与えられます。これは、そのグループの優先度に応じて異なります。例えば、看護師の場合、1000ポイントが追加されます。このようにして、年配の看護師は若い看護師よりも優先され、若い看護師は看護師ではない人よりも優先されます。 次の表は、この考え方を示したものです。
表1 優先順位テーブル
Solver
OptaPlannerの核となるのはソルバーであり、問題データセットを受け取り、計画の制約や構成を重ね合わせるエンジンです。問題データセットには、人、ワクチン、予防接種センターに関するすべての情報が含まれています。ソルバーは様々なデータの組み合わせを検討し、特定のセンターでの予防接種の予約に割り当てられた人々の最適な予約スケジュールを最終的に決定します。次の図は、ソルバーが作成したスケジュールを示しています。
継続的な計画
継続的な計画とは、1つまたは複数の次期計画期間を同時に管理し、そのプロセスを毎月、毎週、毎日、毎時、またはそれ以上の頻度で繰り返す手法です。計画ウィンドウは、指定された間隔で段階的に進みます。次の図は、毎日更新される2週間分の計画ウィンドウを示しています。
2週間の計画対象を半分に分けます。最初の1週間は公開された状態で、2週間目はドラフトの状態です。計画対象の公開された部分とドラフトの部分の両方で、人々は予約枠に割り当てられます。しかし、計画対象の公開された部分にいる人だけが、自分の予約について通知されます。それ以外の人の予定は、次回の実行時に簡単に変更できます。このようにすることで、計画が自らを窮地に追い込むことを防ぐことができます。例えば、2回目の接種が必要な人の準備ができている日が月曜日で、理想的な日が水曜日の場合、週の後半にドラフトの予定を入れることができることを証明できれば、月曜日に招待する必要はありません。
計画対象の大きさを決めることはできますが、問題空間の大きさには注意してください。問題空間とは、計画を作成するために必要な様々な要素のすべてです。つまり、先に計画する日数が多ければ多いほど、問題スペースは大きくなります。
プランニング・エンティティの固定
毎日継続して計画を立てていると、2週間の間にすでに割り当てられている予定が出てきます。予約枠がダブルブッキングにならないようにするためには、既存の予約をピン留めして、割り当て済みとしてマークする必要があります。ピン留めは、1つまたは複数の特定の割り当てを固定し、OptaPlannerにそれらの固定された割り当てを中心にスケジュールを組ませるために使用されます。ピン留めされたプランニング・エンティティ（予約など）は、解決中に変更されることはありません。
エンティティがピン留めされているかどうかは、アポイントメントの状態によって決まります。前の画像を見てみると、画像の左側の予約枠には5つの状態があることがわかります。「空き」、「招待済」、「承認済」、「拒否」、「再予約済」。
注意： OptaPlannerエンジンは予約が固定されているかどうかだけをチェックするので、クイックスタートデモコードでは実際にこれらの状態を直接見ることはできません。
画像からもわかるように、すでに予定されている予約を中心に計画を立てられるようにする必要があります。「招待済」「承認済」状態の予約枠は固定されています。「空き」「再予約済」「拒否」の状態の予約枠は固定されておらず、スケジュール可能な状態です。
この例では、ソルバーが実行されると、公開範囲とドラフト範囲の両方で、2週間の計画対象全体を検索します。ソルバーは、スケジュール外の入力データに加えて、ピン留めされていないエンティティ（空き、再予約済、拒否のいずれかの状態の予約枠）を考慮し、最適な解を見つけます。ソルバーが毎日実行される場合、上の真ん中の画像のように、ソルバーを実行する前にスケジュールに新しい日が追加されています。3つ目のスケジュールには、ソルバーの結果が表示されています。
新しい日の予定が割り当てられ、以前は計画対象のドラフト部分に予定されていたAmyとEdnaが、対象の公開部分に予定されていることに注目してください。これは、GusとHugoが予定変更を要求したために実現しました。AmyとEdnaにはドラフトの日付が通知されていなかったので、これで混乱は起こりません。現在、彼らは計画対象の公開されたセクションで予定を持っているので、通知され、予定を受け入れるか拒否するかを尋ねられ、彼らの予定は固定されるようになりました。
ご期待ください。Optaplannerの予防接種予約計画のクイックスタートについて、より深く、より技術的に見たフォローアップブログを掲載する予定です。
こちらもご覧ください Vaccination appointment scheduling video
Github appointment planner code
OptaPlanner User Guide
翻訳：Solution Architect 梅野
