Red Hat build of OptaPlanner を使用したソルバーの開発

Red Hat build of OptaPlanner は、Red Hat build of Quarkus プラットフォームに統合されるようになりました。OptaPlanner の依存関係を含むプラットフォームアーティファクトの依存関係のバージョンは、Quarkus bill of materials (BOM)ファイル com.redhat.quarkus.platform:quarkus-bom で維持されます。OptaPlanner プロジェクトで Quarkus BOM ファイルを使用する場合は、どの依存関係バージョンが連携するかを指定する必要はありません。代わりに、Quarkus BOM ファイルを pom.xml 設定ファイルにインポートできます。依存関係のバージョンは <dependencyManagement> セクションに含まれています。そのため、pom.xml ファイルの指定の BOM で管理される個別の Quarkus 依存関係のバージョンを記述する必要はありません。

ほとんどの場合、プランニング変数と値範囲間のリンクは自動検出されます。そのため、@ValueRangeProvider アノテーションは id プロパティーを提供する必要がなくなりました。同様に、プランニング変数は、valueRangeProviderRefs プロパティーを介して値の範囲プロバイダーを参照する必要がなくなりました。

コードや設定変更は必要ありません。簡潔さよりも明確さを優先する場合は、引き続き値範囲プロバイダーを明示的に参照できます。

XStream を使用した XML へのシリアル化に対する OptaPlanner のサポートは、このリリースでは非推奨になりました。optaplanner-persistence-xstream モジュールと、それに含まれるすべてのクラスは非推奨となり、Red Hat build of OptaPlanner の今後のリリースで削除されます。XML へのシリアライズを続行するには、optaplanner-persistence-jaxb モジュールに切り替えます。

optaplanner-examples モジュール内のすべての例は optaplanner-persistance-jackson モジュールを使用して JSON にリファクタリングされています。クイックスタートは、すでに JSON にシリアライズされているため、今回の変更の影響を受けます。

以下の例は、optaplanner-examples ディレクトリーから削除されました。

OptaPlanner は API と実装を分離します。

計画問題 では、限られたリソースや個別の制約の中で最適なゴールを見つけ出します。最適なゴールは、次のようなさまざまなものです。

これらのゴールに到達できるかどうかは、利用できるリソースの数に依存します。たとえば、以下のようなリソースには制限があります。

これらのリソースに関連する個別の制約についても考慮する必要があります。たとえば、要員が働くことのできる時間数、特定の装置を使用することのできる技能、または機器同士の互換性などです。

Red Hat build of OptaPlanner は、Java プログラマーが制約の飽和性の問題を効率的に解決するのに役立ちます。最適化ヒューリスティックとメタヒューリスティックを効率的なスコア計算と組み合わせます。

例に挙げたユースケースは 通常 NP 完全または NP 困難 であり、以下のことが言えます。

この場合、一般的な 2 つの手法では不十分であるため、問題を解くのが予想より困難だと考えられます。

高度な最適化アルゴリズムを用いる OptaPlanner であれば、このような計画問題に対する適切な解を、妥当な時間内に見つけ出すことができます。

計画問題には、多数の解が存在します。

以下に示すように、解は複数のカテゴリーに分類されます。

直観には反していますが、小規模なデータセットの場合であっても、(正しく計算された場合は) 膨大な数の可能解が存在します。

optaplanner-examples/src 配布フォルダーで提供される例では、ほとんどのインスタンスに多数の可能解が存在します。最適解を確実に見つけることができる方法は存在しないため、いかなる実行方法も、これらすべての可能解の部分集合を評価することしかできません。

膨大な数の可能解全体を効率的に網羅するために、OptaPlanner はさまざまな最適化アルゴリズムをサポートしています。

ユースケースによっては、ある最適化アルゴリズムが他のアルゴリズムより勝ることがありますが、それを事前に予測することは不可能です。OptaPlanner では、XML またはコード中の Solver 設定を数行変更するだけで、最適化アルゴリズムを切り替えることができます。

通常、プランニングの問題には、少なくとも 2 つの制約レベルがあります。

正の制約を持つ問題もあります。

一部の基本的な問題にはハード制約のみがあります。問題によっては、3 つ以上の制約があります (例: ハード制約、中程度の制約、ソフト制約)。

これらの制約により、計画問題における スコア計算方法 (または 適合度関数) が定義されます。プランニングの問題の解は、それぞれスコアで等級付けすることができます。OptaPlanner のスコア制約は、Java などのオブジェクト指向言語または Drools ルールで記述されます。

このタイプのコードは柔軟で、スケーラビリティーに優れます。

Red Hat build of OptaPlanner には、OptaPlanner のサンプルが複数同梱されています。たとえばコードなどを確認して、ニーズに合ったものに変更できます。

OptaPlanner サンプルには、教育関連のコンテストで出題された問題を解決するものもあります。以下の表の Contest 列には、このようなコンテストが掲載されています。また、コンテストの目的として、現実的 か、非現実的 かの識別をしています。現実的なコンテスト とは、以下の基準を満たす、独立した公式コンテストを指します。

現実的なコンテストでは、競合のソフトウェアや教育研究と OptaPlanner を客観的に比較できます。

n サイズのチェスボードに、他のクィーンに取られないクィーンに n 個のクィーンを置きます。最も一般的な n クィーンパズルは、n = 8 の 8 個のクィーンパズルです。

制約:

本書では、4 つのクイーンパズルを主な例として多用しています。

以下が提案された解です。

図4.1 4 個のクィーンパズルの誤った解

上記の解は、A1 と B0 (および B0 と D0) のクィーンがお互いに駒を取れるので間違っています。B0 のクィーンをどかせば他のクィーンに取られないようにするという制約は順守できますが、n 個のクィーンを置くという制約に違反します。

以下は正しい解です。

図4.2 クィーン 4 個のパズルの正しい解

すべての制約が満たされているので、これが正解です。

n クィーンパズルでは、正解が複数存在する場合が多々あります。特定の n に対して考えられる解を見つけるのではなく、特定の n に対する正しい解を 1 つ導き出すことにフォーカスします 。

4queens   has   4 queens with a search space of    256.
8queens   has   8 queens with a search space of   10^7.
16queens  has  16 queens with a search space of  10^19.
32queens  has  32 queens with a search space of  10^48.
64queens  has  64 queens with a search space of 10^115.
256queens has 256 queens with a search space of 10^616.

n クィーンは、初心者用のサンプルとして実装されているため、最適化はされていません。それにもかかわらず、クィーンが 64 個になっても簡単に処理できます。何点か変更を加えると、クィーンが 5000 個以上になっても簡単に対応できることが立証されています。

4.7.1. N クィーンのドメインモデル

この例では、4 つのクィーンの問題を解決するドメインモデルを使用します。

• ドメインモデルの作成

  適切なドメインモデルを使用すると、プランニングの問題をより簡単に理解し、解決することができます。

  以下は、n クィーンの例のドメインモデルです。

  public class Column {
  
      private int index;
  
      // ... getters and setters
  }

  public class Row {
  
      private int index;
  
      // ... getters and setters
  }

  public class Queen {
  
      private Column column;
      private Row row;
  
      public int getAscendingDiagonalIndex() {...}
      public int getDescendingDiagonalIndex() {...}
  
      // ... getters and setters
  }

• 探索空間の計算

  Queen インスタンスには Column (例: 0 は列 A、1 は列 B​) および Row (例: 0 は行 0、1 は行 1​) が含まれます。

  列と行をもとに、昇順の対角線、および降順の対角線を計算することができます。

  列と行のインデックスは、チェスボードの左上隅から数えています。

  public class NQueens {
  
      private int n;
      private List<Column> columnList;
      private List<Row> rowList;
  
      private List<Queen> queenList;
  
      private SimpleScore score;
  
      // ... getters and setters
  }

• 解の求め方

  1 つの NQueens インスタンスには Queen インスタンスの一覧が含まれています。これが Solution 実装として提供され、Solver が解決して読み出します。

たとえば、4 クイーンのサンプルでは、NQueens の getN() メソッドが常に 4 を返します。

図4.3 クィーン 4 個の解

表4.2 ドメインモデルの解の詳細

	columnIndex	rowIndex	ascendingDiagonalIndex (columnIndex + rowIndex)	descendingDiagonalIndex (columnIndex - rowIndex)
A1	0	1	1 (**)	-1
B0	1	0 (*)	1 (**)	1
C2	2	2	4	0
D0	3	0 (*)	3	3

(*) や (**) のように、クィーン 2 つが同じ行、列、対角線を共有する場合は、2 つの駒が互いを取ることができます。

この例に関する詳細は、Red Hat build of OptaPlanner クイックスタートガイド を参照してください。

都市の一覧をもとに、セールスマンが最短距離で、各都市を 1 度だけ訪問するルートを探します。

この問題は ウィキペディア に定義されています。これは、計算数学で 最も熱心に研究された問題の 1 つ です。大概は、従業員のシフト勤務など、その他の制約と一緒に計画の問題の一部として使用されます。

dj38     has  38 cities with a search space of   10^43.
europe40 has  40 cities with a search space of   10^46.
st70     has  70 cities with a search space of   10^98.
pcb442   has 442 cities with a search space of  10^976.
lu980    has 980 cities with a search space of 10^2504.

テニスクラブでは、毎週 4 チームが総あたりで試合をします。4 つの対戦枠を公平にチームに割り当てます。

ハード制約:

中程度の制約:

ソフト制約:

munich-7teams has 7 teams, 18 days, 12 unavailabilityPenalties and 72 teamAssignments with a search space of 10^60.

図4.4 ドメインモデル

各会議に、開始時間と会議室を割り当てます。会議の長さは異なります。

ハード制約:

中程度の制約:

ソフト制約:

50meetings-160timegrains-5rooms  has  50 meetings, 160 timeGrains and 5 rooms with a search space of 10^145.
100meetings-320timegrains-5rooms has 100 meetings, 320 timeGrains and 5 rooms with a search space of 10^320.
200meetings-640timegrains-5rooms has 200 meetings, 640 timeGrains and 5 rooms with a search space of 10^701.
400meetings-1280timegrains-5rooms has 400 meetings, 1280 timeGrains and 5 rooms with a search space of 10^1522.
800meetings-2560timegrains-5rooms has 800 meetings, 2560 timeGrains and 5 rooms with a search space of 10^3285.

各授業を、時間枠および講義室に割り当ててスケジュールを組みます。

ハード制約:

ソフト制約:

この問題は、International Timetabling Competition 2007 track 3 で定義されています。

comp01 has 24 teachers,  14 curricula,  30 courses, 160 lectures, 30 periods,  6 rooms and   53 unavailable period constraints with a search space of  10^360.
comp02 has 71 teachers,  70 curricula,  82 courses, 283 lectures, 25 periods, 16 rooms and  513 unavailable period constraints with a search space of  10^736.
comp03 has 61 teachers,  68 curricula,  72 courses, 251 lectures, 25 periods, 16 rooms and  382 unavailable period constraints with a search space of  10^653.
comp04 has 70 teachers,  57 curricula,  79 courses, 286 lectures, 25 periods, 18 rooms and  396 unavailable period constraints with a search space of  10^758.
comp05 has 47 teachers, 139 curricula,  54 courses, 152 lectures, 36 periods,  9 rooms and  771 unavailable period constraints with a search space of  10^381.
comp06 has 87 teachers,  70 curricula, 108 courses, 361 lectures, 25 periods, 18 rooms and  632 unavailable period constraints with a search space of  10^957.
comp07 has 99 teachers,  77 curricula, 131 courses, 434 lectures, 25 periods, 20 rooms and  667 unavailable period constraints with a search space of 10^1171.
comp08 has 76 teachers,  61 curricula,  86 courses, 324 lectures, 25 periods, 18 rooms and  478 unavailable period constraints with a search space of  10^859.
comp09 has 68 teachers,  75 curricula,  76 courses, 279 lectures, 25 periods, 18 rooms and  405 unavailable period constraints with a search space of  10^740.
comp10 has 88 teachers,  67 curricula, 115 courses, 370 lectures, 25 periods, 18 rooms and  694 unavailable period constraints with a search space of  10^981.
comp11 has 24 teachers,  13 curricula,  30 courses, 162 lectures, 45 periods,  5 rooms and   94 unavailable period constraints with a search space of  10^381.
comp12 has 74 teachers, 150 curricula,  88 courses, 218 lectures, 36 periods, 11 rooms and 1368 unavailable period constraints with a search space of  10^566.
comp13 has 77 teachers,  66 curricula,  82 courses, 308 lectures, 25 periods, 19 rooms and  468 unavailable period constraints with a search space of  10^824.
comp14 has 68 teachers,  60 curricula,  85 courses, 275 lectures, 25 periods, 17 rooms and  486 unavailable period constraints with a search space of  10^722.

図4.5 ドメインモデル

各プロセスをマシンに割り当てます。全プロセスには、すでに元の (最適化されていない) 割り当てがあります。プロセスにはそれぞれ、各リソース (CPU、メモリーなど) が一定量必要です。これは、クラウドのバランスの例の応用です。

ハード制約:

ソフト制約:

この問題は the Google ROADEF/EURO Challenge 2012 で定義されています。

図4.6 価値提案

model_a1_1 has  2 resources,  1 neighborhoods,   4 locations,    4 machines,    79 services,   100 processes and 1 balancePenalties with a search space of     10^60.
model_a1_2 has  4 resources,  2 neighborhoods,   4 locations,  100 machines,   980 services,  1000 processes and 0 balancePenalties with a search space of   10^2000.
model_a1_3 has  3 resources,  5 neighborhoods,  25 locations,  100 machines,   216 services,  1000 processes and 0 balancePenalties with a search space of   10^2000.
model_a1_4 has  3 resources, 50 neighborhoods,  50 locations,   50 machines,   142 services,  1000 processes and 1 balancePenalties with a search space of   10^1698.
model_a1_5 has  4 resources,  2 neighborhoods,   4 locations,   12 machines,   981 services,  1000 processes and 1 balancePenalties with a search space of   10^1079.
model_a2_1 has  3 resources,  1 neighborhoods,   1 locations,  100 machines,  1000 services,  1000 processes and 0 balancePenalties with a search space of   10^2000.
model_a2_2 has 12 resources,  5 neighborhoods,  25 locations,  100 machines,   170 services,  1000 processes and 0 balancePenalties with a search space of   10^2000.
model_a2_3 has 12 resources,  5 neighborhoods,  25 locations,  100 machines,   129 services,  1000 processes and 0 balancePenalties with a search space of   10^2000.
model_a2_4 has 12 resources,  5 neighborhoods,  25 locations,   50 machines,   180 services,  1000 processes and 1 balancePenalties with a search space of   10^1698.
model_a2_5 has 12 resources,  5 neighborhoods,  25 locations,   50 machines,   153 services,  1000 processes and 0 balancePenalties with a search space of   10^1698.
model_b_1  has 12 resources,  5 neighborhoods,  10 locations,  100 machines,  2512 services,  5000 processes and 0 balancePenalties with a search space of  10^10000.
model_b_2  has 12 resources,  5 neighborhoods,  10 locations,  100 machines,  2462 services,  5000 processes and 1 balancePenalties with a search space of  10^10000.
model_b_3  has  6 resources,  5 neighborhoods,  10 locations,  100 machines, 15025 services, 20000 processes and 0 balancePenalties with a search space of  10^40000.
model_b_4  has  6 resources,  5 neighborhoods,  50 locations,  500 machines,  1732 services, 20000 processes and 1 balancePenalties with a search space of  10^53979.
model_b_5  has  6 resources,  5 neighborhoods,  10 locations,  100 machines, 35082 services, 40000 processes and 0 balancePenalties with a search space of  10^80000.
model_b_6  has  6 resources,  5 neighborhoods,  50 locations,  200 machines, 14680 services, 40000 processes and 1 balancePenalties with a search space of  10^92041.
model_b_7  has  6 resources,  5 neighborhoods,  50 locations, 4000 machines, 15050 services, 40000 processes and 1 balancePenalties with a search space of 10^144082.
model_b_8  has  3 resources,  5 neighborhoods,  10 locations,  100 machines, 45030 services, 50000 processes and 0 balancePenalties with a search space of 10^100000.
model_b_9  has  3 resources,  5 neighborhoods, 100 locations, 1000 machines,  4609 services, 50000 processes and 1 balancePenalties with a search space of 10^150000.
model_b_10 has  3 resources,  5 neighborhoods, 100 locations, 5000 machines,  4896 services, 50000 processes and 1 balancePenalties with a search space of 10^184948.

図4.7 ドメインモデル

複数の車両を使用して、各顧客の品物を回収し、倉庫まで運びます。1 つの車両で複数の顧客から品物を回収することはできますが、収容できる容量には限りがあります。

基本例 (CVRP) のほかに、時間枠の設定が加わった例 (CVRPTW) もあります。

ハード制約:

ソフト制約:

CVRP (Capacitated Vehicle Routing Problem)と CVRPTW (Capacitated Vehicle Routing Problem)は、Networking and Emerging Optimization (NEO) VRP Web サイトで定義されています。

図4.8 価値提案

belgium-n50-k10             has  1 depots, 10 vehicles and   49 customers with a search space of   10^74.
belgium-n100-k10            has  1 depots, 10 vehicles and   99 customers with a search space of  10^170.
belgium-n500-k20            has  1 depots, 20 vehicles and  499 customers with a search space of 10^1168.
belgium-n1000-k20           has  1 depots, 20 vehicles and  999 customers with a search space of 10^2607.
belgium-n2750-k55           has  1 depots, 55 vehicles and 2749 customers with a search space of 10^8380.
belgium-road-km-n50-k10     has  1 depots, 10 vehicles and   49 customers with a search space of   10^74.
belgium-road-km-n100-k10    has  1 depots, 10 vehicles and   99 customers with a search space of  10^170.
belgium-road-km-n500-k20    has  1 depots, 20 vehicles and  499 customers with a search space of 10^1168.
belgium-road-km-n1000-k20   has  1 depots, 20 vehicles and  999 customers with a search space of 10^2607.
belgium-road-km-n2750-k55   has  1 depots, 55 vehicles and 2749 customers with a search space of 10^8380.
belgium-road-time-n50-k10   has  1 depots, 10 vehicles and   49 customers with a search space of   10^74.
belgium-road-time-n100-k10  has  1 depots, 10 vehicles and   99 customers with a search space of  10^170.
belgium-road-time-n500-k20  has  1 depots, 20 vehicles and  499 customers with a search space of 10^1168.
belgium-road-time-n1000-k20 has  1 depots, 20 vehicles and  999 customers with a search space of 10^2607.
belgium-road-time-n2750-k55 has  1 depots, 55 vehicles and 2749 customers with a search space of 10^8380.
belgium-d2-n50-k10          has  2 depots, 10 vehicles and   48 customers with a search space of   10^74.
belgium-d3-n100-k10         has  3 depots, 10 vehicles and   97 customers with a search space of  10^170.
belgium-d5-n500-k20         has  5 depots, 20 vehicles and  495 customers with a search space of 10^1168.
belgium-d8-n1000-k20        has  8 depots, 20 vehicles and  992 customers with a search space of 10^2607.
belgium-d10-n2750-k55       has 10 depots, 55 vehicles and 2740 customers with a search space of 10^8380.

A-n32-k5  has 1 depots,  5 vehicles and  31 customers with a search space of  10^40.
A-n33-k5  has 1 depots,  5 vehicles and  32 customers with a search space of  10^41.
A-n33-k6  has 1 depots,  6 vehicles and  32 customers with a search space of  10^42.
A-n34-k5  has 1 depots,  5 vehicles and  33 customers with a search space of  10^43.
A-n36-k5  has 1 depots,  5 vehicles and  35 customers with a search space of  10^46.
A-n37-k5  has 1 depots,  5 vehicles and  36 customers with a search space of  10^48.
A-n37-k6  has 1 depots,  6 vehicles and  36 customers with a search space of  10^49.
A-n38-k5  has 1 depots,  5 vehicles and  37 customers with a search space of  10^49.
A-n39-k5  has 1 depots,  5 vehicles and  38 customers with a search space of  10^51.
A-n39-k6  has 1 depots,  6 vehicles and  38 customers with a search space of  10^52.
A-n44-k7  has 1 depots,  7 vehicles and  43 customers with a search space of  10^61.
A-n45-k6  has 1 depots,  6 vehicles and  44 customers with a search space of  10^62.
A-n45-k7  has 1 depots,  7 vehicles and  44 customers with a search space of  10^63.
A-n46-k7  has 1 depots,  7 vehicles and  45 customers with a search space of  10^65.
A-n48-k7  has 1 depots,  7 vehicles and  47 customers with a search space of  10^68.
A-n53-k7  has 1 depots,  7 vehicles and  52 customers with a search space of  10^77.
A-n54-k7  has 1 depots,  7 vehicles and  53 customers with a search space of  10^79.
A-n55-k9  has 1 depots,  9 vehicles and  54 customers with a search space of  10^82.
A-n60-k9  has 1 depots,  9 vehicles and  59 customers with a search space of  10^91.
A-n61-k9  has 1 depots,  9 vehicles and  60 customers with a search space of  10^93.
A-n62-k8  has 1 depots,  8 vehicles and  61 customers with a search space of  10^94.
A-n63-k9  has 1 depots,  9 vehicles and  62 customers with a search space of  10^97.
A-n63-k10 has 1 depots, 10 vehicles and  62 customers with a search space of  10^98.
A-n64-k9  has 1 depots,  9 vehicles and  63 customers with a search space of  10^99.
A-n65-k9  has 1 depots,  9 vehicles and  64 customers with a search space of 10^101.
A-n69-k9  has 1 depots,  9 vehicles and  68 customers with a search space of 10^108.
A-n80-k10 has 1 depots, 10 vehicles and  79 customers with a search space of 10^130.
F-n45-k4  has 1 depots,  4 vehicles and  44 customers with a search space of  10^60.
F-n72-k4  has 1 depots,  4 vehicles and  71 customers with a search space of 10^108.
F-n135-k7 has 1 depots,  7 vehicles and 134 customers with a search space of 10^240.

CVRPTW インスタンス (時間枠あり):

belgium-tw-d2-n50-k10    has  2 depots, 10 vehicles and   48 customers with a search space of   10^74.
belgium-tw-d3-n100-k10   has  3 depots, 10 vehicles and   97 customers with a search space of  10^170.
belgium-tw-d5-n500-k20   has  5 depots, 20 vehicles and  495 customers with a search space of 10^1168.
belgium-tw-d8-n1000-k20  has  8 depots, 20 vehicles and  992 customers with a search space of 10^2607.
belgium-tw-d10-n2750-k55 has 10 depots, 55 vehicles and 2740 customers with a search space of 10^8380.
belgium-tw-n50-k10       has  1 depots, 10 vehicles and   49 customers with a search space of   10^74.
belgium-tw-n100-k10      has  1 depots, 10 vehicles and   99 customers with a search space of  10^170.
belgium-tw-n500-k20      has  1 depots, 20 vehicles and  499 customers with a search space of 10^1168.
belgium-tw-n1000-k20     has  1 depots, 20 vehicles and  999 customers with a search space of 10^2607.
belgium-tw-n2750-k55     has  1 depots, 55 vehicles and 2749 customers with a search space of 10^8380.

Solomon_025_C101       has 1 depots,  25 vehicles and   25 customers with a search space of   10^40.
Solomon_025_C201       has 1 depots,  25 vehicles and   25 customers with a search space of   10^40.
Solomon_025_R101       has 1 depots,  25 vehicles and   25 customers with a search space of   10^40.
Solomon_025_R201       has 1 depots,  25 vehicles and   25 customers with a search space of   10^40.
Solomon_025_RC101      has 1 depots,  25 vehicles and   25 customers with a search space of   10^40.
Solomon_025_RC201      has 1 depots,  25 vehicles and   25 customers with a search space of   10^40.
Solomon_100_C101       has 1 depots,  25 vehicles and  100 customers with a search space of  10^185.
Solomon_100_C201       has 1 depots,  25 vehicles and  100 customers with a search space of  10^185.
Solomon_100_R101       has 1 depots,  25 vehicles and  100 customers with a search space of  10^185.
Solomon_100_R201       has 1 depots,  25 vehicles and  100 customers with a search space of  10^185.
Solomon_100_RC101      has 1 depots,  25 vehicles and  100 customers with a search space of  10^185.
Solomon_100_RC201      has 1 depots,  25 vehicles and  100 customers with a search space of  10^185.
Homberger_0200_C1_2_1  has 1 depots,  50 vehicles and  200 customers with a search space of  10^429.
Homberger_0200_C2_2_1  has 1 depots,  50 vehicles and  200 customers with a search space of  10^429.
Homberger_0200_R1_2_1  has 1 depots,  50 vehicles and  200 customers with a search space of  10^429.
Homberger_0200_R2_2_1  has 1 depots,  50 vehicles and  200 customers with a search space of  10^429.
Homberger_0200_RC1_2_1 has 1 depots,  50 vehicles and  200 customers with a search space of  10^429.
Homberger_0200_RC2_2_1 has 1 depots,  50 vehicles and  200 customers with a search space of  10^429.
Homberger_0400_C1_4_1  has 1 depots, 100 vehicles and  400 customers with a search space of  10^978.
Homberger_0400_C2_4_1  has 1 depots, 100 vehicles and  400 customers with a search space of  10^978.
Homberger_0400_R1_4_1  has 1 depots, 100 vehicles and  400 customers with a search space of  10^978.
Homberger_0400_R2_4_1  has 1 depots, 100 vehicles and  400 customers with a search space of  10^978.
Homberger_0400_RC1_4_1 has 1 depots, 100 vehicles and  400 customers with a search space of  10^978.
Homberger_0400_RC2_4_1 has 1 depots, 100 vehicles and  400 customers with a search space of  10^978.
Homberger_0600_C1_6_1  has 1 depots, 150 vehicles and  600 customers with a search space of 10^1571.
Homberger_0600_C2_6_1  has 1 depots, 150 vehicles and  600 customers with a search space of 10^1571.
Homberger_0600_R1_6_1  has 1 depots, 150 vehicles and  600 customers with a search space of 10^1571.
Homberger_0600_R2_6_1  has 1 depots, 150 vehicles and  600 customers with a search space of 10^1571.
Homberger_0600_RC1_6_1 has 1 depots, 150 vehicles and  600 customers with a search space of 10^1571.
Homberger_0600_RC2_6_1 has 1 depots, 150 vehicles and  600 customers with a search space of 10^1571.
Homberger_0800_C1_8_1  has 1 depots, 200 vehicles and  800 customers with a search space of 10^2195.
Homberger_0800_C2_8_1  has 1 depots, 200 vehicles and  800 customers with a search space of 10^2195.
Homberger_0800_R1_8_1  has 1 depots, 200 vehicles and  800 customers with a search space of 10^2195.
Homberger_0800_R2_8_1  has 1 depots, 200 vehicles and  800 customers with a search space of 10^2195.
Homberger_0800_RC1_8_1 has 1 depots, 200 vehicles and  800 customers with a search space of 10^2195.
Homberger_0800_RC2_8_1 has 1 depots, 200 vehicles and  800 customers with a search space of 10^2195.
Homberger_1000_C110_1  has 1 depots, 250 vehicles and 1000 customers with a search space of 10^2840.
Homberger_1000_C210_1  has 1 depots, 250 vehicles and 1000 customers with a search space of 10^2840.
Homberger_1000_R110_1  has 1 depots, 250 vehicles and 1000 customers with a search space of 10^2840.
Homberger_1000_R210_1  has 1 depots, 250 vehicles and 1000 customers with a search space of 10^2840.
Homberger_1000_RC110_1 has 1 depots, 250 vehicles and 1000 customers with a search space of 10^2840.
Homberger_1000_RC210_1 has 1 depots, 250 vehicles and 1000 customers with a search space of 10^2840.

4.14.1. 配送経路のドメインモデル

時間枠ありの配送経路のドメインモデルでは、シャドウ変数の機能を多用します。こうすることで、arrivalTime や departureTime などのプロパティーがドメインモデルで直接利用できるため、制約をより自然に表現できます。

直線距離ではなく道路の距離

車は、直線距離を移動するのではなく、道路や高速道路を使用する必要があります。ビジネスの観点からすると、これは非常に重要です。

最適化アルゴリズムでは、2 点の距離を検索できている (できれば、事前に計算されている) 場合には、これは特に重要ではありません。道路費は距離である必要はありません。また、移動時間、フラッシュコスト、または加重関数を使用することもできます。GraphHopper (埋め込み可能なオフライン Java エンジン)、Open MapQuest (web サービス)、Google Maps Client API (web サービス) など、移動コストを事前に計算する技術があります。

また、Leaflet や Google Maps for developers など、レンダリングする技術も複数あります。

GraphHopper または Google Map Directions を使用して実際の経路をレンダリングすることも可能ですが、高速道路で経路が重なるため、停止する順番を確認するのが困難になります。

2 点間の移動費は、OptaPlanner で使用されるのと同じ最適化条件を使用する点に注意してください。たとえば、GraphHopper はデフォルトで、最短ではなく、最速の経路を返します。最速の GPS 経路の km (またはマイル) の距離を使用して、OptaPlanner で最短の移動を最適化しないようにしてください。以下のように、準最適な解が導き出される可能性があります。

一般的な考え方とは異なり、多くのユーザーは最短の経路ではなく、最速の経路を使用したいと考えます。通常の道路よりも高速道路の使用を好みます。舗装されていない道よりも舗装されている道路を好みます。実際には、最速の経路と、最短の経路が同じであることはほとんどありません。

プロジェクトの遅延を最小限に抑えるために、すべてのジョブを時間内に実行できるようにスケジュールを設定します。各ジョブは、プロジェクトに含まれます。ジョブは、異なる方法で実行できます。方法ごとに期間や使用するリソースが異なります。これは、柔軟な ジョブショップスケジューリング (JSP) の応用です。

ハード制約:

中程度の制約:

ソフト制約:

この問題は、the MISTA 2013 challenge で定義されています。

Schedule A-1  has  2 projects,  24 jobs,   64 execution modes,  7 resources and  150 resource requirements.
Schedule A-2  has  2 projects,  44 jobs,  124 execution modes,  7 resources and  420 resource requirements.
Schedule A-3  has  2 projects,  64 jobs,  184 execution modes,  7 resources and  630 resource requirements.
Schedule A-4  has  5 projects,  60 jobs,  160 execution modes, 16 resources and  390 resource requirements.
Schedule A-5  has  5 projects, 110 jobs,  310 execution modes, 16 resources and  900 resource requirements.
Schedule A-6  has  5 projects, 160 jobs,  460 execution modes, 16 resources and 1440 resource requirements.
Schedule A-7  has 10 projects, 120 jobs,  320 execution modes, 22 resources and  900 resource requirements.
Schedule A-8  has 10 projects, 220 jobs,  620 execution modes, 22 resources and 1860 resource requirements.
Schedule A-9  has 10 projects, 320 jobs,  920 execution modes, 31 resources and 2880 resource requirements.
Schedule A-10 has 10 projects, 320 jobs,  920 execution modes, 31 resources and 2970 resource requirements.
Schedule B-1  has 10 projects, 120 jobs,  320 execution modes, 31 resources and  900 resource requirements.
Schedule B-2  has 10 projects, 220 jobs,  620 execution modes, 22 resources and 1740 resource requirements.
Schedule B-3  has 10 projects, 320 jobs,  920 execution modes, 31 resources and 3060 resource requirements.
Schedule B-4  has 15 projects, 180 jobs,  480 execution modes, 46 resources and 1530 resource requirements.
Schedule B-5  has 15 projects, 330 jobs,  930 execution modes, 46 resources and 2760 resource requirements.
Schedule B-6  has 15 projects, 480 jobs, 1380 execution modes, 46 resources and 4500 resource requirements.
Schedule B-7  has 20 projects, 240 jobs,  640 execution modes, 61 resources and 1710 resource requirements.
Schedule B-8  has 20 projects, 440 jobs, 1240 execution modes, 42 resources and 3180 resource requirements.
Schedule B-9  has 20 projects, 640 jobs, 1840 execution modes, 61 resources and 5940 resource requirements.
Schedule B-10 has 20 projects, 460 jobs, 1300 execution modes, 42 resources and 4260 resource requirements.

従業員のキューのスポットに各タスクを割り当てます。タスクごとに、従業員のアフィニティーレベルから影響を受ける期間と、タスクの顧客が含まれます。

ハード制約:

ソフトレベル 0 の制約:

ソフトレベル 1 の制約:

ソフトレベル 2 の制約:

ソフトレベル 3 の制約:

図4.9 価値提案

24tasks-8employees   has  24 tasks, 6 skills,  8 employees,   4 task types and  4 customers with a search space of   10^30.
50tasks-5employees   has  50 tasks, 5 skills,  5 employees,  10 task types and 10 customers with a search space of   10^69.
100tasks-5employees  has 100 tasks, 5 skills,  5 employees,  20 task types and 15 customers with a search space of  10^164.
500tasks-20employees has 500 tasks, 6 skills, 20 employees, 100 task types and 60 customers with a search space of 10^1168.

図4.10 ドメインモデル

すべての試験に、時間と部屋を割り当てます。同じ時間帯に同じ部屋で、複数の試験を行うことができるものとします。

ハード制約:

ソフト制約 (パラメーター化されたペナルティーがそれぞれ設定されている):

実際に大学から取得した大規模な試験データセットを使用します。

この問題は、International Timetabling Competition 2007 track 1 で定義されています。Geoffrey De Smet は、非常に初期バージョンの OptaPlanner で 4 位を終了しました。このコンペティション以降、多くの改良点が加えられています。

exam_comp_set1 has  7883 students,  607 exams, 54 periods,  7 rooms,  12 period constraints and  0 room constraints with a search space of 10^1564.
exam_comp_set2 has 12484 students,  870 exams, 40 periods, 49 rooms,  12 period constraints and  2 room constraints with a search space of 10^2864.
exam_comp_set3 has 16365 students,  934 exams, 36 periods, 48 rooms, 168 period constraints and 15 room constraints with a search space of 10^3023.
exam_comp_set4 has  4421 students,  273 exams, 21 periods,  1 rooms,  40 period constraints and  0 room constraints with a search space of  10^360.
exam_comp_set5 has  8719 students, 1018 exams, 42 periods,  3 rooms,  27 period constraints and  0 room constraints with a search space of 10^2138.
exam_comp_set6 has  7909 students,  242 exams, 16 periods,  8 rooms,  22 period constraints and  0 room constraints with a search space of  10^509.
exam_comp_set7 has 13795 students, 1096 exams, 80 periods, 15 rooms,  28 period constraints and  0 room constraints with a search space of 10^3374.
exam_comp_set8 has  7718 students,  598 exams, 80 periods,  8 rooms,  20 period constraints and  1 room constraints with a search space of 10^1678.

4.17.1. テストの時間割のドメインモデル

以下の図では、主な試験のドメインクラスを紹介しています。

図4.11 試験のドメインクラスの図

試験のコンセプトを、Exam クラスと Topic クラスに分けた点に注意してください。期間または教室のプロパティーを変更し、解 (プランニングエンティティークラス) を求めると、Exam インスタンスが変化します。このとき、Topic インスタンス、Period インスタンス、および Room インスタンスは変化しません (他のクラスと同様、これらも問題ファクトです)。

各シフトに看護師を割り当てます。

ハード制約:

ソフト制約:

この問題は International Nurse Rostering Competition 2010 で定義されています。

図4.12 価値提案

toy1          has 1 skills, 3 shiftTypes, 2 patterns, 1 contracts,  6 employees,  7 shiftDates,  35 shiftAssignments and   0 requests with a search space of   10^27.
toy2          has 1 skills, 3 shiftTypes, 3 patterns, 2 contracts, 20 employees, 28 shiftDates, 180 shiftAssignments and 140 requests with a search space of  10^234.

sprint01      has 1 skills, 4 shiftTypes, 3 patterns, 4 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint02      has 1 skills, 4 shiftTypes, 3 patterns, 4 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint03      has 1 skills, 4 shiftTypes, 3 patterns, 4 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint04      has 1 skills, 4 shiftTypes, 3 patterns, 4 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint05      has 1 skills, 4 shiftTypes, 3 patterns, 4 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint06      has 1 skills, 4 shiftTypes, 3 patterns, 4 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint07      has 1 skills, 4 shiftTypes, 3 patterns, 4 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint08      has 1 skills, 4 shiftTypes, 3 patterns, 4 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint09      has 1 skills, 4 shiftTypes, 3 patterns, 4 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint10      has 1 skills, 4 shiftTypes, 3 patterns, 4 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint_hint01 has 1 skills, 4 shiftTypes, 8 patterns, 3 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint_hint02 has 1 skills, 4 shiftTypes, 0 patterns, 3 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint_hint03 has 1 skills, 4 shiftTypes, 8 patterns, 3 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint_late01 has 1 skills, 4 shiftTypes, 8 patterns, 3 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint_late02 has 1 skills, 3 shiftTypes, 4 patterns, 3 contracts, 10 employees, 28 shiftDates, 144 shiftAssignments and 139 requests with a search space of  10^144.
sprint_late03 has 1 skills, 4 shiftTypes, 8 patterns, 3 contracts, 10 employees, 28 shiftDates, 160 shiftAssignments and 150 requests with a search space of  10^160.
sprint_late04 has 1 skills, 4 shiftTypes, 8 patterns, 3 contracts, 10 employees, 28 shiftDates, 160 shiftAssignments and 150 requests with a search space of  10^160.
sprint_late05 has 1 skills, 4 shiftTypes, 8 patterns, 3 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint_late06 has 1 skills, 4 shiftTypes, 0 patterns, 3 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint_late07 has 1 skills, 4 shiftTypes, 0 patterns, 3 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.
sprint_late08 has 1 skills, 4 shiftTypes, 0 patterns, 3 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and   0 requests with a search space of  10^152.
sprint_late09 has 1 skills, 4 shiftTypes, 0 patterns, 3 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and   0 requests with a search space of  10^152.
sprint_late10 has 1 skills, 4 shiftTypes, 0 patterns, 3 contracts, 10 employees, 28 shiftDates, 152 shiftAssignments and 150 requests with a search space of  10^152.

medium01      has 1 skills, 4 shiftTypes, 0 patterns, 4 contracts, 31 employees, 28 shiftDates, 608 shiftAssignments and 403 requests with a search space of  10^906.
medium02      has 1 skills, 4 shiftTypes, 0 patterns, 4 contracts, 31 employees, 28 shiftDates, 608 shiftAssignments and 403 requests with a search space of  10^906.
medium03      has 1 skills, 4 shiftTypes, 0 patterns, 4 contracts, 31 employees, 28 shiftDates, 608 shiftAssignments and 403 requests with a search space of  10^906.
medium04      has 1 skills, 4 shiftTypes, 0 patterns, 4 contracts, 31 employees, 28 shiftDates, 608 shiftAssignments and 403 requests with a search space of  10^906.
medium05      has 1 skills, 4 shiftTypes, 0 patterns, 4 contracts, 31 employees, 28 shiftDates, 608 shiftAssignments and 403 requests with a search space of  10^906.
medium_hint01 has 1 skills, 4 shiftTypes, 7 patterns, 4 contracts, 30 employees, 28 shiftDates, 428 shiftAssignments and 390 requests with a search space of  10^632.
medium_hint02 has 1 skills, 4 shiftTypes, 7 patterns, 3 contracts, 30 employees, 28 shiftDates, 428 shiftAssignments and 390 requests with a search space of  10^632.
medium_hint03 has 1 skills, 4 shiftTypes, 7 patterns, 4 contracts, 30 employees, 28 shiftDates, 428 shiftAssignments and 390 requests with a search space of  10^632.
medium_late01 has 1 skills, 4 shiftTypes, 7 patterns, 4 contracts, 30 employees, 28 shiftDates, 424 shiftAssignments and 390 requests with a search space of  10^626.
medium_late02 has 1 skills, 4 shiftTypes, 7 patterns, 3 contracts, 30 employees, 28 shiftDates, 428 shiftAssignments and 390 requests with a search space of  10^632.
medium_late03 has 1 skills, 4 shiftTypes, 0 patterns, 4 contracts, 30 employees, 28 shiftDates, 428 shiftAssignments and 390 requests with a search space of  10^632.
medium_late04 has 1 skills, 4 shiftTypes, 7 patterns, 3 contracts, 30 employees, 28 shiftDates, 416 shiftAssignments and 390 requests with a search space of  10^614.
medium_late05 has 2 skills, 5 shiftTypes, 7 patterns, 4 contracts, 30 employees, 28 shiftDates, 452 shiftAssignments and 390 requests with a search space of  10^667.

long01        has 2 skills, 5 shiftTypes, 3 patterns, 3 contracts, 49 employees, 28 shiftDates, 740 shiftAssignments and 735 requests with a search space of 10^1250.
long02        has 2 skills, 5 shiftTypes, 3 patterns, 3 contracts, 49 employees, 28 shiftDates, 740 shiftAssignments and 735 requests with a search space of 10^1250.
long03        has 2 skills, 5 shiftTypes, 3 patterns, 3 contracts, 49 employees, 28 shiftDates, 740 shiftAssignments and 735 requests with a search space of 10^1250.
long04        has 2 skills, 5 shiftTypes, 3 patterns, 3 contracts, 49 employees, 28 shiftDates, 740 shiftAssignments and 735 requests with a search space of 10^1250.
long05        has 2 skills, 5 shiftTypes, 3 patterns, 3 contracts, 49 employees, 28 shiftDates, 740 shiftAssignments and 735 requests with a search space of 10^1250.
long_hint01   has 2 skills, 5 shiftTypes, 9 patterns, 3 contracts, 50 employees, 28 shiftDates, 740 shiftAssignments and   0 requests with a search space of 10^1257.
long_hint02   has 2 skills, 5 shiftTypes, 7 patterns, 3 contracts, 50 employees, 28 shiftDates, 740 shiftAssignments and   0 requests with a search space of 10^1257.
long_hint03   has 2 skills, 5 shiftTypes, 7 patterns, 3 contracts, 50 employees, 28 shiftDates, 740 shiftAssignments and   0 requests with a search space of 10^1257.
long_late01   has 2 skills, 5 shiftTypes, 9 patterns, 3 contracts, 50 employees, 28 shiftDates, 752 shiftAssignments and   0 requests with a search space of 10^1277.
long_late02   has 2 skills, 5 shiftTypes, 9 patterns, 4 contracts, 50 employees, 28 shiftDates, 752 shiftAssignments and   0 requests with a search space of 10^1277.
long_late03   has 2 skills, 5 shiftTypes, 9 patterns, 3 contracts, 50 employees, 28 shiftDates, 752 shiftAssignments and   0 requests with a search space of 10^1277.
long_late04   has 2 skills, 5 shiftTypes, 9 patterns, 4 contracts, 50 employees, 28 shiftDates, 752 shiftAssignments and   0 requests with a search space of 10^1277.
long_late05   has 2 skills, 5 shiftTypes, 9 patterns, 3 contracts, 50 employees, 28 shiftDates, 740 shiftAssignments and   0 requests with a search space of 10^1257.

図4.13 ドメインモデル

患者入院スケジュール (PAS) は、病院のベッド計画とも呼ばれ、病院に入院する各患者にベッドを割り当てます。病床は、患者の予定された滞在期間中、患者に割り当てられます。各病床は病室に属し、各病室は部門に属します。患者の来院日と退院日は決まっています。病床を割り当てるだけで済みます。

この問題は、過度に制約されたデータセットを特徴としています。すべてのプランニングエンティティーを割り当てる必要がない場合は、厳しい制約に違反することなく、必要な数のエンティティーを割り当てることが適切です。これは、過剰制約プランニングと呼ばれます。

ハード制約:

中程度の制約:

ソフト制約:

問題は Kaho’s Patient Scheduling のバリエーションであり、データセットは実際の病院から取得します。

overconstrained01 has 6 specialisms, 4 equipments, 1 departments,  25 rooms,  69 beds, 14 nights,  519 patients and  519 admissions with a search space of 10^958.
testdata01        has 4 specialisms, 2 equipments, 4 departments,  98 rooms, 286 beds, 14 nights,  652 patients and  652 admissions with a search space of 10^1603.
testdata02        has 6 specialisms, 2 equipments, 6 departments, 151 rooms, 465 beds, 14 nights,  755 patients and  755 admissions with a search space of 10^2015.
testdata03        has 5 specialisms, 2 equipments, 5 departments, 131 rooms, 395 beds, 14 nights,  708 patients and  708 admissions with a search space of 10^1840.
testdata04        has 6 specialisms, 2 equipments, 6 departments, 155 rooms, 471 beds, 14 nights,  746 patients and  746 admissions with a search space of 10^1995.
testdata05        has 4 specialisms, 2 equipments, 4 departments, 102 rooms, 325 beds, 14 nights,  587 patients and  587 admissions with a search space of 10^1476.
testdata06        has 4 specialisms, 2 equipments, 4 departments, 104 rooms, 313 beds, 14 nights,  685 patients and  685 admissions with a search space of 10^1711.
testdata07        has 6 specialisms, 4 equipments, 6 departments, 162 rooms, 472 beds, 14 nights,  519 patients and  519 admissions with a search space of 10^1389.
testdata08        has 6 specialisms, 4 equipments, 6 departments, 148 rooms, 441 beds, 21 nights,  895 patients and  895 admissions with a search space of 10^2368.
testdata09        has 4 specialisms, 4 equipments, 4 departments, 105 rooms, 310 beds, 28 nights, 1400 patients and 1400 admissions with a search space of 10^3490.
testdata10        has 4 specialisms, 4 equipments, 4 departments, 104 rooms, 308 beds, 56 nights, 1575 patients and 1575 admissions with a search space of 10^3922.
testdata11        has 4 specialisms, 4 equipments, 4 departments, 107 rooms, 318 beds, 91 nights, 2514 patients and 2514 admissions with a search space of 10^6295.
testdata12        has 4 specialisms, 4 equipments, 4 departments, 105 rooms, 310 beds, 84 nights, 2750 patients and 2750 admissions with a search space of 10^6856.
testdata13        has 5 specialisms, 4 equipments, 5 departments, 125 rooms, 368 beds, 28 nights,  907 patients and 1109 admissions with a search space of 10^2847.

図4.14 ドメインモデル

n 人数のチーム間の一致をスケジュールします。

ハード制約:

ソフト制約:

この問題は Michael Trick の Web サイト (世界記録が含まれます) で定義されています。

1-nl04     has  6 days,  4 teams and   12 matches with a search space of    10^5.
1-nl06     has 10 days,  6 teams and   30 matches with a search space of   10^19.
1-nl08     has 14 days,  8 teams and   56 matches with a search space of   10^43.
1-nl10     has 18 days, 10 teams and   90 matches with a search space of   10^79.
1-nl12     has 22 days, 12 teams and  132 matches with a search space of  10^126.
1-nl14     has 26 days, 14 teams and  182 matches with a search space of  10^186.
1-nl16     has 30 days, 16 teams and  240 matches with a search space of  10^259.
2-bra24    has 46 days, 24 teams and  552 matches with a search space of  10^692.
3-nfl16    has 30 days, 16 teams and  240 matches with a search space of  10^259.
3-nfl18    has 34 days, 18 teams and  306 matches with a search space of  10^346.
3-nfl20    has 38 days, 20 teams and  380 matches with a search space of  10^447.
3-nfl22    has 42 days, 22 teams and  462 matches with a search space of  10^562.
3-nfl24    has 46 days, 24 teams and  552 matches with a search space of  10^692.
3-nfl26    has 50 days, 26 teams and  650 matches with a search space of  10^838.
3-nfl28    has 54 days, 28 teams and  756 matches with a search space of  10^999.
3-nfl30    has 58 days, 30 teams and  870 matches with a search space of 10^1175.
3-nfl32    has 62 days, 32 teams and  992 matches with a search space of 10^1367.
4-super04  has  6 days,  4 teams and   12 matches with a search space of    10^5.
4-super06  has 10 days,  6 teams and   30 matches with a search space of   10^19.
4-super08  has 14 days,  8 teams and   56 matches with a search space of   10^43.
4-super10  has 18 days, 10 teams and   90 matches with a search space of   10^79.
4-super12  has 22 days, 12 teams and  132 matches with a search space of  10^126.
4-super14  has 26 days, 14 teams and  182 matches with a search space of  10^186.
5-galaxy04 has  6 days,  4 teams and   12 matches with a search space of    10^5.
5-galaxy06 has 10 days,  6 teams and   30 matches with a search space of   10^19.
5-galaxy08 has 14 days,  8 teams and   56 matches with a search space of   10^43.
5-galaxy10 has 18 days, 10 teams and   90 matches with a search space of   10^79.
5-galaxy12 has 22 days, 12 teams and  132 matches with a search space of  10^126.
5-galaxy14 has 26 days, 14 teams and  182 matches with a search space of  10^186.
5-galaxy16 has 30 days, 16 teams and  240 matches with a search space of  10^259.
5-galaxy18 has 34 days, 18 teams and  306 matches with a search space of  10^346.
5-galaxy20 has 38 days, 20 teams and  380 matches with a search space of  10^447.
5-galaxy22 has 42 days, 22 teams and  462 matches with a search space of  10^562.
5-galaxy24 has 46 days, 24 teams and  552 matches with a search space of  10^692.
5-galaxy26 has 50 days, 26 teams and  650 matches with a search space of  10^838.
5-galaxy28 has 54 days, 28 teams and  756 matches with a search space of  10^999.
5-galaxy30 has 58 days, 30 teams and  870 matches with a search space of 10^1175.
5-galaxy32 has 62 days, 32 teams and  992 matches with a search space of 10^1367.
5-galaxy34 has 66 days, 34 teams and 1122 matches with a search space of 10^1576.
5-galaxy36 has 70 days, 36 teams and 1260 matches with a search space of 10^1801.
5-galaxy38 has 74 days, 38 teams and 1406 matches with a search space of 10^2042.
5-galaxy40 has 78 days, 40 teams and 1560 matches with a search space of 10^2301.

全タスクを時間内にスケジュールし、機械の電気代を最小限に抑えます。電気代は時間によって異なります。これは、ジョブショップスケジューリング の応用です。

ハード制約:

中程度の制約:

ソフト制約 (問題に元々設定されている定義に追加):

この問題は、ICON challenge で定義されています。

sample01   has 3 resources,   2 machines, 288 periods and   25 tasks with a search space of    10^53.
sample02   has 3 resources,   2 machines, 288 periods and   50 tasks with a search space of   10^114.
sample03   has 3 resources,   2 machines, 288 periods and  100 tasks with a search space of   10^226.
sample04   has 3 resources,   5 machines, 288 periods and  100 tasks with a search space of   10^266.
sample05   has 3 resources,   2 machines, 288 periods and  250 tasks with a search space of   10^584.
sample06   has 3 resources,   5 machines, 288 periods and  250 tasks with a search space of   10^673.
sample07   has 3 resources,   2 machines, 288 periods and 1000 tasks with a search space of  10^2388.
sample08   has 3 resources,   5 machines, 288 periods and 1000 tasks with a search space of  10^2748.
sample09   has 4 resources,  20 machines, 288 periods and 2000 tasks with a search space of  10^6668.
instance00 has 1 resources,  10 machines, 288 periods and  200 tasks with a search space of   10^595.
instance01 has 1 resources,  10 machines, 288 periods and  200 tasks with a search space of   10^599.
instance02 has 1 resources,  10 machines, 288 periods and  200 tasks with a search space of   10^599.
instance03 has 1 resources,  10 machines, 288 periods and  200 tasks with a search space of   10^591.
instance04 has 1 resources,  10 machines, 288 periods and  200 tasks with a search space of   10^590.
instance05 has 2 resources,  25 machines, 288 periods and  200 tasks with a search space of   10^667.
instance06 has 2 resources,  25 machines, 288 periods and  200 tasks with a search space of   10^660.
instance07 has 2 resources,  25 machines, 288 periods and  200 tasks with a search space of   10^662.
instance08 has 2 resources,  25 machines, 288 periods and  200 tasks with a search space of   10^651.
instance09 has 2 resources,  25 machines, 288 periods and  200 tasks with a search space of   10^659.
instance10 has 2 resources,  20 machines, 288 periods and  500 tasks with a search space of  10^1657.
instance11 has 2 resources,  20 machines, 288 periods and  500 tasks with a search space of  10^1644.
instance12 has 2 resources,  20 machines, 288 periods and  500 tasks with a search space of  10^1637.
instance13 has 2 resources,  20 machines, 288 periods and  500 tasks with a search space of  10^1659.
instance14 has 2 resources,  20 machines, 288 periods and  500 tasks with a search space of  10^1643.
instance15 has 3 resources,  40 machines, 288 periods and  500 tasks with a search space of  10^1782.
instance16 has 3 resources,  40 machines, 288 periods and  500 tasks with a search space of  10^1778.
instance17 has 3 resources,  40 machines, 288 periods and  500 tasks with a search space of  10^1764.
instance18 has 3 resources,  40 machines, 288 periods and  500 tasks with a search space of  10^1769.
instance19 has 3 resources,  40 machines, 288 periods and  500 tasks with a search space of  10^1778.
instance20 has 3 resources,  50 machines, 288 periods and 1000 tasks with a search space of  10^3689.
instance21 has 3 resources,  50 machines, 288 periods and 1000 tasks with a search space of  10^3678.
instance22 has 3 resources,  50 machines, 288 periods and 1000 tasks with a search space of  10^3706.
instance23 has 3 resources,  50 machines, 288 periods and 1000 tasks with a search space of  10^3676.
instance24 has 3 resources,  50 machines, 288 periods and 1000 tasks with a search space of  10^3681.
instance25 has 3 resources,  60 machines, 288 periods and 1000 tasks with a search space of  10^3774.
instance26 has 3 resources,  60 machines, 288 periods and 1000 tasks with a search space of  10^3737.
instance27 has 3 resources,  60 machines, 288 periods and 1000 tasks with a search space of  10^3744.
instance28 has 3 resources,  60 machines, 288 periods and 1000 tasks with a search space of  10^3731.
instance29 has 3 resources,  60 machines, 288 periods and 1000 tasks with a search space of  10^3746.
instance30 has 4 resources,  70 machines, 288 periods and 2000 tasks with a search space of  10^7718.
instance31 has 4 resources,  70 machines, 288 periods and 2000 tasks with a search space of  10^7740.
instance32 has 4 resources,  70 machines, 288 periods and 2000 tasks with a search space of  10^7686.
instance33 has 4 resources,  70 machines, 288 periods and 2000 tasks with a search space of  10^7672.
instance34 has 4 resources,  70 machines, 288 periods and 2000 tasks with a search space of  10^7695.
instance35 has 4 resources,  80 machines, 288 periods and 2000 tasks with a search space of  10^7807.
instance36 has 4 resources,  80 machines, 288 periods and 2000 tasks with a search space of  10^7814.
instance37 has 4 resources,  80 machines, 288 periods and 2000 tasks with a search space of  10^7764.
instance38 has 4 resources,  80 machines, 288 periods and 2000 tasks with a search space of  10^7736.
instance39 has 4 resources,  80 machines, 288 periods and 2000 tasks with a search space of  10^7783.
instance40 has 4 resources,  90 machines, 288 periods and 4000 tasks with a search space of 10^15976.
instance41 has 4 resources,  90 machines, 288 periods and 4000 tasks with a search space of 10^15935.
instance42 has 4 resources,  90 machines, 288 periods and 4000 tasks with a search space of 10^15887.
instance43 has 4 resources,  90 machines, 288 periods and 4000 tasks with a search space of 10^15896.
instance44 has 4 resources,  90 machines, 288 periods and 4000 tasks with a search space of 10^15885.
instance45 has 4 resources, 100 machines, 288 periods and 5000 tasks with a search space of 10^20173.
instance46 has 4 resources, 100 machines, 288 periods and 5000 tasks with a search space of 10^20132.
instance47 has 4 resources, 100 machines, 288 periods and 5000 tasks with a search space of 10^20126.
instance48 has 4 resources, 100 machines, 288 periods and 5000 tasks with a search space of 10^20110.
instance49 has 4 resources, 100 machines, 288 periods and 5000 tasks with a search space of 10^20078.

各資産クラスに投資する相対数を決定します。

ハード制約:

ソフト制約:

de_smet_1 has 1 regions, 3 sectors and 11 asset classes with a search space of 10^4.
irrinki_1 has 2 regions, 3 sectors and 6 asset classes with a search space of 10^3.

サイズが大きいデータセットは作成/検証されていませんが、問題はないはずです。データに関する適切な情報源として、このアセット相関の Web サイト を参照してください。

各会議を時間帯と部屋に割り当てていきます。時間帯は重複させることができます。LibreOffice や Excel で編集可能な *.xlsx ファイルとの読み書きが可能です。

ハード制約:

ソフト制約:

図4.15 価値提案

18talks-6timeslots-5rooms    has  18 talks,  6 timeslots and  5 rooms with a search space of  10^26.
36talks-12timeslots-5rooms   has  36 talks, 12 timeslots and  5 rooms with a search space of  10^64.
72talks-12timeslots-10rooms  has  72 talks, 12 timeslots and 10 rooms with a search space of 10^149.
108talks-18timeslots-10rooms has 108 talks, 18 timeslots and 10 rooms with a search space of 10^243.
216talks-18timeslots-20rooms has 216 talks, 18 timeslots and 20 rooms with a search space of 10^552.

次のショーへの移動はロックバンクバスを使用し、空いている日のみショーをスケジュールする。

ハード制約:

中程度の制約:

ソフト制約:

47shows has 47 shows with a search space of 10^59.

パイロットと客室乗務員にフライトを割り当てます。

ハード制約:

ソフト制約:

175flights-7days-Europe  has 2 skills, 50 airports, 150 employees, 175 flights and  875 flight assignments with a search space of  10^1904.
700flights-28days-Europe has 2 skills, 50 airports, 150 employees, 700 flights and 3500 flight assignments with a search space of  10^7616.
875flights-7days-Europe  has 2 skills, 50 airports, 750 employees, 875 flights and 4375 flight assignments with a search space of 10^12578.
175flights-7days-US      has 2 skills, 48 airports, 150 employees, 175 flights and  875 flight assignments with a search space of  10^1904.

Apache Maven は分散型構築自動化ツールで、ソフトウェアプロジェクトの作成、ビルド、および管理を行うために Java アプリケーション開発で使用されます。Maven は Project Object Model (POM) ファイルと呼ばれる標準の設定ファイルを使用して、プロジェクトの定義や構築プロセスの管理を行います。POM ファイルは、モジュールおよびコンポーネントの依存関係、ビルドの順番、結果となるプロジェクトパッケージのターゲットを記述し、XML ファイルを使用して出力します。これにより、プロジェクトが適切かつ統一された状態でビルドされるようになります。

Quarkus プロジェクトでオンライン Maven リポジトリーを使用するか、Red Hat build of Quarkus の Maven リポジトリーをダウンロードできます。

Apache Maven および Quarkus Maven プラグインを使用して、Red Hat build of OptaPlanner および Quarkus アプリケーションの使用を開始できます。

https://code.quarkus.redhat.com の Web サイトを使用して Red Hat build of OptaPlanner Quarkus の Maven プロジェクトを生成し、アプリケーションで使用する拡張機能を自動的に追加および設定できます。

本セクションでは、以下のトピックを含む OptaPlanner Maven プロジェクトを生成するプロセスについて説明します。

Quarkus コマンドラインインターフェイス (CLI) を使用して、Quarkus OptaPlanner プロジェクトを作成できます。

各サンプルプロジェクトには、編集可能なソルバー設定ファイルがあります。<EXAMPLE>SolverConfig.xml ファイルは、org.optaplanner.optaplanner-8.33.0.Final-redhat-00004/optaplanner-examples/src/main/resources/org/optaplanner/examples/<EXAMPLE>ディレクトリーにあります。<EXAMPLE> は OptaPlanner サンプルプロジェクトの名前です。または、SolverFactory.createFromXmlFile() で ファイルから SolverFactory を作成することもできます。ただし、移植性の理由から、クラスパスのリソースが推奨されます。

Solver と SolverFactory の両方に、 Solution_ と呼ばれるジェネリック型があります。これは、計画の問題と解決策を表すクラスです。

OptaPlanner を使用すると、設定を変更することで、最適化アルゴリズムを比較的簡単に切り替えることができます。

SolverConfig API を使用して Solver を設定できます。これは特に、ランタイム時に値を動的に変更する場合に便利です。以下の例では、NQueens プロジェクトで Solver を構築する前のシステムプロパティーに基づいて実行時間を変更します。

        SolverConfig solverConfig = SolverConfig.createFromXmlResource(
                "org/optaplanner/examples/nqueens/optional/nqueensSolverConfig.xml");
        solverConfig.withTerminationConfig(new TerminationConfig()
                        .withMinutesSpentLimit(userInput));

        SolverFactory<NQueens> solverFactory = SolverFactory.create(solverConfig);
        Solver<NQueens> solver = solverFactory.buildSolver();

ソルバー設定 XML ファイルのすべての要素は、パッケージ namespace org.optaplanner.core.config の Config クラスまたは プロパティー として使用できます。これらの Config クラスは XML 形式の Java 表現です。これらのコンポーネントには、パッケージ namespace org.optaplanner.core.impl のランタイムコンポーネントをビルドし、それらを効率的な Solver に組み込むことができます。

    private SolverConfig template;

    public void init() {
        template = SolverConfig.createFromXmlResource(
                "org/optaplanner/examples/nqueens/optional/nqueensSolverConfig.xml");
        template.setTerminationConfig(new TerminationConfig());
    }

    // Called concurrently from different threads
    public void userRequest(..., long userInput) {
        SolverConfig solverConfig = new SolverConfig(template); // Copy it
        solverConfig.getTerminationConfig().setMinutesSpentLimit(userInput);
        SolverFactory<NQueens> solverFactory = SolverFactory.create(solverConfig);
        Solver<NQueens> solver = solverFactory.buildSolver();
        ...
    }

ドメインモデルのクラスは、プランニング変数などのプランニングエンティティーを指定する必要があります。以下の方法のいずれかを使用して、OptaPlanner プロジェクトにアノテーションを追加します。

デフォルトでは、OptaPlanner はリフレクションを使用してドメインにアクセスします。リフレクションは信頼性がありますが、直接アクセスに比べると遅くなります。または、Gizmo を使用してドメインにアクセスするように OptaPlanner を設定できます。これにより、リフレクションなしにドメインのフィールドとメソッドに直接アクセスするバイトコードが生成されます。ただし、この手法には以下の制限があります。

  <solver>
    <domainAccessType>GIZMO</domainAccessType>
  </solver>

OptaPlanner プロジェクトでは、クラスをインスタンス化し、カスタムプロパティーに明示的に言及するドキュメントを持つソルバー設定要素にカスタムプロパティーを追加できます。

ソルバーを使用して、計画の問題を解決します。

次の例は、NQueens の問題を解決します。

    NQueens problem = ...;
    NQueens bestSolution = solver.solve(problem);

この例では、 solve() メソッドは、すべての Queen が Row に割り当てられた NQueens インスタンスを返します。

図8.1 8ms のフォークイーンズパズルのベストソリューション (最適なソリューションでもあります)

solve (Solution) メソッドは、問題のサイズとソルバーの設定によっては時間がかかる場合があります。Solver は、可能な解決策の検索スペースをインテリジェントに処理し、解決中に遭遇した最良の解決策を記憶します。問題の大きさ、Solver が持っているどのくらいの時間、ソルバーの設定、等々の数ある要因により、最善の 解決策は、最適な 解決策ではない可能性もあります、

ソルバー環境モードを使用すると、実装の一般的なバグを検出できます。ロギングレベルには影響しません。

ソルバーには単一のランダムインスタンスがあります。一部のソルバー設定は、他の設定よりもランダムインスタンスを多く使用します。たとえば、シミュレーテッドアニーリングアルゴリズムは乱数に大きく依存しますが、Tabu Search はスコアの同点を解決するために乱数にのみ依存します。環境モードは、そのランダムインスタンスのシードに影響を与えます。

ソルバー設定 XML ファイルで環境モードを設定できます。次の例では、 FAST_ASSERT モードを設定します。

<solver xmlns="https://www.optaplanner.org/xsd/solver" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://www.optaplanner.org/xsd/solver https://www.optaplanner.org/xsd/solver/solver.xsd">
  <environmentMode>FAST_ASSERT</environmentMode>
  ...
</solver>

OptaPlanner ソルバーのログレベルを変更して、ソルバーアクティビティーを確認できます。次のリストは、さまざまなログレベルについて説明しています。

次の例は、デバッグログからの出力を示しています。

INFO  Solving started: time spent (3), best score (-4init/0), random (JDK with seed 0).
DEBUG     CH step (0), time spent (5), score (-3init/0), selected move count (1), picked move (Queen-2 {null -> Row-0}).
DEBUG     CH step (1), time spent (7), score (-2init/0), selected move count (3), picked move (Queen-1 {null -> Row-2}).
DEBUG     CH step (2), time spent (10), score (-1init/0), selected move count (4), picked move (Queen-3 {null -> Row-3}).
DEBUG     CH step (3), time spent (12), score (-1), selected move count (4), picked move (Queen-0 {null -> Row-1}).
INFO  Construction Heuristic phase (0) ended: time spent (12), best score (-1), score calculation speed (9000/sec), step total (4).
DEBUG     LS step (0), time spent (19), score (-1),     best score (-1), accepted/selected move count (12/12), picked move (Queen-1 {Row-2 -> Row-3}).
DEBUG     LS step (1), time spent (24), score (0), new best score (0), accepted/selected move count (9/12), picked move (Queen-3 {Row-3 -> Row-2}).
INFO  Local Search phase (1) ended: time spent (24), best score (0), score calculation speed (4000/sec), step total (2).
INFO  Solving ended: time spent (24), best score (0), score calculation speed (7000/sec), phase total (2), environment mode (REPRODUCIBLE).

費やされた時間の値はすべてミリ秒単位です。

すべてが SLF4J に記録されます。これは、すべてのログメッセージを Logback、Apache Commons Logging、Log4j、または java.util.logging に委任する単純なログファサードです。選択したロギングフレームワークのロギングアダプターに依存関係を追加します。

Logback は、OptaPlanner で使用するために推奨されるロギングフレームワークです。Logback を使用して、OptaPlanner ソルバーアクティビティーをログに記録します。

すでに Log4J を使用していて、より高速な後継である Logback に切り替えたくない場合は、Log4J 用に OptaPlanner プロジェクトを設定できます。

OptaPlanner は、Java アプリケーション用のメトリック計測ライブラリーである Micrometer を介してメトリックを公開します。一般的な監視システムで Micrometer を使用して、OptaPlanner ソルバーを監視できます。

<solver xmlns="https://www.optaplanner.org/xsd/solver" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://www.optaplanner.org/xsd/solver https://www.optaplanner.org/xsd/solver/solver.xsd">
  <monitoring>
    <metric>BEST_SCORE</metric>
    <metric>SCORE_CALCULATION_COUNT</metric>
    ...
  </monitoring>
  ...
</solver>

多くのヒューリスティックおよびメタヒューリスティックは、移動の選択、スコアの結びつきの解決、確率ベースの移動の受け入れなどを疑似乱数ジェネレーターに依存しています。解決中に、同じランダムインスタンスが再利用され、再現性、パフォーマンス、およびランダム値の均一な分布が向上します。

ランダムシードは、疑似乱数ジェネレータを初期化するために使用される番号です。

ほとんどのユースケースでは、 randomType プロパティーの値は、複数のデータセットでの最良のソリューションの平均品質に大きな影響を与えません。

バッチ解決とは、複数のデータセットを並行して解決することです。バッチ解決は夜間処理で特に役立ちます。

public class TimeTableService {

    private SolverManager<TimeTable, Long> solverManager;

    // Returns immediately, call it for every data set
    public void solveBatch(Long timeTableId) {
        solverManager.solve(timeTableId,
                // Called once, when solving starts
                this::findById,
                // Called once, when solving ends
                this::save);
    }

    public TimeTable findById(Long timeTableId) {...}

    public void save(TimeTable timeTable) {...}

}

ユーザーがソリューションを待っている間にソルバーが実行されている場合、ユーザーは結果を受け取るまでに数分または数時間待つ必要がある場合があります。すべてが順調に進んでいることをユーザーに保証するために、これまでに達成された最良の解決策と最良のスコアを表示して進捗状況を示します。

Red Hat build of OptaPlanner の時間割プロジェクトの目標は、レッスンごとに時間枠と部屋に割り当てることです。これには、次の図に示すように、Timeslot、Lesson、および Room の 3 つのクラスを追加します。

高校のスケジュールは毎週 (同じ内容が) 繰り返されるだけなので、時間枠には日付がありません。また、継続的プランニング は必要ありません。解決時に Timeslot インスタンスが変更しないため、Timeslot は 問題ファクト と呼ばれます。このようなクラスには OptaPlanner 固有のアノテーションは必要ありません。

Room インスタンスは解決時に変化しないため、Room は 問題ファクト でもあります。

解決中に、OptaPlanner は、Lesson クラスの timeslot フィールドと room フィールドを変更して、各授業を、時間枠 1 つ、部屋 1 つに割り当てます。OptaPlanner はこれらのフィールドを変更するため、Lesson は プランニングエンティティー となります。

前図では、オレンジのフィールド以外のほぼすべてのフィールドに、入力データが含まれています。授業の timeslot フィールドと room フィールドは、入力データに割り当てられておらず (null)、出力データに割り当てられて (null ではない) います。Red Hat build of OptaPlanner は、解決時にこれらのフィールドを変更します。このようなフィールドはプランニング変数と呼ばれます。このフィールドを OptaPlanner に認識させるには、timeslot フィールドと room のフィールドに @PlanningVariable アノテーションが必要です。このフィールドに含まれる Lesson クラスには、@PlanningEntity アノテーションが必要です。

問題の解決時に スコア で導かれた解の質を表します。スコアが高いほど質が高くなります。Red Hat build of OptaPlanner は、利用可能な時間内で見つかった解の中から最高スコアのものを探し出します。これが 最適 解である可能性があります。

時間割の例のユースケースでは、ハードとソフト制約を使用しているため、HardSoftScore クラスでスコアを表します。

ハード制約は、他のハード制約と比べて、重み付けを行います。ソフト制約は、他のソフト制約と比べて、重み付けを行います。ハード制約は、それぞれの重みに関係なく、常にソフト制約よりも高くなります。

EasyScoreCalculator クラスを実装して、スコアを計算できます。

public class TimeTableEasyScoreCalculator implements EasyScoreCalculator<TimeTable> {

    @Override
    public HardSoftScore calculateScore(TimeTable timeTable) {
        List<Lesson> lessonList = timeTable.getLessonList();
        int hardScore = 0;
        for (Lesson a : lessonList) {
            for (Lesson b : lessonList) {
                if (a.getTimeslot() != null && a.getTimeslot().equals(b.getTimeslot())
                        && a.getId() < b.getId()) {
                    // A room can accommodate at most one lesson at the same time.
                    if (a.getRoom() != null && a.getRoom().equals(b.getRoom())) {
                        hardScore--;
                    }
                    // A teacher can teach at most one lesson at the same time.
                    if (a.getTeacher().equals(b.getTeacher())) {
                        hardScore--;
                    }
                    // A student can attend at most one lesson at the same time.
                    if (a.getStudentGroup().equals(b.getStudentGroup())) {
                        hardScore--;
                    }
                }
            }
        }
        int softScore = 0;
        // Soft constraints are only implemented in the "complete" implementation
        return HardSoftScore.of(hardScore, softScore);
    }

}

残念ながら、この解は漸増的ではないので、適切にスケーリングされません。授業が別の時間枠や教室に割り当てられるたびに、全授業が再評価され、新しいスコアが計算されます。

src/main/java/com/example/solver/TimeTableConstraintProvider.java クラスを作成して、漸増的スコア計算を実行すると、解がより優れたものになります。このクラスは、Java 8 Streams と SQL を基にした OptaPlanner の ConstraintStream API を使用します。ConstraintProvider は、EasyScoreCalculator と比べ、スケーリングの規模が遥かに大きくなっています (O (n²) ではなく O (n))。

package com.example.solver;

import com.example.domain.Lesson;
import org.optaplanner.core.api.score.buildin.hardsoft.HardSoftScore;
import org.optaplanner.core.api.score.stream.Constraint;
import org.optaplanner.core.api.score.stream.ConstraintFactory;
import org.optaplanner.core.api.score.stream.ConstraintProvider;
import org.optaplanner.core.api.score.stream.Joiners;

public class TimeTableConstraintProvider implements ConstraintProvider {

    @Override
    public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
        return new Constraint[] {
                // Hard constraints
                roomConflict(constraintFactory),
                teacherConflict(constraintFactory),
                studentGroupConflict(constraintFactory),
                // Soft constraints are only implemented in the "complete" implementation
        };
    }

    private Constraint roomConflict(ConstraintFactory constraintFactory) {
        // A room can accommodate at most one lesson at the same time.

        // Select a lesson ...
        return constraintFactory.forEach(Lesson.class)
                // ... and pair it with another lesson ...
                .join(Lesson.class,
                        // ... in the same timeslot ...
                        Joiners.equal(Lesson::getTimeslot),
                        // ... in the same room ...
                        Joiners.equal(Lesson::getRoom),
                        // ... and the pair is unique (different id, no reverse pairs)
                        Joiners.lessThan(Lesson::getId))
                // then penalize each pair with a hard weight.
                .penalize(HardSoftScore.ONE_HARD)
                .asConstraint("Room conflict");
    }

    private Constraint teacherConflict(ConstraintFactory constraintFactory) {
        // A teacher can teach at most one lesson at the same time.
        return constraintFactory.forEach(Lesson.class)
                .join(Lesson.class,
                        Joiners.equal(Lesson::getTimeslot),
                        Joiners.equal(Lesson::getTeacher),
                        Joiners.lessThan(Lesson::getId))
                        .penalize(HardSoftScore.ONE_HARD)
                        .asConstraint("Teacher conflict");
    }

    private Constraint studentGroupConflict(ConstraintFactory constraintFactory) {
        // A student can attend at most one lesson at the same time.
        return constraintFactory.forEach(Lesson.class)
                .join(Lesson.class,
                        Joiners.equal(Lesson::getTimeslot),
                        Joiners.equal(Lesson::getStudentGroup),
                        Joiners.lessThan(Lesson::getId))
                        .penalize(HardSoftScore.ONE_HARD)
                        .asConstraint("Student group conflict");
    }

}

TimeTable インスタンスは、単一データセットの Timeslot インスタンス、Room インスタンス、および Lesson インスタンスをラップします。さらに、このインスタンスは、特定のプランニング変数の状態を持つ授業がすべて含まれているため、このインスタンスは プランニングソリューション となり、スコアが割り当てられます。

TimeTable クラスには @PlanningSolution アノテーションが含まれているため、Red Hat build of OptaPlanner はこのクラスに全入出力データが含まれていることを認識します。

具体的には、このクラスは問題の入力です。

ただし、このクラスはソリューションの出力でもあります。

package com.example.domain;

import java.util.List;

import org.optaplanner.core.api.domain.solution.PlanningEntityCollectionProperty;
import org.optaplanner.core.api.domain.solution.PlanningScore;
import org.optaplanner.core.api.domain.solution.PlanningSolution;
import org.optaplanner.core.api.domain.solution.ProblemFactCollectionProperty;
import org.optaplanner.core.api.domain.valuerange.ValueRangeProvider;
import org.optaplanner.core.api.score.buildin.hardsoft.HardSoftScore;

@PlanningSolution
public class TimeTable {

    @ValueRangeProvider(id = "timeslotRange")
    @ProblemFactCollectionProperty
    private List<Timeslot> timeslotList;

    @ValueRangeProvider(id = "roomRange")
    @ProblemFactCollectionProperty
    private List<Room> roomList;

    @PlanningEntityCollectionProperty
    private List<Lesson> lessonList;

    @PlanningScore
    private HardSoftScore score;

    private TimeTable() {
    }

    public TimeTable(List<Timeslot> timeslotList, List<Room> roomList,
            List<Lesson> lessonList) {
        this.timeslotList = timeslotList;
        this.roomList = roomList;
        this.lessonList = lessonList;
    }

    // ********************************
    // Getters and setters
    // ********************************

    public List<Timeslot> getTimeslotList() {
        return timeslotList;
    }

    public List<Room> getRoomList() {
        return roomList;
    }

    public List<Lesson> getLessonList() {
        return lessonList;
    }

    public HardSoftScore getScore() {
        return score;
    }

}

同じロジックに従い、roomList フィールドにも @ValueRangeProvider アノテーションが含まれています。

timeslotList フィールドと roomList フィールドには @ProblemFactCollectionProperty アノテーションが含まれているため、TimeTableConstraintProvider はこれらのインスタンスから選択できます。

lessonList には @PlanningEntityCollectionProperty アノテーションが含まれているため、OptaPlanner は解決時に変更でき、TimeTableConstraintProvider はこの中から選択できます。

REST スレッドで計画問題を解決すると、HTTP タイムアウトの問題が発生します。そのため、Quarkus スターターでは SolverManager を注入することで、個別のスレッドプールでソルバーを実行して複数のデータセットを並行して解決できます。

package org.acme.optaplanner.rest;

import java.util.UUID;
import java.util.concurrent.ExecutionException;
import javax.inject.Inject;
import javax.ws.rs.POST;
import javax.ws.rs.Path;

import org.acme.optaplanner.domain.TimeTable;
import org.optaplanner.core.api.solver.SolverJob;
import org.optaplanner.core.api.solver.SolverManager;

@Path("/timeTable")
public class TimeTableResource {

    @Inject
    SolverManager<TimeTable, UUID> solverManager;

    @POST
    @Path("/solve")
    public TimeTable solve(TimeTable problem) {
        UUID problemId = UUID.randomUUID();
        // Submit the problem to start solving
        SolverJob<TimeTable, UUID> solverJob = solverManager.solve(problemId, problem);
        TimeTable solution;
        try {
            // Wait until the solving ends
            solution = solverJob.getFinalBestSolution();
        } catch (InterruptedException | ExecutionException e) {
            throw new IllegalStateException("Solving failed.", e);
        }
        return solution;
    }

}

この例では、初期実装はソルバーが完了するのを待つため、HTTP タイムアウトがまだ発生します。complete 実装を使用することで、より適切に HTTP タイムアウトを回避できます。

プランニングアプリケーションに終了設定または終了イベントがない場合、理論的には永続的に実行されることになり、実際には HTTP タイムアウトエラーが発生します。これが発生しないようにするには、optaplanner.solver.termination.spent-limit パラメーターを使用して、アプリケーションが終了してからの時間を指定します。多くのアプリケーションでは、この時間を最低でも 5 分 (5m) に設定します。ただし、時間割の例では、解決時間を 5 分に制限すると、期間が十分に短いため HTTP タイムアウトを回避できます。

quarkus.optaplanner.solver.termination.spent-limit=5s

時間割プロジェクトを作成したら、開発モードで実行します。開発モードでは、アプリケーションの実行中にアプリケーションソースおよび設定を更新できます。変更が実行中のアプリケーションに反映されます。

適切なアプリケーションにはテストが含まれます。timetable プロジェクトで制約とソルバーをテストします。

package org.acme.optaplanner.solver;

import java.time.DayOfWeek;
import java.time.LocalTime;

import javax.inject.Inject;

import io.quarkus.test.junit.QuarkusTest;
import org.acme.optaplanner.domain.Lesson;
import org.acme.optaplanner.domain.Room;
import org.acme.optaplanner.domain.TimeTable;
import org.acme.optaplanner.domain.Timeslot;
import org.junit.jupiter.api.Test;
import org.optaplanner.test.api.score.stream.ConstraintVerifier;

@QuarkusTest
class TimeTableConstraintProviderTest {

    private static final Room ROOM = new Room("Room1");
    private static final Timeslot TIMESLOT1 = new Timeslot(DayOfWeek.MONDAY, LocalTime.of(9,0), LocalTime.NOON);
    private static final Timeslot TIMESLOT2 = new Timeslot(DayOfWeek.TUESDAY, LocalTime.of(9,0), LocalTime.NOON);

    @Inject
    ConstraintVerifier<TimeTableConstraintProvider, TimeTable> constraintVerifier;

    @Test
    void roomConflict() {
        Lesson firstLesson = new Lesson(1, "Subject1", "Teacher1", "Group1");
        Lesson conflictingLesson = new Lesson(2, "Subject2", "Teacher2", "Group2");
        Lesson nonConflictingLesson = new Lesson(3, "Subject3", "Teacher3", "Group3");

        firstLesson.setRoom(ROOM);
        firstLesson.setTimeslot(TIMESLOT1);

        conflictingLesson.setRoom(ROOM);
        conflictingLesson.setTimeslot(TIMESLOT1);

        nonConflictingLesson.setRoom(ROOM);
        nonConflictingLesson.setTimeslot(TIMESLOT2);

        constraintVerifier.verifyThat(TimeTableConstraintProvider::roomConflict)
                .given(firstLesson, conflictingLesson, nonConflictingLesson)
                .penalizesBy(1);
    }

}

Red Hat build of OptaPlanner の時間割プロジェクトを完了後にロギング情報を使用すると、ConstraintProvider で制約が微調整しやすくなります。info ログファイルでスコア計算の速度を確認して、制約に加えた変更の影響を評価します。デバッグモードでアプリケーションを実行して、アプリケーションが行う手順をすべて表示するか、追跡ログを使用して全手順および動きをロギングします。

Quarkus OptaPlanner 学校の時間割アプリケーションを作成したら、それをデータベースと統合し、ウェブベースのユーザーインターフェイスを作成して時間割を表示できます。

OptaPlanner は、Java アプリケーション用のメトリック計測ライブラリーである Micrometer を介してメトリックを公開します。Prometheus で Micrometer を使用して、学校の時間割アプリケーションで OptaPlanner ソルバーを監視できます。

スケジュール予約には、主に 2 つの方法があります。システムは、ユーザーが予約枠 (ユーザーの選択) を選択できるようにするか、システムが予約枠を割り当ててそのユーザーにワクチン予約の日付と場所 (システムの自動割当) を通知することができます。OptaPlanner のワクチン接種予約スケジューラーは、システム自動割り当てのアプローチを使用します。OptaPlanner ワクチン接種予約スケジューラーでは、システムに情報を提供するアプリケーションを作成して、システムが予約を割り当てます。

このアプローチの特徴は次のとおりです。

このアプローチにより、プランニング制約を使用して各ユーザーのスコアを作成し、できるだけ多くの人がワクチン接種を受けられるようにする問題を解決します。スコアで、予約を取得するタイミングが決まります。スコアが高いほど、早い段階で受信できる可能性が高くなります。

11.1.2. Red Hat build of OptaPlanner のソルバー

OptaPlanner のコアには Solver があり、エンジンは、問題データセットを取り、プランニングの制約および設定をオーバーレイします。問題データセットには、人、ワクチン、ワクチンセンターなどの情報すべてが含まれます。ソルバーは、さまざまなデータを組み合わせて機能し、最終的に特定のセンターでワクチン接種予約を割り当てる時に、最適な予約スケジュールを決定します。以下は、ソルバーで作成されたスケジュールを示しています。

11.1.3. 継続プランニング

継続プランニングは、1 つ以上の今後のプランニング期間をまとめて管理して、そのプロセスを月単位、週単位、日単位、1 時間単位、またはそれよりも短い単位で繰り返す手法です。プランニング枠は、指定した間隔で増分して進められます。以下は、毎日更新される 2 週間のプランニング枠を示しています。

2 週間計画枠を半分に分割します。1 週間目は公開状態で、2 週間目がドラフト状態にあります。プランニング枠の公開部分とドラフト部分の両方で、予約を割り当てます。ただし、プランニング枠の公開部分の方だけに、予約の通知が行きます。他の予約は、次の実行でまだ簡単に変更できます。こうすることで、ソルバーを次回実行すると、必要に応じて OptaPlanner が柔軟にドラフトの部分の予約を変更できます。たとえば、2 回目の投与の準備が月曜にできており、理想の日付が水曜の場合には、同じ週のドラフト予約を指定できることが証明できるのであれば、OptaPlanner は月曜に予約を割り当てる必要はありません。

プランニング枠のサイズは指定できますが、問題領域のサイズを認識しておいてください。問題領域は、スケジュールの作成に使用されるさまざまな要素すべてです。計画期間が長いと、問題領域が大きくなります。

OptaPlanner ワクチン接種予約スケジューラークイックスタートをダウンロードし、Quarkus の開発モードで起動して、ブラウザーでアプリケーションを表示します。Quarkus 開発モードを使用すると、実行中にアプリケーションを変更し、更新できます。

quarkus:dev モードの OptaPlanner ワクチン接種予約スケジューラーで開発作業が完了したら、アプリケーションを従来の jar ファイルとして実行します。

OptaPlanner 従業員スケジューラークイックスタートアーカイブをダウンロードし、Quarkus 開発モードで起動して、ブラウザーでアプリケーションを表示します。Quarkus 開発モードを使用すると、実行中にアプリケーションを変更し、更新できます。

quarkus:dev モードで OptaPlanner 従業員スケジューラーの開発作業が完了したら、アプリケーションを従来の jar ファイルとして実行します。

Spring Boot 製品を備えた Red Hat build of OptaPlanner 向けの授業の時間割プロジェクトの完全な例を表示するには、Red Hat カスタマーポータルからスターターアプリケーションをダウンロードします。

Red Hat build of OptaPlanner の時間割プロジェクトの目標は、レッスンごとに時間枠と部屋に割り当てることです。これには、次の図に示すように、Timeslot、Lesson、および Room の 3 つのクラスを追加します。

高校のスケジュールは毎週 (同じ内容が) 繰り返されるだけなので、時間枠には日付がありません。また、継続的プランニング は必要ありません。解決時に Timeslot インスタンスが変更しないため、Timeslot は 問題ファクト と呼ばれます。このようなクラスには OptaPlanner 固有のアノテーションは必要ありません。

Room インスタンスは解決時に変化しないため、Room は 問題ファクト でもあります。

解決中に、OptaPlanner は、Lesson クラスの timeslot フィールドと room フィールドを変更して、各授業を、時間枠 1 つ、部屋 1 つに割り当てます。OptaPlanner はこれらのフィールドを変更するため、Lesson は プランニングエンティティー となります。

前図では、オレンジのフィールド以外のほぼすべてのフィールドに、入力データが含まれています。授業の timeslot フィールドと room フィールドは、入力データに割り当てられておらず (null)、出力データに割り当てられて (null ではない) います。Red Hat build of OptaPlanner は、解決時にこれらのフィールドを変更します。このようなフィールドはプランニング変数と呼ばれます。このフィールドを OptaPlanner に認識させるには、timeslot フィールドと room のフィールドに @PlanningVariable アノテーションが必要です。このフィールドに含まれる Lesson クラスには、@PlanningEntity アノテーションが必要です。

問題の解決時に スコア で導かれた解の質を表します。スコアが高いほど質が高くなります。Red Hat build of OptaPlanner は、利用可能な時間内で見つかった解の中から最高スコアのものを探し出します。これが 最適 解である可能性があります。

時間割の例のユースケースでは、ハードとソフト制約を使用しているため、HardSoftScore クラスでスコアを表します。

ハード制約は、他のハード制約と比べて、重み付けを行います。ソフト制約は、他のソフト制約と比べて、重み付けを行います。ハード制約は、それぞれの重みに関係なく、常にソフト制約よりも高くなります。

EasyScoreCalculator クラスを実装して、スコアを計算できます。

public class TimeTableEasyScoreCalculator implements EasyScoreCalculator<TimeTable> {

    @Override
    public HardSoftScore calculateScore(TimeTable timeTable) {
        List<Lesson> lessonList = timeTable.getLessonList();
        int hardScore = 0;
        for (Lesson a : lessonList) {
            for (Lesson b : lessonList) {
                if (a.getTimeslot() != null && a.getTimeslot().equals(b.getTimeslot())
                        && a.getId() < b.getId()) {
                    // A room can accommodate at most one lesson at the same time.
                    if (a.getRoom() != null && a.getRoom().equals(b.getRoom())) {
                        hardScore--;
                    }
                    // A teacher can teach at most one lesson at the same time.
                    if (a.getTeacher().equals(b.getTeacher())) {
                        hardScore--;
                    }
                    // A student can attend at most one lesson at the same time.
                    if (a.getStudentGroup().equals(b.getStudentGroup())) {
                        hardScore--;
                    }
                }
            }
        }
        int softScore = 0;
        // Soft constraints are only implemented in the "complete" implementation
        return HardSoftScore.of(hardScore, softScore);
    }

}

残念ながら、この解は漸増的ではないので、適切にスケーリングされません。授業が別の時間枠や教室に割り当てられるたびに、全授業が再評価され、新しいスコアが計算されます。

src/main/java/com/example/solver/TimeTableConstraintProvider.java クラスを作成して、漸増的スコア計算を実行すると、解がより優れたものになります。このクラスは、Java 8 Streams と SQL を基にした OptaPlanner の ConstraintStream API を使用します。ConstraintProvider は、EasyScoreCalculator と比べ、スケーリングの規模が遥かに大きくなっています (O (n²) ではなく O (n))。

package com.example.solver;

import com.example.domain.Lesson;
import org.optaplanner.core.api.score.buildin.hardsoft.HardSoftScore;
import org.optaplanner.core.api.score.stream.Constraint;
import org.optaplanner.core.api.score.stream.ConstraintFactory;
import org.optaplanner.core.api.score.stream.ConstraintProvider;
import org.optaplanner.core.api.score.stream.Joiners;

public class TimeTableConstraintProvider implements ConstraintProvider {

    @Override
    public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
        return new Constraint[] {
                // Hard constraints
                roomConflict(constraintFactory),
                teacherConflict(constraintFactory),
                studentGroupConflict(constraintFactory),
                // Soft constraints are only implemented in the "complete" implementation
        };
    }

    private Constraint roomConflict(ConstraintFactory constraintFactory) {
        // A room can accommodate at most one lesson at the same time.

        // Select a lesson ...
        return constraintFactory.forEach(Lesson.class)
                // ... and pair it with another lesson ...
                .join(Lesson.class,
                        // ... in the same timeslot ...
                        Joiners.equal(Lesson::getTimeslot),
                        // ... in the same room ...
                        Joiners.equal(Lesson::getRoom),
                        // ... and the pair is unique (different id, no reverse pairs)
                        Joiners.lessThan(Lesson::getId))
                // then penalize each pair with a hard weight.
                .penalize(HardSoftScore.ONE_HARD)
                .asConstraint("Room conflict");
    }

    private Constraint teacherConflict(ConstraintFactory constraintFactory) {
        // A teacher can teach at most one lesson at the same time.
        return constraintFactory.forEach(Lesson.class)
                .join(Lesson.class,
                        Joiners.equal(Lesson::getTimeslot),
                        Joiners.equal(Lesson::getTeacher),
                        Joiners.lessThan(Lesson::getId))
                        .penalize(HardSoftScore.ONE_HARD)
                        .asConstraint("Teacher conflict");
    }

    private Constraint studentGroupConflict(ConstraintFactory constraintFactory) {
        // A student can attend at most one lesson at the same time.
        return constraintFactory.forEach(Lesson.class)
                .join(Lesson.class,
                        Joiners.equal(Lesson::getTimeslot),
                        Joiners.equal(Lesson::getStudentGroup),
                        Joiners.lessThan(Lesson::getId))
                        .penalize(HardSoftScore.ONE_HARD)
                        .asConstraint("Student group conflict");
    }

}

TimeTable インスタンスは、単一データセットの Timeslot インスタンス、Room インスタンス、および Lesson インスタンスをラップします。さらに、このインスタンスは、特定のプランニング変数の状態を持つ授業がすべて含まれているため、このインスタンスは プランニングソリューション となり、スコアが割り当てられます。

TimeTable クラスには @PlanningSolution アノテーションが含まれているため、Red Hat build of OptaPlanner はこのクラスに全入出力データが含まれていることを認識します。

具体的には、このクラスは問題の入力です。

ただし、このクラスはソリューションの出力でもあります。

package com.example.domain;

import java.util.List;

import org.optaplanner.core.api.domain.solution.PlanningEntityCollectionProperty;
import org.optaplanner.core.api.domain.solution.PlanningScore;
import org.optaplanner.core.api.domain.solution.PlanningSolution;
import org.optaplanner.core.api.domain.solution.ProblemFactCollectionProperty;
import org.optaplanner.core.api.domain.valuerange.ValueRangeProvider;
import org.optaplanner.core.api.score.buildin.hardsoft.HardSoftScore;

@PlanningSolution
public class TimeTable {

    @ValueRangeProvider(id = "timeslotRange")
    @ProblemFactCollectionProperty
    private List<Timeslot> timeslotList;

    @ValueRangeProvider(id = "roomRange")
    @ProblemFactCollectionProperty
    private List<Room> roomList;

    @PlanningEntityCollectionProperty
    private List<Lesson> lessonList;

    @PlanningScore
    private HardSoftScore score;

    private TimeTable() {
    }

    public TimeTable(List<Timeslot> timeslotList, List<Room> roomList,
            List<Lesson> lessonList) {
        this.timeslotList = timeslotList;
        this.roomList = roomList;
        this.lessonList = lessonList;
    }

    // ********************************
    // Getters and setters
    // ********************************

    public List<Timeslot> getTimeslotList() {
        return timeslotList;
    }

    public List<Room> getRoomList() {
        return roomList;
    }

    public List<Lesson> getLessonList() {
        return lessonList;
    }

    public HardSoftScore getScore() {
        return score;
    }

}

同じロジックに従い、roomList フィールドにも @ValueRangeProvider アノテーションが含まれています。

timeslotList フィールドと roomList フィールドには @ProblemFactCollectionProperty アノテーションが含まれているため、TimeTableConstraintProvider はこれらのインスタンスから選択できます。

lessonList には @PlanningEntityCollectionProperty アノテーションが含まれているため、OptaPlanner は解決時に変更でき、TimeTableConstraintProvider はこの中から選択できます。

これですべて組み合わせ、REST サービスを作成する準備ができました。しかし、REST スレッドで計画問題を解決すると、HTTP タイムアウトの問題が発生します。そのため、Spring Boot スターターでは SolverManager を注入することで、個別のスレッドプールでソルバーを実行して複数のデータセットを並行して解決できます。

package com.example.solver;

import java.util.UUID;
import java.util.concurrent.ExecutionException;

import com.example.domain.TimeTable;
import org.optaplanner.core.api.solver.SolverJob;
import org.optaplanner.core.api.solver.SolverManager;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.web.bind.annotation.PostMapping;
import org.springframework.web.bind.annotation.RequestBody;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RestController;

@RestController
@RequestMapping("/timeTable")
public class TimeTableController {

    @Autowired
    private SolverManager<TimeTable, UUID> solverManager;

    @PostMapping("/solve")
    public TimeTable solve(@RequestBody TimeTable problem) {
        UUID problemId = UUID.randomUUID();
        // Submit the problem to start solving
        SolverJob<TimeTable, UUID> solverJob = solverManager.solve(problemId, problem);
        TimeTable solution;
        try {
            // Wait until the solving ends
            solution = solverJob.getFinalBestSolution();
        } catch (InterruptedException | ExecutionException e) {
            throw new IllegalStateException("Solving failed.", e);
        }
        return solution;
    }

}

この例では、初期実装はソルバーが完了するのを待つので、HTTP タイムアウトがまだ発生します。complete 実装を使用することで、より適切に HTTP タイムアウトを回避できます。

プランニングアプリケーションに終了設定または終了イベントがない場合、理論的には永続的に実行されることになり、実際には HTTP タイムアウトエラーが発生します。これが発生しないようにするには、optaplanner.solver.termination.spent-limit パラメーターを使用して、アプリケーションが終了してからの時間を指定します。多くのアプリケーションでは、この時間を最低でも 5 分 (5m) に設定します。ただし、時間割の例では、解決時間を 5 分に制限すると、期間が十分に短いため HTTP タイムアウトを回避できます。

quarkus.optaplanner.solver.termination.spent-limit=5s

Red Hat build of OptaPlanner Spring Boot の時間割プロジェクトを完了すると、標準 Java main() メソッドで駆動する 1 つの実行可能 JAR ファイルにすべてをパッケージ化します。

$ curl -i -X POST http://localhost:8080/timeTable/solve -H "Content-Type:application/json" -d '{"timeslotList":[{"dayOfWeek":"MONDAY","startTime":"08:30:00","endTime":"09:30:00"},{"dayOfWeek":"MONDAY","startTime":"09:30:00","endTime":"10:30:00"}],"roomList":[{"name":"Room A"},{"name":"Room B"}],"lessonList":[{"id":1,"subject":"Math","teacher":"A. Turing","studentGroup":"9th grade"},{"id":2,"subject":"Chemistry","teacher":"M. Curie","studentGroup":"9th grade"},{"id":3,"subject":"French","teacher":"M. Curie","studentGroup":"10th grade"},{"id":4,"subject":"History","teacher":"I. Jones","studentGroup":"10th grade"}]}'

HTTP/1.1 200
Content-Type: application/json
...

{"timeslotList":...,"roomList":...,"lessonList":[{"id":1,"subject":"Math","teacher":"A. Turing","studentGroup":"9th grade","timeslot":{"dayOfWeek":"MONDAY","startTime":"08:30:00","endTime":"09:30:00"},"room":{"name":"Room A"}},{"id":2,"subject":"Chemistry","teacher":"M. Curie","studentGroup":"9th grade","timeslot":{"dayOfWeek":"MONDAY","startTime":"09:30:00","endTime":"10:30:00"},"room":{"name":"Room A"}},{"id":3,"subject":"French","teacher":"M. Curie","studentGroup":"10th grade","timeslot":{"dayOfWeek":"MONDAY","startTime":"08:30:00","endTime":"09:30:00"},"room":{"name":"Room B"}},{"id":4,"subject":"History","teacher":"I. Jones","studentGroup":"10th grade","timeslot":{"dayOfWeek":"MONDAY","startTime":"09:30:00","endTime":"10:30:00"},"room":{"name":"Room B"}}],"score":"0hard/0soft"}

... Solving started: time spent (33), best score (-8init/0hard/0soft), environment mode (REPRODUCIBLE), random (JDK with seed 0).
... Construction Heuristic phase (0) ended: time spent (73), best score (0hard/0soft), score calculation speed (459/sec), step total (4).
... Local Search phase (1) ended: time spent (5000), best score (0hard/0soft), score calculation speed (28949/sec), step total (28398).
... Solving ended: time spent (5000), best score (0hard/0soft), score calculation speed (28524/sec), phase total (2), environment mode (REPRODUCIBLE).

package com.example.solver;

import java.time.DayOfWeek;
import java.time.LocalTime;
import java.util.ArrayList;
import java.util.List;

import com.example.domain.Lesson;
import com.example.domain.Room;
import com.example.domain.TimeTable;
import com.example.domain.Timeslot;
import org.junit.jupiter.api.Test;
import org.junit.jupiter.api.Timeout;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.test.context.SpringBootTest;

import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertNotNull;
import static org.junit.jupiter.api.Assertions.assertTrue;

@SpringBootTest(properties = {
        "optaplanner.solver.termination.spent-limit=1h", // Effectively disable this termination in favor of the best-score-limit
        "optaplanner.solver.termination.best-score-limit=0hard/*soft"})
public class TimeTableControllerTest {

    @Autowired
    private TimeTableController timeTableController;

    @Test
    @Timeout(600_000)
    public void solve() {
        TimeTable problem = generateProblem();
        TimeTable solution = timeTableController.solve(problem);
        assertFalse(solution.getLessonList().isEmpty());
        for (Lesson lesson : solution.getLessonList()) {
            assertNotNull(lesson.getTimeslot());
            assertNotNull(lesson.getRoom());
        }
        assertTrue(solution.getScore().isFeasible());
    }

    private TimeTable generateProblem() {
        List<Timeslot> timeslotList = new ArrayList<>();
        timeslotList.add(new Timeslot(DayOfWeek.MONDAY, LocalTime.of(8, 30), LocalTime.of(9, 30)));
        timeslotList.add(new Timeslot(DayOfWeek.MONDAY, LocalTime.of(9, 30), LocalTime.of(10, 30)));
        timeslotList.add(new Timeslot(DayOfWeek.MONDAY, LocalTime.of(10, 30), LocalTime.of(11, 30)));
        timeslotList.add(new Timeslot(DayOfWeek.MONDAY, LocalTime.of(13, 30), LocalTime.of(14, 30)));
        timeslotList.add(new Timeslot(DayOfWeek.MONDAY, LocalTime.of(14, 30), LocalTime.of(15, 30)));

        List<Room> roomList = new ArrayList<>();
        roomList.add(new Room("Room A"));
        roomList.add(new Room("Room B"));
        roomList.add(new Room("Room C"));

        List<Lesson> lessonList = new ArrayList<>();
        lessonList.add(new Lesson(101L, "Math", "B. May", "9th grade"));
        lessonList.add(new Lesson(102L, "Physics", "M. Curie", "9th grade"));
        lessonList.add(new Lesson(103L, "Geography", "M. Polo", "9th grade"));
        lessonList.add(new Lesson(104L, "English", "I. Jones", "9th grade"));
        lessonList.add(new Lesson(105L, "Spanish", "P. Cruz", "9th grade"));

        lessonList.add(new Lesson(201L, "Math", "B. May", "10th grade"));
        lessonList.add(new Lesson(202L, "Chemistry", "M. Curie", "10th grade"));
        lessonList.add(new Lesson(203L, "History", "I. Jones", "10th grade"));
        lessonList.add(new Lesson(204L, "English", "P. Cruz", "10th grade"));
        lessonList.add(new Lesson(205L, "French", "M. Curie", "10th grade"));
        return new TimeTable(timeslotList, roomList, lessonList);
    }

}

Spring Boot を使用して Red Hat build of OptaPlanner アプリケーションの例を作成したら、データベースと UI 統合を追加します。

OptaPlanner は、Java アプリケーション用のメトリック計測ライブラリーである Micrometer を介してメトリックを公開します。Prometheus で Micrometer を使用して、学校の時間割アプリケーションで OptaPlanner ソルバーを監視できます。

OptaPlanner 学校の時間割アプリケーションには、Maven または Gradle を使用できます。ビルドファイルを作成したら、次の依存関係を追加します。

Red Hat build of OptaPlanner の時間割プロジェクトの目標は、レッスンごとに時間枠と部屋に割り当てることです。これには、次の図に示すように、Timeslot、Lesson、および Room の 3 つのクラスを追加します。

高校のスケジュールは毎週 (同じ内容が) 繰り返されるだけなので、時間枠には日付がありません。また、継続的プランニング は必要ありません。解決時に Timeslot インスタンスが変更しないため、Timeslot は 問題ファクト と呼ばれます。このようなクラスには OptaPlanner 固有のアノテーションは必要ありません。

Room インスタンスは解決時に変化しないため、Room は 問題ファクト でもあります。

解決中に、OptaPlanner は、Lesson クラスの timeslot フィールドと room フィールドを変更して、各授業を、時間枠 1 つ、部屋 1 つに割り当てます。OptaPlanner はこれらのフィールドを変更するため、Lesson は プランニングエンティティー となります。

前図では、オレンジのフィールド以外のほぼすべてのフィールドに、入力データが含まれています。授業の timeslot フィールドと room フィールドは、入力データに割り当てられておらず (null)、出力データに割り当てられて (null ではない) います。Red Hat build of OptaPlanner は、解決時にこれらのフィールドを変更します。このようなフィールドはプランニング変数と呼ばれます。このフィールドを OptaPlanner に認識させるには、timeslot フィールドと room のフィールドに @PlanningVariable アノテーションが必要です。このフィールドに含まれる Lesson クラスには、@PlanningEntity アノテーションが必要です。

問題の解決時に スコア で導かれた解の質を表します。スコアが高いほど質が高くなります。Red Hat build of OptaPlanner は、利用可能な時間内で見つかった解の中から最高スコアのものを探し出します。これが 最適 解である可能性があります。

時間割の例のユースケースでは、ハードとソフト制約を使用しているため、HardSoftScore クラスでスコアを表します。

ハード制約は、他のハード制約と比べて、重み付けを行います。ソフト制約は、他のソフト制約と比べて、重み付けを行います。ハード制約は、それぞれの重みに関係なく、常にソフト制約よりも高くなります。

EasyScoreCalculator クラスを実装して、スコアを計算できます。

public class TimeTableEasyScoreCalculator implements EasyScoreCalculator<TimeTable> {

    @Override
    public HardSoftScore calculateScore(TimeTable timeTable) {
        List<Lesson> lessonList = timeTable.getLessonList();
        int hardScore = 0;
        for (Lesson a : lessonList) {
            for (Lesson b : lessonList) {
                if (a.getTimeslot() != null && a.getTimeslot().equals(b.getTimeslot())
                        && a.getId() < b.getId()) {
                    // A room can accommodate at most one lesson at the same time.
                    if (a.getRoom() != null && a.getRoom().equals(b.getRoom())) {
                        hardScore--;
                    }
                    // A teacher can teach at most one lesson at the same time.
                    if (a.getTeacher().equals(b.getTeacher())) {
                        hardScore--;
                    }
                    // A student can attend at most one lesson at the same time.
                    if (a.getStudentGroup().equals(b.getStudentGroup())) {
                        hardScore--;
                    }
                }
            }
        }
        int softScore = 0;
        // Soft constraints are only implemented in the "complete" implementation
        return HardSoftScore.of(hardScore, softScore);
    }

}

残念ながら、この解は漸増的ではないので、適切にスケーリングされません。授業が別の時間枠や教室に割り当てられるたびに、全授業が再評価され、新しいスコアが計算されます。

src/main/java/com/example/solver/TimeTableConstraintProvider.java クラスを作成して、漸増的スコア計算を実行すると、解がより優れたものになります。このクラスは、Java 8 Streams と SQL を基にした OptaPlanner の ConstraintStream API を使用します。ConstraintProvider は、EasyScoreCalculator と比べ、スケーリングの規模が遥かに大きくなっています (O (n²) ではなく O (n))。

package com.example.solver;

import com.example.domain.Lesson;
import org.optaplanner.core.api.score.buildin.hardsoft.HardSoftScore;
import org.optaplanner.core.api.score.stream.Constraint;
import org.optaplanner.core.api.score.stream.ConstraintFactory;
import org.optaplanner.core.api.score.stream.ConstraintProvider;
import org.optaplanner.core.api.score.stream.Joiners;

public class TimeTableConstraintProvider implements ConstraintProvider {

    @Override
    public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
        return new Constraint[] {
                // Hard constraints
                roomConflict(constraintFactory),
                teacherConflict(constraintFactory),
                studentGroupConflict(constraintFactory),
                // Soft constraints are only implemented in the "complete" implementation
        };
    }

    private Constraint roomConflict(ConstraintFactory constraintFactory) {
        // A room can accommodate at most one lesson at the same time.

        // Select a lesson ...
        return constraintFactory.forEach(Lesson.class)
                // ... and pair it with another lesson ...
                .join(Lesson.class,
                        // ... in the same timeslot ...
                        Joiners.equal(Lesson::getTimeslot),
                        // ... in the same room ...
                        Joiners.equal(Lesson::getRoom),
                        // ... and the pair is unique (different id, no reverse pairs)
                        Joiners.lessThan(Lesson::getId))
                // then penalize each pair with a hard weight.
                .penalize(HardSoftScore.ONE_HARD)
                .asConstraint("Room conflict");
    }

    private Constraint teacherConflict(ConstraintFactory constraintFactory) {
        // A teacher can teach at most one lesson at the same time.
        return constraintFactory.forEach(Lesson.class)
                .join(Lesson.class,
                        Joiners.equal(Lesson::getTimeslot),
                        Joiners.equal(Lesson::getTeacher),
                        Joiners.lessThan(Lesson::getId))
                        .penalize(HardSoftScore.ONE_HARD)
                        .asConstraint("Teacher conflict");
    }

    private Constraint studentGroupConflict(ConstraintFactory constraintFactory) {
        // A student can attend at most one lesson at the same time.
        return constraintFactory.forEach(Lesson.class)
                .join(Lesson.class,
                        Joiners.equal(Lesson::getTimeslot),
                        Joiners.equal(Lesson::getStudentGroup),
                        Joiners.lessThan(Lesson::getId))
                        .penalize(HardSoftScore.ONE_HARD)
                        .asConstraint("Student group conflict");
    }

}

TimeTable インスタンスは、単一データセットの Timeslot インスタンス、Room インスタンス、および Lesson インスタンスをラップします。さらに、このインスタンスは、特定のプランニング変数の状態を持つ授業がすべて含まれているため、このインスタンスは プランニングソリューション となり、スコアが割り当てられます。

TimeTable クラスには @PlanningSolution アノテーションが含まれているため、Red Hat build of OptaPlanner はこのクラスに全入出力データが含まれていることを認識します。

具体的には、このクラスは問題の入力です。

ただし、このクラスはソリューションの出力でもあります。

package com.example.domain;

import java.util.List;

import org.optaplanner.core.api.domain.solution.PlanningEntityCollectionProperty;
import org.optaplanner.core.api.domain.solution.PlanningScore;
import org.optaplanner.core.api.domain.solution.PlanningSolution;
import org.optaplanner.core.api.domain.solution.ProblemFactCollectionProperty;
import org.optaplanner.core.api.domain.valuerange.ValueRangeProvider;
import org.optaplanner.core.api.score.buildin.hardsoft.HardSoftScore;

@PlanningSolution
public class TimeTable {

    @ValueRangeProvider(id = "timeslotRange")
    @ProblemFactCollectionProperty
    private List<Timeslot> timeslotList;

    @ValueRangeProvider(id = "roomRange")
    @ProblemFactCollectionProperty
    private List<Room> roomList;

    @PlanningEntityCollectionProperty
    private List<Lesson> lessonList;

    @PlanningScore
    private HardSoftScore score;

    private TimeTable() {
    }

    public TimeTable(List<Timeslot> timeslotList, List<Room> roomList,
            List<Lesson> lessonList) {
        this.timeslotList = timeslotList;
        this.roomList = roomList;
        this.lessonList = lessonList;
    }

    // ********************************
    // Getters and setters
    // ********************************

    public List<Timeslot> getTimeslotList() {
        return timeslotList;
    }

    public List<Room> getRoomList() {
        return roomList;
    }

    public List<Lesson> getLessonList() {
        return lessonList;
    }

    public HardSoftScore getScore() {
        return score;
    }

}

同じロジックに従い、roomList フィールドにも @ValueRangeProvider アノテーションが含まれています。

timeslotList フィールドと roomList フィールドには @ProblemFactCollectionProperty アノテーションが含まれているため、TimeTableConstraintProvider はこれらのインスタンスから選択できます。

lessonList には @PlanningEntityCollectionProperty アノテーションが含まれているため、OptaPlanner は解決時に変更でき、TimeTableConstraintProvider はこの中から選択できます。

学校の時間割アプリケーションのすべてのコンポーネントを作成したら、それらをすべて TimeTableApp.java クラスにまとめます。

main() メソッドは以下のタスクを実行します。

通常、アプリケーションには、解決する問題データセットごとに新しい Solver インスタンスを構築するための SolverFactory が 1 つあります。SolverFactory はスレッドセーフですが、Solver はそうではありません。学校の時間割アプリケーションの場合、データセットは 1 つしかないため、Solver インスタンスは 1 つだけです。

完成した TimeTableApp.java クラスは次のとおりです。

package org.acme.schooltimetabling;

import java.time.DayOfWeek;
import java.time.Duration;
import java.time.LocalTime;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

import org.acme.schooltimetabling.domain.Lesson;
import org.acme.schooltimetabling.domain.Room;
import org.acme.schooltimetabling.domain.TimeTable;
import org.acme.schooltimetabling.domain.Timeslot;
import org.acme.schooltimetabling.solver.TimeTableConstraintProvider;
import org.optaplanner.core.api.solver.Solver;
import org.optaplanner.core.api.solver.SolverFactory;
import org.optaplanner.core.config.solver.SolverConfig;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

public class TimeTableApp {

    private static final Logger LOGGER = LoggerFactory.getLogger(TimeTableApp.class);

    public static void main(String[] args) {
        SolverFactory<TimeTable> solverFactory = SolverFactory.create(new SolverConfig()
                .withSolutionClass(TimeTable.class)
                .withEntityClasses(Lesson.class)
                .withConstraintProviderClass(TimeTableConstraintProvider.class)
                // The solver runs only for 5 seconds on this small data set.
                // It's recommended to run for at least 5 minutes ("5m") otherwise.
                .withTerminationSpentLimit(Duration.ofSeconds(5)));

        // Load the problem
        TimeTable problem = generateDemoData();

        // Solve the problem
        Solver<TimeTable> solver = solverFactory.buildSolver();
        TimeTable solution = solver.solve(problem);

        // Visualize the solution
        printTimetable(solution);
    }

    public static TimeTable generateDemoData() {
        List<Timeslot> timeslotList = new ArrayList<>(10);
        timeslotList.add(new Timeslot(DayOfWeek.MONDAY, LocalTime.of(8, 30), LocalTime.of(9, 30)));
        timeslotList.add(new Timeslot(DayOfWeek.MONDAY, LocalTime.of(9, 30), LocalTime.of(10, 30)));
        timeslotList.add(new Timeslot(DayOfWeek.MONDAY, LocalTime.of(10, 30), LocalTime.of(11, 30)));
        timeslotList.add(new Timeslot(DayOfWeek.MONDAY, LocalTime.of(13, 30), LocalTime.of(14, 30)));
        timeslotList.add(new Timeslot(DayOfWeek.MONDAY, LocalTime.of(14, 30), LocalTime.of(15, 30)));

        timeslotList.add(new Timeslot(DayOfWeek.TUESDAY, LocalTime.of(8, 30), LocalTime.of(9, 30)));
        timeslotList.add(new Timeslot(DayOfWeek.TUESDAY, LocalTime.of(9, 30), LocalTime.of(10, 30)));
        timeslotList.add(new Timeslot(DayOfWeek.TUESDAY, LocalTime.of(10, 30), LocalTime.of(11, 30)));
        timeslotList.add(new Timeslot(DayOfWeek.TUESDAY, LocalTime.of(13, 30), LocalTime.of(14, 30)));
        timeslotList.add(new Timeslot(DayOfWeek.TUESDAY, LocalTime.of(14, 30), LocalTime.of(15, 30)));

        List<Room> roomList = new ArrayList<>(3);
        roomList.add(new Room("Room A"));
        roomList.add(new Room("Room B"));
        roomList.add(new Room("Room C"));

        List<Lesson> lessonList = new ArrayList<>();
        long id = 0;
        lessonList.add(new Lesson(id++, "Math", "A. Turing", "9th grade"));
        lessonList.add(new Lesson(id++, "Math", "A. Turing", "9th grade"));
        lessonList.add(new Lesson(id++, "Physics", "M. Curie", "9th grade"));
        lessonList.add(new Lesson(id++, "Chemistry", "M. Curie", "9th grade"));
        lessonList.add(new Lesson(id++, "Biology", "C. Darwin", "9th grade"));
        lessonList.add(new Lesson(id++, "History", "I. Jones", "9th grade"));
        lessonList.add(new Lesson(id++, "English", "I. Jones", "9th grade"));
        lessonList.add(new Lesson(id++, "English", "I. Jones", "9th grade"));
        lessonList.add(new Lesson(id++, "Spanish", "P. Cruz", "9th grade"));
        lessonList.add(new Lesson(id++, "Spanish", "P. Cruz", "9th grade"));

        lessonList.add(new Lesson(id++, "Math", "A. Turing", "10th grade"));
        lessonList.add(new Lesson(id++, "Math", "A. Turing", "10th grade"));
        lessonList.add(new Lesson(id++, "Math", "A. Turing", "10th grade"));
        lessonList.add(new Lesson(id++, "Physics", "M. Curie", "10th grade"));
        lessonList.add(new Lesson(id++, "Chemistry", "M. Curie", "10th grade"));
        lessonList.add(new Lesson(id++, "French", "M. Curie", "10th grade"));
        lessonList.add(new Lesson(id++, "Geography", "C. Darwin", "10th grade"));
        lessonList.add(new Lesson(id++, "History", "I. Jones", "10th grade"));
        lessonList.add(new Lesson(id++, "English", "P. Cruz", "10th grade"));
        lessonList.add(new Lesson(id++, "Spanish", "P. Cruz", "10th grade"));

        return new TimeTable(timeslotList, roomList, lessonList);
    }

    private static void printTimetable(TimeTable timeTable) {
        LOGGER.info("");
        List<Room> roomList = timeTable.getRoomList();
        List<Lesson> lessonList = timeTable.getLessonList();
        Map<Timeslot, Map<Room, List<Lesson>>> lessonMap = lessonList.stream()
                .filter(lesson -> lesson.getTimeslot() != null && lesson.getRoom() != null)
                .collect(Collectors.groupingBy(Lesson::getTimeslot, Collectors.groupingBy(Lesson::getRoom)));
        LOGGER.info("|            | " + roomList.stream()
                .map(room -> String.format("%-10s", room.getName())).collect(Collectors.joining(" | ")) + " |");
        LOGGER.info("|" + "------------|".repeat(roomList.size() + 1));
        for (Timeslot timeslot : timeTable.getTimeslotList()) {
            List<List<Lesson>> cellList = roomList.stream()
                    .map(room -> {
                        Map<Room, List<Lesson>> byRoomMap = lessonMap.get(timeslot);
                        if (byRoomMap == null) {
                            return Collections.<Lesson>emptyList();
                        }
                        List<Lesson> cellLessonList = byRoomMap.get(room);
                        if (cellLessonList == null) {
                            return Collections.<Lesson>emptyList();
                        }
                        return cellLessonList;
                    })
                    .collect(Collectors.toList());

            LOGGER.info("| " + String.format("%-10s",
                    timeslot.getDayOfWeek().toString().substring(0, 3) + " " + timeslot.getStartTime()) + " | "
                    + cellList.stream().map(cellLessonList -> String.format("%-10s",
                            cellLessonList.stream().map(Lesson::getSubject).collect(Collectors.joining(", "))))
                            .collect(Collectors.joining(" | "))
                    + " |");
            LOGGER.info("|            | "
                    + cellList.stream().map(cellLessonList -> String.format("%-10s",
                            cellLessonList.stream().map(Lesson::getTeacher).collect(Collectors.joining(", "))))
                            .collect(Collectors.joining(" | "))
                    + " |");
            LOGGER.info("|            | "
                    + cellList.stream().map(cellLessonList -> String.format("%-10s",
                            cellLessonList.stream().map(Lesson::getStudentGroup).collect(Collectors.joining(", "))))
                            .collect(Collectors.joining(" | "))
                    + " |");
            LOGGER.info("|" + "------------|".repeat(roomList.size() + 1));
        }
        List<Lesson> unassignedLessons = lessonList.stream()
                .filter(lesson -> lesson.getTimeslot() == null || lesson.getRoom() == null)
                .collect(Collectors.toList());
        if (!unassignedLessons.isEmpty()) {
            LOGGER.info("");
            LOGGER.info("Unassigned lessons");
            for (Lesson lesson : unassignedLessons) {
                LOGGER.info("  " + lesson.getSubject() + " - " + lesson.getTeacher() + " - " + lesson.getStudentGroup());
            }
        }
    }

}

main () メソッドは最初に SolverFactory を作成します。

SolverFactory<TimeTable> solverFactory = SolverFactory.create(new SolverConfig()
        .withSolutionClass(TimeTable.class)
        .withEntityClasses(Lesson.class)
        .withConstraintProviderClass(TimeTableConstraintProvider.class)
        // The solver runs only for 5 seconds on this small data set.
        // It's recommended to run for at least 5 minutes ("5m") otherwise.
        .withTerminationSpentLimit(Duration.ofSeconds(5)));

SolverFactory の作成により、以前に作成した @PlanningSolution クラス、@PlanningEntity クラス、および ConstraintProvider クラスが登録されます。

終了設定または terminationEarly() イベントがない場合、ソルバーは永久に実行されます。これを避けるために、ソルバーは解決時間を 5 秒に制限します。

5 秒後、main() メソッドは問題をロードして解決し、解決策を出力します。

        // Load the problem
        TimeTable problem = generateDemoData();

        // Solve the problem
        Solver<TimeTable> solver = solverFactory.buildSolver();
        TimeTable solution = solver.solve(problem);

        // Visualize the solution
        printTimetable(solution);

solve() メソッドはすぐには戻りません。最適解を返す前に 5 秒間実行されます。

OptaPlanner は、利用可能な終了時間内に見つかった最適なソリューションを返します。NP 困難な問題の性質上、特に大規模なデータセットの場合、最適解が最適ではない可能性があります。終了時間を増やして、より良い解決策を見つけてください。

generateDemoData() メソッドは、解決する学校の時間割の問題を生成します。

printTimetable() メソッドは時刻表をコンソールにきれいに出力するので、スケジュールが適切かどうかを視覚的に簡単に判断できます。

学校の時間割 Java アプリケーションのすべてのコンポーネントが完成したので、それらをすべて TimeTableApp.java クラスにまとめて実行する準備が整いました。

info ログは、OptaPlanner がその 5 秒間に何をしたかを示しています。

... Solving started: time spent (33), best score (-8init/0hard/0soft), environment mode (REPRODUCIBLE), random (JDK with seed 0).
... Construction Heuristic phase (0) ended: time spent (73), best score (0hard/0soft), score calculation speed (459/sec), step total (4).
... Local Search phase (1) ended: time spent (5000), best score (0hard/0soft), score calculation speed (28949/sec), step total (28398).
... Solving ended: time spent (5000), best score (0hard/0soft), score calculation speed (28524/sec), phase total (2), environment mode (REPRODUCIBLE).

適切なアプリケーションにはテストが含まれます。timetable プロジェクトで制約とソルバーをテストします。

package org.acme.optaplanner.solver;

import java.time.DayOfWeek;
import java.time.LocalTime;

import javax.inject.Inject;

import io.quarkus.test.junit.QuarkusTest;
import org.acme.optaplanner.domain.Lesson;
import org.acme.optaplanner.domain.Room;
import org.acme.optaplanner.domain.TimeTable;
import org.acme.optaplanner.domain.Timeslot;
import org.junit.jupiter.api.Test;
import org.optaplanner.test.api.score.stream.ConstraintVerifier;

@QuarkusTest
class TimeTableConstraintProviderTest {

    private static final Room ROOM = new Room("Room1");
    private static final Timeslot TIMESLOT1 = new Timeslot(DayOfWeek.MONDAY, LocalTime.of(9,0), LocalTime.NOON);
    private static final Timeslot TIMESLOT2 = new Timeslot(DayOfWeek.TUESDAY, LocalTime.of(9,0), LocalTime.NOON);

    @Inject
    ConstraintVerifier<TimeTableConstraintProvider, TimeTable> constraintVerifier;

    @Test
    void roomConflict() {
        Lesson firstLesson = new Lesson(1, "Subject1", "Teacher1", "Group1");
        Lesson conflictingLesson = new Lesson(2, "Subject2", "Teacher2", "Group2");
        Lesson nonConflictingLesson = new Lesson(3, "Subject3", "Teacher3", "Group3");

        firstLesson.setRoom(ROOM);
        firstLesson.setTimeslot(TIMESLOT1);

        conflictingLesson.setRoom(ROOM);
        conflictingLesson.setTimeslot(TIMESLOT1);

        nonConflictingLesson.setRoom(ROOM);
        nonConflictingLesson.setTimeslot(TIMESLOT2);

        constraintVerifier.verifyThat(TimeTableConstraintProvider::roomConflict)
                .given(firstLesson, conflictingLesson, nonConflictingLesson)
                .penalizesBy(1);
    }

}

Red Hat build of OptaPlanner の時間割プロジェクトを完了後にロギング情報を使用すると、ConstraintProvider で制約が微調整しやすくなります。info ログファイルでスコア計算の速度を確認して、制約に加えた変更の影響を評価します。デバッグモードでアプリケーションを実行して、アプリケーションが行う手順をすべて表示するか、追跡ログを使用して全手順および動きをロギングします。

OptaPlanner は、Java アプリケーション用のメトリック計測ライブラリーである Micrometer を介してメトリックを公開します。Prometheus で Micrometer を使用して、学校の時間割アプリケーションで OptaPlanner ソルバーを監視できます。

最も簡単な方法で OptaWeb 配送経路を使い始めるには、引数を指定せずに runLocally.sh スクリプトを実行します。

対話モードを使用して、ダウンロードした OSM ファイルと、各地域に割り当てられた国コードの一覧を表示します。対話モードを使用すると、Web サイトに移動してダウンロード先を選択せずに Geofabrik から追加の OSM ファイルをダウンロードできます。

非対話モードで OptaWeb 配送経路を使用して、コマンド 1 つで OptaWeb 配送経路を起動し、先ほどダウンロードした OSM ファイルを追加します。これは、地域間を素早く切り替える場合や、デモを行う場合に便利です。

別のデータディレクトリーを使用する場合は、OptaWeb 配送経路が使用するディレクトリーとは異なるデータディレクトリーに更新できます。デフォルトのデータディレクトリーは $HOME/.optaweb-vehicle-routing です。

OptaWeb Vehicle Routing アプリケーションを Red Hat OpenShift にデプロイしたら、バックエンドとフロントエンドを更新できます。

最適な経路を作成するには、OptaWeb 配送経路ユーザーインターフェイスの Demo タブを使用します。

場所を追加/削除したり、車両数を変更したりするたびに、アプリケーションは新しい最適経路を作成して表示します。そのソリューションで複数の車両を使用する場合、アプリケーションは、全車両の経路を別の色で表示します。

OptaWeb 配送経路の他のタブを使用し、追加の情報を表示して設定できます。

ベルギー内の複数の大都市を含むデモデータセットが組み込まれています。Load demo メニューで他のデモを利用する場合は、ご自身のデータセットを用意します。

バックエンドを再起動した後に、Load demo メニューにデータセットディレクトリーのファイルが表示されます。

OptaWeb 配送経路で予期せぬ動作をする場合は、以下の手順に従い、トラブルシューティングを行います。

OptaWeb 配送経路プロジェクトは、マルチモジュールの Maven プロジェクトです。

バックエンドとフロントエンドモジュールは、モジュールツリーの一番下にあります。これらのモジュールには、アプリケーションのソースコードが含まれます。

スタンドアロンモジュールは、バックエンドとフロントエンドを 1 つの実行可能な JAR ファイルに統合するアセンブリーモジュールです。

ディストリビューションモジュールは、最終的なアセンブリーの手順を表します。このモジュールは、スタンドアロンアプリケーションと、ドキュメントを受けとり、配信しやすいようにアーカイブとしてラッピングします。

バックエンドとフロントエンドは、別にビルドとデプロイが可能な、別個のプロジェクトです。実際には、全く異なる言語で記述され、異なるツールでビルドされています。どちらのプロジェクトでも、コードの変更からアプリケーションの実行までの対応時間を短くし、最新の開発体験ができるようにするツールが含まれています。

次のセクションでは、バックエンドとフロントエンドのプロジェクトを開発モードで実行する方法を説明します。

バックエンドモジュールには、Red Hat build of OptaPlanner を使用して配送経路を最適化するサーバー側のアプリケーションが含まれています。最適化は CPU を集中的に使用する計算であり、最大限に能力を発揮するには I/O 操作を回避する必要があります。移動コスト (時間または距離) を最小限に抑えることが主な目的の 1 つであるため、OptaWeb 配送経路では RAM メモリーに移動コストの情報を保持します。OptaPlanner は、解を出す時に、ユーザーが入力した全場所間の移動コストを把握しておく必要があります。この情報は、距離行列 と呼ばれる構造に保存されます。

新しい場所を入力すると、OptaWeb 配送経路は新しい場所と、それ以外でこれまでに入力されたすべての場所との間の移動コストを計算して、距離行列にその移動コストを保存します。移動コストの計算は、GraphHopper の経路エンジンで実行されます。

バックエンドモジュールは、以下のような機能を追加で実装します。

バックエンドコードのアーキテクチャーの詳細は、22章OptaWeb 配送経路のバックエンドアーキテクチャー を参照してください。

次のセクションでは、開発モードでバックエンドを設定して実行する方法を説明します。

フロントエンドのプロジェクトは、Create React App でブートストラップされました。Create React App には、開発や、実稼働環境でアプリケーションをビルドしやすくするためのスクリプトや依存関係が多数含まれています。

以前の図で示されるように、バックエンドコードは 3 つの層で整理されます。

org.optaweb.vehiclerouting
├── domain
├── plugin          # Infrastructure layer
│   ├── persistence
│   ├── planner
│   ├── routing
│   └── rest
└── service         # Application layer
    ├── demo
    ├── distance
    ├── error
    ├── location
    ├── region
    ├── reload
    ├── route
    └── vehicle

service パッケージには、ユースケースを実装するアプリケーション層が含まれます。plugin パッケージにはインフラストラクチャー層が含まれます。

各層のコードは、さらに機能別に編成されます。つまり、各サービスまたはプラグインに独自のパッケージがあります。

コンパイル時間の依存関係は、外層から中心に向けてのみ可能です。このルールに従うことで、ドメインモデルを、基盤となるフレームワークや、他の実装詳細から独立させ、ビジネスエンティティーの動作をより正確にモデル化できます。プレゼンテーションや永続性を周辺に押し出すことで、ビジネスエンティティーとユースケースの動作をより簡単にテストできます。

ドメインには依存関係はありません。

サービスはドメインにだけ依存します。サービスが (データベースまたはクライアントに) 結果を送信する必要がある場合には、出力境界インターフェイスを使用します。実装は contexts and dependency injection (CDI) コンテナーで注入されます。

プラグインは、2 つの方法でサービスに依存します。1 つ目は、ユーザー入力や最適化エンジンによる経路の更新など、イベントを基にサービスを呼び出します。サービスがプラグインに注入され、構築や依存関係の解決の負荷を IoC コンテナーに移動します。2 つ目は、プラグインがサービス出力境界インターフェイスを実装し、変更を永続化してデータベースに保存したり、応答を Web UI に送信したりなど、ユースケースの結果を処理します。

domain パッケージには、business objects が含まれており、Location、Vehicle、Route など、このプロジェクトのドメインをモデル化します。このようなオブジェクトは完全にビジネス指向で、オブジェクトリレーションマッピングツールや Web サービスフレームワークなど、ツールやフレームワークの影響を受けないようにする必要があります。

service パッケージには、ユースケース を実装するクラスが含まれます。ユースケースには、新しい場所の追加、車両の積載量の変更、住所の座標検索など、実行することを記述します。ユースケースを統括するビジネスルールは、ドメインオブジェクトを使用して表現します。

サービスは、永続性、Web、最適化など、外層のプラグインを操作する必要があります。層と層の間の依存関係ルールを満たすには、サービスの依存関係を定義するインターフェイスという観点で、サービスとプラグインの間のやり取りを表現します。プラグインは、サービスの境界インターフェイスを実装する Bean を指定して、サービスの依存関係を満たすことができます。CDI コンテナーは、プラグイン Bean のインスタンスを作成し、ランタイム時にサービスに注入します。これは、制御原理の反転例です。

plugin パッケージには、最適化、永続性、経路、ネットワーク通信などのインフラストラクチャー機能が含まれます。