Repeated Planning - tokobayashi’s blog

ここ、ちょっと掘り下げます。
http://docs.jboss.org/optaplanner/release/latest/optaplanner-docs/html_single/index.html#repeatedPlanning

長期的に Solver を回しっぱなしのときに、problem facts が変化したらどうするのか？3つのパターンが考えられる。

fact の予期せぬ変更
- 例）シフトを割り当てた従業員が病気になる。スケジュールした飛行機が技術上の問題で遅延。コンピュータや車が故障
  - backup planning
不明な未来の fact
- 例） 2週間先までの入院割り当ては信頼できる。3,4週間先の割当ては信頼性が低い。5週間以上先はプランする意味がない
  - continuous planning
定期的に fact が変更される
- - real-time planning

Backup planning

まず、バックアップを考慮に入れて制約を作っておく。スペア従業員、予備ベッドなど。

変化が起こった時（従業員が病気になる）、problem facts / planning entities を変更（従業員をdelete, シフトを空ける）し、プランニングを再開する。このとき、その時点の solution から再開する。変化したので、スコアも変わったはず。construction heuristics は変化により発生したギャップ（シフトの空き）を埋める（スペア従業員で）。metaheuristics で更に改善する。

ポイント：この一連の動作をどのようなコードでやる？うーん、examples を見る限り（Nurse rostering で、Employee を GUI から delete したり、advance 1 day したり）、全部後述の ProblemFactChange でやってるように見える。

質問しました。
http://stackoverflow.com/questions/29410015/repeated-planning-without-problemfactchange

ProblemFactChange を使わない場合、このポストで書いた僕のサンプル（マニュアル再プラン）でOK
この3つのシナリオ（'Backup planning', 'Continuous planning' and 'Real-time planning'）は排他的な関係ではない。それぞれの特徴を説明しているだけで、複数が重なるようなケースもある。再プランの実装方法としては、「ProblemFactChange」「マニュアル再プラン」の2種類がある、と言える。

Continuous planning (windowed planning)

100年分のシフトをプランしても仕方ないですね。一定期間（planning windows）、例えば4週間分だけプランし、それを継続的に（例えば1日ごとに）プランすればよい。過去分のプランの planning entities は変更不可能だが、スコア制約に使うかもしれない（「続けて5日働いては行けない」とか）ので、まだ Solution に入っている。

Immovable planning entities

SelectionFilter を使って、「期間外のMoveは動かさない」を実装します。@PlanningEntity(movableEntitySelectionFilter = ... ) で指定します。

Nonvolatile replanning (semi movable planning entities)

継続的なプランニングでは「既存の状態からあんまり変えたくない」という要求もありえます。その場合、単純にスコア制約を追加すればいい。

Real-time planning

まず基本的な考えとしては、短い planning window で Continuous planning やるってこと。実装テクニックとして、以下がある。

ProblemFactChange

Solver が動いているときは、外部から problem fact を変更してはいけない。ProblemFactChange を使う。ProblemFactChange を実装して、solver.addProblemFactChange()で渡してやると、Solver が適切なタイミングで変更を反映してくれる。

コード例、Warning/Important/Note をよく読もう。problem fact list は自分で Shallow clone している。

実際は Solver は stop し、ProblemFactChange を実行し、restart する。よって、construction heuristic を再実行する。ただし、既存の solution から続けるため、遅くはならない。