オブジェクトの広場は株式会社オージス総研グループのエンジニアによる技術発表サイトです

OptaPlannerによる組み合わせ最適化

第2回:組合せ最適化でシフトスケジュールを作ってみる

〜サンプルを利用してOptaPlannerの使い方を解説〜
株式会社オージス総研 データアナリシス部
西腋 清行
2015年1月15日

連載第一回目ではメタヒューリスティックな解法とは何かと、スコア値(ペナルティ値)を求める際のポイントについて書きました。連載第二回目の本記事では、実際にコードを見ながらどのような構成になっているかを説明したいと思います。特にペナルティ値を決めるためのDRL(Drools Rule Language)は、JBossのBRMS特有の機能であるため、いくつかのポイントを説明したいと思います。実際にコードを実行する方法や実行した際の動きについては次回に解説したいと思います。

おさらい

本編に入る前に、メタヒューリスティックな解法でシフトスケジュールを作成する際の根本的な考え方をおさらいしておきたいと思います。これを間違っているとDRLでの記述にて、なぜシフトスケジュールが出来上がってくるかが理解できなくなります。

割当てを作成する際の従来の考え方は

*日のこの仕事はAと言うスキルが必要なので、Aスキルを持ちかつ*日は勤務可能な人を抽出
その抽出された人の中から、前後の他の仕事への割当状況からある一定の期間が適切に空いている人を選択する・・・・・・・・

といったように、割当てを行うためのフローを構築していくと思います。 しかし、この方法では業務上の制約が増えると割当てを行うためのフローが膨大になり、かつ負荷平準化を行う際一つ割当てを変えると様々なところへ影響が伝播するという事がよく起こります。

ですのでOptaPlannerは「メタヒューリスティックな解法」、すなわち少しずつ割当てを変えながらより良いものを「探索する」と言うアプローチを採用しています。よって、OptaPlannerでシフトスケジュールを構築する場合には、より良い割当状態を定量的に判断するためのペナルティ値の算出方法を記述が必要です。

例えば、以下がシフトスケジュールを構築する際に用いられるペナルティ値です。

  • 仕事Xに誰も割当てられていない場合:Hardのペナルティ値として10000点追加
  • 仕事Xにある人が割当てられており、その人が妥当なスキルを持っていない場合:Hardのペナルティ値として1000点追加
  • 仕事Xにある人が割当てられており、その人がその日に業務不可能である場合(お休みを取る場合):Hardのペナルティ値として1000点追加
  • 平均的には一人10個の仕事が割当てられるので、実際の割当回数との差を基にSoftのペナルティ値を追加
  • 仕事から次の仕事への期間は平均的には10日になるはずなので、実際の期間との差を基にSoftのペナルティ値を追加

このルールを基に変更前と変更後のペナルティの総数を算出しよりペナルティ値が少ない割当状態を選択、を繰り返すことでより良い割当てを探索していきます。 また、変更前と変更後でどのように人の割当てを変更しているのか?と言う疑問を持たれるかもれませんが、基本的にはランダムに割当てを変更すると思って頂いて問題ありません。その際も、全ての仕事に対して人の割当てを変更するのではなく、ごく一部(場合によっては1つ)だけの割当てを変更してより良い割当状態が変更前か後かを定量的に判断しています。

このようなOptaPlannerが行うメタヒューリスティックな解法の特有の動きの概要を把握しておけば、DRLでの記述でより良いシフトが探索できる理由も理解できるかと思います。

メタヒューリスティックな解法の概要
Figure 1 メタヒューリスティックな解法の概要

サンプルコードにてシフトスケジュール作成を解説

では、実際にコードを見ながらクラスや設定ファイルがどのような役割を持っているかを説明したいと思います。今回のサンプルはOptaPlannerの動作を検証するために独自に作成したものですので、OptaPlannerのexamplesとは大きく異なっていますのでご了承ください。

サンプルコードはhiroba-optaplanner-shift-schedule.zipからダウンロードでき、EclipaeのProjectをZIPにしたものとなっています。

また、OptaPlannerのドキュメントを参照して記事を作成していますが、間違った解釈をしているところがあるかもしれませんのでご了承頂きたく思います。

サンプルではシフトスケジュールの中でも最も簡素なタイプとなっており、以下の条件のもとでシフトスケジュールを作成するデモとなっています。

  • 1日5つの仕事があり100日間の計500個の仕事があります。
  • メンバーは総勢50名います。
  • 各仕事には誰か一人を割当てる必要があります。
  • 各メンバーは公休日や有休申請により担当できない日があり、その日に仕事を割当てることはできません。
  • 一人で同じ日に複数の仕事を担当することはできません。
  • 各仕事には必要なスキルが決まっており、かつ各メンバーは様々なスキルを持っているため、各メンバーがどの仕事が担当可能かの対応表に沿った割当てが必要です。

また、実際のシフトスケジュールを作成する際に大きな問題となる負荷平準化には、以下の点を考慮するものとします。

  • 100日間で各メンバーが割当てられた仕事の個数に差が出ないようにしたい(今回の場合、一人10個の仕事が割当てられること)。
  • 仕事と仕事の間隔はできるだけ公平になるようにしたい。

このようなシフトスケジュールの場合、第一回目にも記述したように「1:N」の関係性からまず初めに思いつくクラス設計は、下図のように人をPlanningValue、仕事をPlanningEntityとするような設計ではないでしょうか。実は今回はこちらとは異なるクラス設計の方がより良いと思われます。

シフトスケジュールを解く際のクラス図
Figure 2 シフトスケジュールを解く際のクラス図

OptaPlannerの動きを考慮したクラスの設計

Solverは割当てを組替える前と後を比較するために、PlanningSolution(シフトスケジュールの割当状態をまとめるJobSolutionクラスに該当)をクローンして複数インスタンスを保持しています。その際PlanningEntity(Jobクラスに該当)もクローンされるため、設計に若干の考慮が必要な場合もあります。(ちなみにPlanningValueクラスやその他のクラスは、クローンの対象にはならないようです)

そこで、前述のように「仕事」そのものをPlanningEntityとするのではなく、「仕事」と「人」を結びつける(割当てる)ための関連クラスをPlanningEntityとする方法があります。関連クラスには、「仕事」と「人」を関係づけるためのプロパティだけが存在するため非常にシンプルになり、クローンの影響も最小限に抑えることができるのではないかと思います。 以降のサンプルでは、以下のようにPlanningEntityとしてJobAssignmentクラスを導入しています。

JobAssignmentを導入したクラス図
Figure 3 JobAssignmentを導入したクラス図
JobAssignmentを導入した際の割当変更
Figure 4 JobAssignmentを導入した際の割当変更

AbstractPersistableクラス

AbstractPersistableは、PlanningSolutionクラス・PlanningEntityクラス・PlanningValueクラスの派生元になります。このクラスは現在のところ主に共用的に利用するIDやインスタンスを識別する名前を保持するための実装と、compareToメソッドのベースが入っています。

OptaPlanner Ver6系ではあまり必要性は高くないようです。以前のバージョンのサンプルではequalsメソッドをオーバーライドしてIDを利用して同一インスタンスの判別していたようですが、Ver6でこれを行うと動作がおかしくなることもありましたので注意してください。

JobSolutionクラス

これはPlanningSolutionにあたるクラスとなり、最適化を行う問題を一つにまとめる役割を持っています。Solverに組合せ問題を与えるときや、最適化計算後の結果を受け取る際に利用するクラスにもなり、org.optaplanner.core.impl.solution.Solutionの派生クラスとし、PlanningSolutionアノテーションを付ける必要があります。

@PlanningSolution
public class JobSolution extends AbstractPersistable
                         implements Solution<HardSoftBigDecimalScore> {

Solutionクラスはジェネリスクとなっており、スコア付の方法を指定する必要があります。ペナルティ値は第一回目にもあるようにHard、Medium、Softがあり、問題の種類により3つのうちどれを利用するか決める必要があります。また、ペナルティ値の保持の仕方も、Integer、Long、BigDecimalの3種のうちから選択する必要があり、以下の組合せが定義されています。

スコアリングの定義
スコアリングの定義概要
org.optaplanner.core.api.
score.buildin.simple.
SimpleScore
ペナルティ値をカテゴリ分けせず計算を行う場合に利用します。
ペナルティ値はIntegerで管理されるため、ペナルティ値がオーバーフローしないように注意する必要があります。
org.optaplanner.core.api.
score.buildin.simplelong.
SimpleLongScore
ペナルティ値をカテゴリ分けせず計算を行う場合に利用します。
ペナルティ値はLongで管理されるため、ペナルティ値がオーバーフローしないように注意する必要があります。
org.optaplanner.core.api.
score.buildin.simplebigdecimal.
SimpleBigDecimalScore
ペナルティ値をカテゴリ分けせず計算を行う場合に利用します。
ペナルティ値はBigDecimalで管理されるので、オーバーフローすることはありません。
org.optaplanner.core.api.
score.buildin.hardsoft.
HardSoftScore
HardとSoftの2つカテゴリを利用して計算を行う場合に利用します。
ペナルティ値はIntegerで管理されるため、ペナルティ値がオーバーフローしないように注意する必要があります。
org.optaplanner.core.api.
score.buildin.hardsoftlong.
HardSoftLongScore
HardとSoftの2つカテゴリを利用して計算を行う場合に利用します。
ペナルティ値はLongで管理されるため、ペナルティ値がオーバーフローしないように注意する必要があります。
org.optaplanner.core.api.
score.buildin.hardsoftbigdecimal.
HardSoftBigDecimalScore
HardとSoftの2つカテゴリを利用して計算を行う場合に利用します。
ペナルティ値はBigDecimalで管理されるので、オーバーフローすることはありません。
org.optaplanner.core.api.
score.buildin.hardmediumsoft.
HardMediumSoftScore
HardとMediumとSoftの3つカテゴリを利用して計算を行う場合に利用します。
ペナルティ値はIntegerで管理されるため、ペナルティ値がオーバーフローしないように注意する必要があります。
org.optaplanner.core.api.
score.buildin.bendable.
BendableScore
まだ使い道がわかりません。

またDouble型を利用したものも存在していますが、利用は推奨されていません。浮動小数点を利用すると、小数点以下の判断で不具合が発生することもあります。またBigDecimalを利用する場合も経験上、少数の利用は避けた方が良いようです。

さらにInteger、Longを利用する際はペナルティ値の総計が大きくなりオーバーフローが発生する場合がある事も注意してください。シフトスケジュールの初期の割当状態ではペナルティ値が想像以上の大きくなっている場合もあります。このような際にオーバーフローが発生し的確に定量的な比較ができなくなり、不具合が発生することがあります。

このようにスコアリングの定義だけでもたくさんありますが選択のポイントとしては、問題の規模(シフトスケジュールの対象となる仕事数とメンバー数)でInteger、Long、BigDecimalのどれを利用するかを決め、シフトスケジュールのように絶対守るべきルール(休みの日には割当てない、など)と負荷平準化の両方を考慮しないといけない場合、「HardSoft」を選択します。よって今回のデモでは、HardSoftBigDecimalScoreを利用しています。

Factの登録

FactとはDRL内で利用するJavaインスタンスの事です。OptaPlannerが利用するDRLはもともとBRMSの仕組みで、BRMSでも問題を解くために利用するJavaインスタンスをFactと呼んでいます。

前述にもありますが、PlanningSolutionは最適化を行う問題を一つにまとめる役割を持っているので、シフトスケジュールを作成する際に必要な全ての情報をインスタンス変数として保持しています。それらのインスタンス変数は業務上の制約ルールを記述するためDRLから利用されるので「登録処理」が必要となり、getProblemFactsメソッドをオーバーライドしDRLからアクセスしたいインスタンスの登録処理を行います。 例外的に、後述のPlanningEntityとして定義されたインスタンスはgetProblemFactsメソッドでの登録は不要です。

  @Override
  public Collection<? extends Object> getProblemFacts() {
    List<Object> facts = new ArrayList<Object>();
    facts.addAll(this.peopleList);
    facts.addAll(this.jobList);
    facts.addAll(this.dayList);
    facts.add(this.solutionParameter);
    return facts;
  }

新しくインスタンス変数を追加したものの、DRLから参照できない場合や意図しない動作をする場合、getProblemFactsメソッドの編集を忘れていないかチェックしてみてください。また、addメソッドとaddAllメソッドがあるので登録するインスタンス変数が配列であるか否かもよく確認してください。

@PlanningEntityCollectionProperty

PlanningEntityにあたるクラス(サンプルではJobAssignmentクラス)のListのgetterにPlanningEntityCollectionPropertyアノテーションを付けます。これは、Solverが割当ての組替え作業をする際にPlanningEntityをどこから取得すれば良いかを示すために必要なものです。

  @PlanningEntityCollectionProperty()
  public List<JobAssignment> getJobAssignmentList() {
    return this.jobAssignmentList;
  }

@ValueRangeProvider

PlanningValueにあたるクラス(サンプルではPeopleクラス)のgetterにValueRangeProviderアノテーションを付けます。これは、Solverが割当ての組替え作業をする際にPlanningValueをどこから取得すれば良いかを示すために必要なものです。

  @ValueRangeProvider(id = "peopleList")
  public List<People> getPeopleList() {
    return this.peopleList;
  }

JobAssignmentクラス

これはPlanningEntityにあたるクラスとなり、前述のようにJobとPeopleのプロパティを持っておりクローンの対象になります。JobAssignmentとJobは1:1の関係性で固定されているので組合せを探索する際は変化しませんが、Peopleのプロパティは探索を行う際に様々なPeopleのインスタンスが設定され、「ある仕事はこの人に割当てる」という表現を実現しています。

PlanningEntityにあたるクラスにはPlanningEntityアノテーションを付ける必要があります。

@PlanningEntity(difficultyComparatorClass = JobAssignmentDifficultyComparator.class)
public class JobAssignment extends AbstractPersistable {

DifficultyComparator

Solverが割当ての初期状態を構築する際にいくつかの手法が利用可能ですが、割当てる条件が厳しいものから先に割当てる方が全体的により良い初期状態を作成することができる場合があります。よってどのPlanningEntityが条件として厳しいのか判断するためのComparatorを設定します。

サンプルには実装していませんが、例えば非常に高スキルを要する仕事で担当可能な人が少ない場合などです。別の例を示すと分かりやすいかもしれませんが、荷物(PlanningEntity)を詰込む箱(PlanningValue)を決める問題の場合、より大きな荷物から詰込み先の箱を決め、徐々に小さい荷物の詰込み先の箱を決めた方がより簡単に多くの荷物を詰込むことができると思います。

ですので、この場合は荷物の大きさを比較できるComparatorを作成します。

public class ItemDifficultyComparator implements Comparator<Item>,
                                                 Serializable {
  @Override
  public int compare(final Item arg0, final Item arg1) {
    return new CompareToBuilder()
      .append(arg0.getSize(), arg1.getSize ())
      .append(arg0.getId(), arg1.getId())
      .toComparison();
  }
}

CompareToBuilderを利用する際、数値が大きいほど「割当てる条件が厳しい」と判断していますので、上記のような順番で比較を行います。逆に、数値が小さい方がより「割当てる条件が厳しい」と判断するような問題であった場合は、比較する際の引数の順番を逆転する必要があります。

@PlanningVariable

PlanningEntityにPlanningValueのインスタンスを設定することで組合せを表現しますので、PlanningValueのプロパティ(getter、setter)が必要となります。サンプルではJobAssignmentクラスのpeopleプロパティの事となり、PlanningVariableアノテーションを付けます。

  @PlanningVariable(
    strengthComparatorClass = PeopleStrengthComparator.class,
    nullable = true,
    valueRangeProviderRefs = { "peopleList" }
  )
  public People getPeople() {
    return this.people;
  }

シフトスケジュールを作成する際、条件次第ではあえて仕事には誰も割当てないという事もあるかもしれません。そのような場合はプロパティにnullを設定することで誰も当てられていないことを表現できます。サンプルではnullable=trueとしているため、どうしても条件上割当てられる人がいない場合には誰も割当てないという状態としてnullを設定できるようになっています。

また、重要なものとしてvalueRangeProviderRefsには、PlanningVariableをどこから取得するかを指定します。つまりPeopleのインスタンスをどこから持ってくるか?をSolverに教える働きがあります。ここに指定する値は、ValueRangeProviderアノテーションのidに指定したものとなり、複数指定することも可能です。

strengthComparator

前述の「DifficultyCoparator」で、Solverが割当ての初期状態を構築する際に割当てる条件が厳しいものから割当てる方が全体的に良い初期状態を作成することができる場合があると説明しましたが、PlanningVariableの選択も同様のアプローチを採用した方が良い場合があります。

サンプルには実装していませんが、例えば勤務条件が厳しく担当できる時間が限られている人がいる場合などです。前述にもある別の例を示すと分かりやすいかもしれませんが、荷物(PlanningEntity)を詰込む箱(PlanningValue)を決める問題の場合、より小さい箱から詰め、徐々に大きい箱に詰込んでいく方がより簡単に多くの荷物を詰込むことができます。

ですので、この場合は箱の大きさを比較できるComparatorを作成します。

public class ContainerStrengthComparator implements Comparator<Container>,
                                                    Serializable {
  @Override
  public int compare(final Container arg0, final Container arg1) {
    return new CompareToBuilder()
      .append(arg0.getSize(), arg1.getSize ())
      .append(arg0.getId(), arg1.getId())
      .toComparison();
    }
  }

StrengthComparatorでは、より余裕のあるもの(箱が大きいもの)を「強度が強い」、より余裕がないもの(箱が小さいもの)を「強度が弱い」という表現で扱っており、数値が大きいほど「強度が強い」と認識されます。 よって、上記のような順番で比較を行います。 逆に、数値が小さい方がより「強度が強い」と判断するような問題であった場合は、比較する際の引数の順番を逆転する必要があります。

Peopleクラス

これはPlanningValueにあたるクラスとなり、アノテーションなどは不要で純粋なJavaBeansで作成できます。

シフトスケジュールの場合はメンバーが公休日や有休申請により担当できない日があるため、Dayクラスを指定することでその日は担当可能か否かを取得できる機能を実装する必要があります。

  private HashMap<Day, Boolean> attendanceMap;
 
  public HashMap<Day, Boolean> getAttendanceMap() {
    return this.attendanceMap;
  }

  public void setAttendanceMap(final HashMap<Day, Boolean> attendanceMap) {
    this.attendanceMap = attendanceMap;
  }

  public boolean isAttendance(final Day day) {
    return this.attendanceMap.get(day);
  }

また、メンバーが保有するスキルを基に事前に担当可能な仕事がわかっているとして、Jobクラスを指定することでその仕事が担当可能か否かを取得できる機能も実装する必要があります。

  private HashMap<Job, Boolean> skillMap;

  public HashMap<Job, Boolean> getSkillMap() {
    return this.skillMap;
  }

  public void setSkillMap(final HashMap<Job, Boolean> skillMap) {
    this.skillMap = skillMap;
  }

  public boolean isSkill(final Job job) {
    return this.skillMap.get(job);
  }

今回のサンプルでは簡素化するためメンバーがどの仕事を担当可能であるかを事前に処理したデータをMapに持たせていますが、担当可否の判定が複雑な場合はJavaコードでさらに実装できます。また、比較的簡単な判定の場合や判定方法の変化が多い場合は後述するDRLで記述する方法もあります。

DRL(Drools Rule Language)の書き方

OptaPlannerが行うメタヒューリスティックな解法で最も重要なスコア付は、Drools Rule Languageで業務上の制約を記述して行う方法があります。Javaで記述することもできるのですが、DRLで記述する方がパフォーマンス上良くなるメリットがあるためDRLでの記述をお勧めします。 Drools Rule Languageの言語仕様については、以下のDroolsのドキュメントの「Chapter 7. Rule Language Reference」を参照してください。

http://docs.jboss.org/drools/release/6.0.1.Final/drools-docs/html_single/#DroolsLanguageReferenceChapter

では、最も簡単な業務上の制約を例にしてDRLがどのようなものかを示したいと思います。

DRLヘッダー部分

package jp.co.ogis_ri.optaplanner.jobSolution.solver;
    dialect "java"

import java.lang.Math;
import java.math.BigDecimal;

import org.optaplanner.core.api.score.buildin.hardsoftbigdecimal.HardSoftBigDecimalScoreHolder

import jp.co.ogis_ri.optaplanner.jobSolution.domain.JobSolution;
import jp.co.ogis_ri.optaplanner.jobSolution.domain.JobAssignment;
import jp.co.ogis_ri.optaplanner.jobSolution.domain.Job;
import jp.co.ogis_ri.optaplanner.jobSolution.domain.People;
import jp.co.ogis_ri.optaplanner.jobSolution.domain.Job;
import jp.co.ogis_ri.optaplanner.jobSolution.domain.Day;
import jp.co.ogis_ri.optaplanner.jobSolution.domain.SolutionParameter

global HardSoftBigDecimalScoreHolder scoreHolder;

「package」は通常のJavaと同じもので、「dialect」はDRL内でロジックを記述する際に利用する方式を指定します。サンプルではjava方式を利用していますが、BRMSのマニュアルによると「mvel」も使えるようです。

「import」もJavaでのものと同じです。「global」はDRL内のどこでも利用可能な変数を指定するもので、ScoreHolderは算出したペナルティ値を追加するのに必要であるため必ず記述します。サンプルでは「HardSoft」方式でBigDecimalを利用するとしましたので「HardSoftBigDecimalScoreHolder」となります。

DRLでの業務上の制約を記述、ペナルティを追加する方法

まずOptaPlannerでのペナルティ値の考えのおさらいですが、より値が高い方がより良い割当てと判断します。シフトスケジュールの場合、多くの場合は行ってはいけない割当てが規定されている場合が多いので、行ってはいけない割当てを探し出しマイナス値のペナルティを加算していく方式になります。

ですので、割当てルールに違反している箇所があり負荷にも偏りがある場合はペナルティ値が大きなマイナスの値になりますが、探索を行うことで割当てルールに違反しておらず負荷平準化も良くなり、ペナルティ値が0に近づいていきます。

探索中のペナルティ値の推移
Figure 5 探索中のペナルティ値の推移

いざ実業務のシフトスケジュールをこの方式で作成しようとした場合、先程にもあった「行ってはいけない割当て」ではなく「割当てる際の処理フロー」が既に規定されていることが多いと思います。ですので、実業務に展開する際は少し発想を転換し、実際に人手でシフトを作成したい際の処理フローから「行ってはいけない割当てとは?」を導き出すようにしてみてください。

またシフトスケジュールの作成担当者にヒアリングを行うと、処理フローの裏に隠された業務的な制約を理解されているので、「行ってはいけない割当て」を整理しやすくなります。

仕事は必ず誰かが担当すること

シフトスケジュールでは仕事に人を割当てる必要がありますが、前述しているpeopleプロパティにはnullable = trueとなっているPlanningVariableアノテーションがついています。つまりpeopleプロパティがnullになり、仕事に誰も割当てられない可能性もあります。例えば、お休みの人が多い日があり、かつその日の仕事は高スキルが必要となると、どうしても人を割当てることができない仕事も発生しえます。

しかし、シフトスケジュールを作成するからには出来る限り仕事に人を割当てたいため、割当てが行われていない仕事は減らす必要があります。よって、人が割当てられていない仕事にはペナルティを与え、より良い割当て状態を判定できるようにする必要があります。

ではこれをDRLで記述してみましょう。

DRLではfor文などでJavaインスタンスを一つずつ条件確認するような記述は不要で、一行の記述により条件に適合するJavaインスタンスを全て取得できます。例の場合PlanningEntityであるJobAssignmentのpeopleプロパティがnullであるインスタンスを全て取得できるようにし、誰も割当てられていない仕事の一覧を取得するように記述しています。

thenの部分では、条件に適合したJavaインスタンスに対してどのような処理を行うか、を記述します。仮に500個の仕事のうち10個の仕事に誰も割当てられていない場合、10個のJobAssignmentインスタンスがwhenに記述された条件により取得され、thenの中のロジックは10回呼び出されます。

ペナルティ追加にはaddSoftConstraintMatchメソッドを利用し、Softのペナルティを追加します。なぜSoftにペナルティを追加するのかですが、お休みの人が多い日があるとどうしても人を割当てることができない仕事も発生する可能性もあり、必ず人を割当てられるとは言えません。よって、条件次第では仕事を割当てられない仕事も許す場合などはSoftを利用する方法があります。

rule "requiredPeople"
  when
    JobAssignment(people == null)
  then
    scoreHolder.addSoftConstraintMatch(kcontext, new BigDecimal(-10000));
end

前述の500個の仕事のうち10個の仕事に誰も割当てられていない場合を例にすると、-10000のペナルティ値をSoftに対して10回追加することとなり、計-100000のsoftのペナルティ値を持つこととなります。

仮に、割当状態を少し変更し500個の仕事のうち9個の仕事に誰も割当てられていない状態を作ることができると計-90000のsoftのペナルティ値を持つ状態へ変わり、より良い割当て状態と定量的に判断できるわけです。

その仕事は担当可否がある

シフトスケジュールを割当てる際、その仕事を担当できる人を割当てることは重要なことです。ですので、割当てられた人は必ずその仕事を行うスキルを有している必要があり、これもDRLで記述しておかなければなりません。実際に仕事を行うためのスキルを有しているかの確認は、業務により様々ですのでサンプルの実装は一つの例として見て頂ければと思います。

サンプルではPeopleクラスには与えられた仕事が自分自身で担当可能であるかを判定するためのgetSkillメソッドを作ってあります。実装自体は単純でJobインスタンスを与えれば、スキル的に担当可能であればtrueを、スキル的に担当不可能であればfalseを返すだけです。

その判定用メソッドをどのように呼び出すかの例として、以下のように記述する方法があります。まず全てのJobAssignmentインスタンスの中からpeopleプロパティがnullではないものを抽出します。次に、peopleプロパティに設定されているPeopleインスタンスに対してgetSkillメソッドを呼び出してスキル的に仕事が担当可能であるかを取得し、担当不可能であると判断されるJobAssignmentインスタンスを抽出したいので「== false」が付けてあります。また、getSkillメソッドを呼び出す際の引数「job」は、JobAssignmentインスタンスのjobプロパティの値となります。

rule "skill"
  when
    JobAssignment(people != null, people.getSkill(job) == false)
  then
    scoreHolder.addHardConstraintMatch(kcontext, new BigDecimal(-1));
end

このような記述により、人を割当ててはみたもののスキル的には実際はダメな割当状態である仕事を抽出することができます。そこでthenの中でペナルティを追加しますが、仕事に割当てられた人がスキル的に担当可能である事は必須であるため、違反した場合(スキル的に担当不可能な人が割当てられている)はHardのペナルティに追加します。このように、絶対守らなければならない業務上のルールがある場合は、Hardのペナルティに追加していくのが基本となります。

仮に500個の仕事のうち5個の仕事に対して本来スキル的に担当不可能な人が割当てられている場合、計-5のHardのペナルティが追加されます。

その日は休みではないこと

スキルの有無の判定と同じく、その日が担当可能であるかも非常に重要な項目です。基本的な構成はスキルの判定と同じです。 「people != null」により人が割当てられてことを判定し、「people.getAttendance(job.day) == false」により割当てられた人はその日は担当不可能ではないかを判定します。これにより、人を割当ててみたものの実はその人はその日は休みの日で担当不可能である状態になってしまっている仕事を取得しています。

rule "attendance"
  when
    JobAssignment(people != null, people.getAttendance(job.day) == false)
  then
    scoreHolder.addHardConstraintMatch(kcontext, new BigDecimal(-1));
end

仮に500個の仕事のうち7個の仕事が人は割当ててみたものの実はその人はその日は休みの日で担当不可能な状態になってしまっている場合、計-7のHardのペナルティが追加されます。

同じ日に複数の仕事は担当しないこと

今回のシフトスケジュールには1日に5つの仕事がありますが、一人で同じ日の仕事を複数担当することはできないという業務上の条件を規定しています。これも、実際のシフトスケジュールでは良くあることと思います。「同じ日」ではなく「同じ時間帯」という事も多いと思いますが、この考えを応用すれば「同じ時間帯では複数の仕事は担当できない」という条件も記述できます。

ここでDRLの記述上のポイントを解説したいと思います。

まず変数の代入方法です。

一般的に良く使われる「=」ではないので注意して頂きたいところです。DRLで変数への代入は「:」を利用します。「$job1 : job」とあると、jobプロパティの値を$job1という変数に代入する、という事になります。代入した変数のそれ以降の任意の場所で条件判定などに利用できますし、またthenの中でペナルティ値を算出にも利用可能です(これは後述する負荷平準化で利用しています)

次にDRLで抽出を複数記述したときの動きです。

DRLでは条件に合致したインスタンスの一覧を取得しますが、次の行が実行される際は事前に抽出されたインスタンスのそれぞれに対して繰り返し実行されます。 例えば、以下のDRLですと

rule "requiredDuplication"
  when
    JobAssignment($job1 : job,  people != null, $people1 : people, $day : job.day)
    JobAssignment(job != $job1, people != null, people == $people1, job.day == $day)
  then
    scoreHolder.addHardConstraintMatch(kcontext, new BigDecimal(-1));
end
  • まず3行目の記述で誰かが割当てられている(people != null)全ての仕事がまず抽出されます。
  • 次に、4行目の条件でさらに条件に合致する仕事が抽出されます。この際、3行目の条件で抽出された仕事に関する情報が「$job1」「$people1」「$day」変数に格納されていますので、4行目の条件で抽出される仕事は、「同じ仕事以外(job != $job1)」かつ「誰かが割当てられており(people != null)」かつ「3行で抽出した仕事に割当てられている人と4行で抽出した仕事に割当てられている人が同じ(people == $people1)」かつ「同じ日の仕事(job.day == $day)」となります。
  • 最後に「同じ日に同じ人が割当てられてしまった仕事の組合せ」が存在すると業務上の制約に違反することになりますので、then中でペナルティを追加することとなります。

このDRLでの記述を通常のJavaで記述すると、どのように動いているか理解しやすいかと思います。

全仕事(全てのJobAssignmentインスタンス)に対してfor文を2回適用させ、仕事の全ての組合せを表現し、同じ日に複数の仕事を同じ人が担当していないかチェック。もし同じ日に複数の仕事を同じ人が担当していればペナルティを追加します。 このようにAndで複数の条件を積み重ねていく必要がある場合も、DRLをうまく利用すると簡単に記述することができます。

for (JobAssignment jobAssignment1 : jobAssignmentList) {
  if(jobAssignment1.getPeople() != null){
    for (JobAssignment jobAssignment2 : jobAssignmentList) {
      if(jobAssignment2.getPeople() != null){
        if(jobAssignment1 != jobAssignment2 && 
           jobAssignment1.getPeople() == jobAssignment2.getPeople() &&
           jobAssignment1.getJob().getDay() == jobAssignment2.getJob().getDay()){
          //同じ日に同じ人が割当てられてしまった仕事の組合せがあるので
          //業務上の制約違反としてペナルティを追加
        }
      }
    }
  }
}

担当回数の差は小さくすること

シフトスケジュールを作成する際、メンバーの負荷を均等にするために担当回数を同じにする、または担当回数の差をできるだけ小さくするというのは通常行われると思います。このような負荷平準化は暗黙的に行われているので業務上の制約として明記されていない場合も多いかもしれませんが、メタヒューリスティックな解法でシフトスケジュールを作成する際は明記しなければなりません。そうしなければ担当回数が極端に偏った割当てが作成されてしまいます。

以下のDRLの記述では、whenで各メンバーの仕事の担当回数を算出し、thenで平均的な仕事の担当回数との差をペナルティとして追加しています。

rule "countLeveling"
  when
    $solutionParameter : SolutionParameter()
    $people : People()
    $jobCountPerPeople : Number() from accumulate(
      $jobAssignment : JobAssignment( people == $people ), count( $jobAssignment ) )
  then
    scoreHolder.addSoftConstraintMatch(kcontext,
      new BigDecimal((int)(-10000D * Math.pow($solutionParameter.getCountAverage() - $jobCountPerPeople.doubleValue(), 2) )));
end

まずはwhenの中の1行目のSolutionParameterは各種情報が入ったJavaBeanで、thenの中で利用するために記述しています。SolutionParameterのインスタンスは1つしか存在しないようにしているため、実質上はあまり条件記述としては機能しておらず、単に各種情報を読み取るために存在させています。(もっと良い方法がないか、今後調査したいところでもあります)

2行目からが条件記述としての本番です。

  • まず全てのメンバーを抽出します。「People()」とカッコの中に条件が記述されていないので全てのメンバーが抽出されることとなります。
  • 次に、accumulate句の前半の「$jobAssignment : JobAssignment( people == $people )」により、あるメンバーに割当てられた仕事を全て抽出し$jobAssignment変数に代入します
  • さらにaccumulate句の後半のcount( $jobAssignment )で、$jobAssignment変数に代入されている仕事の数(JobAssignmentインスタンスの数)を計算し、$jobCountPerPeople変数にJavaのNumberクラスとして代入します。

これによりwhenの最後では$jobCountPerPeople変数にメンバー毎の担当回数が入っています。

最後にthenで平均的な仕事の担当回数との差をペナルティとして追加しますが、メンバーが50名いれば$jobCountPerPeople変数は50名分の各担当回数が入っていますので、thenの中の処理は実際50回行われることとなります。

では、「平均的な仕事の担当回数との差」をどのようにペナルティとして表現するかが問題になるのですがここでも2つの工夫を行っています。

まず、1つ目ですが平均的な負荷を事前に求められる場合は事前に計算を行っておきます。例のような単純なスケジューリングですと各メンバーが10回担当することが事前に求められ(全てで500個の仕事があり、メンバーは総勢50名いますので)、その情報はSolutionParameterのCountAverageプロパティに入れてあります。よって「平均的な仕事の担当回数との差」は、実際の担当回数である$jobCountPerPeople変数の値とCountAverageプロパティの値の差分を取ります。

次に2つ目の工夫として「平均的な仕事の担当回数との差分の二乗値」をペナルティとして追加するという事です。単純に考えると平均値からの差分の絶対値をペナルティ値にする方法もありますが、平準化するには不適切な面もあります。 例えば以下の場合、ペナルティ値はそれぞれ同じになりますが、実施のシフトスケジューリングを作っている場合は「1.」の方がより平準化されていると判断している場合が多いのではないでしょうか。

  • 平均値である10回から1回ずれている人(9回の人と11回の人)が計5名いる
  • 平均値である10回から5回ずれている人(5回の人または15回の人)が1名いる

この場合、「平均値からの差分の絶対値」をペナルティとして利用すると、両方の場合でペナルティは「5」となりどちらが良いか定量的に判断できなくなります。特に、シフトスケジューリングでの担当回数の平準化の際、全仕事数は事前に決まっておりメンバーへの割り振りを決めるわけですから「誰かの担当回数が減れば誰かの担当回数が増える」といったような動きをし、絶対値でペナルティを求めるといかなる割当状態でも平準化に関するペナルティ値はいつも同じ値となるという現象が発生しかねません。

よって平均値からの差分の二乗値を利用する方法があります。 この方法でのペナルティ値はそれぞれ以下のようになります

  • 平均値である10回から1回ずれている人(9回の人と11回の人)が計5名いる場合、12×5 =5 のペナルティ
  • 平均値である10回から5回ずれている人(5回の人または15回の人)が1名いる場合、52×1 =25 のペナルティ

となり「1.」の方がより平準化されていると定量的に判断することができます。 このように、平準化を記述する際は「二乗値を利用する」と言う方法もある事を知っておくと便利かと思います。

仕事と仕事の間隔に大きな差が出ないようにすること

さらに負荷平準化の観点からよく考慮されるのは仕事を担当してから次の仕事までの期間です。シフトスケジュールを作成する期間の前半ではあるメンバーがメインで担当し、後半では別のメンバーがメインで担当するような偏りが出てしまうと、全体としてメンバーの負荷が大きくなってしまうことになります。

あるメンバーに割当てられた仕事と仕事の間隔の平均的な値は、全ての仕事数と期間・メンバー数がわかっていると事前に大まかな値が分かるかと思います。ですので、担当回数の平準化の時と同じように、実際の仕事と仕事の間隔の日数と平均的な値の差分の2乗値をペナルティとして追加する方法にしています。

では、実際の仕事と仕事の間隔の日数をどのように取得すればよいか、となりますが以下の4行目と6行目の条件式により取得する方法が考えられます。 4行目の「JobAssignment($job : job, people != null, $people : people, $day1 : job.day)」では、メンバーが割当てられている仕事を全て抽出します。次に6行目のaccumulate句の前半にて、4行で抽出された仕事よりも後の仕事で、かつ同じ人が割当てられている仕事の一覧を抽出します。そしてaccumulate句の後半にて、min句を利用して最も間隔が小さい仕事の組合せを取得することで、実際の仕事と仕事の間隔の日数を取得します。

rule "intervalLeveling1"
  when
    $solutionParameter : SolutionParameter()
    JobAssignment($job : job,  people != null, $people : people, $day1 : job.day)
    exists JobAssignment(job != $job ,people == $people, job.day.getDayValue() > $day1.getDayValue())
    $intervalLevelingMin : Number() from accumulate(JobAssignment(job != $job ,people == $people, job.day.getDayValue() > $day1.getDayValue() , $day2 : job.day ), min( $day2.getDayValue() - $day1.getDayValue() ) )
  then
    scoreHolder.addSoftConstraintMatch(kcontext,
      new BigDecimal((int)(-1D * Math.pow($solutionParameter.getIntervalDayAverage() - $intervalLevelingMin.doubleValue(),2) )));
end

実際にメンバーに仕事を割当てられた状態をメンバーと日付で整理した表にすると分かりやすいかもしれません。

メンバーに仕事を割り当てられた状態

4行目の条件式でメンバーが割当てられた仕事が全て抽出されるので、上記の表にある6個の仕事は全て抽出されます。

次に、6行目の式が6個の仕事についてそれぞれ判定されますので例として「仕事6」を見てみると、「仕事6」より後にあり、かつ同じメンバーが割当てられている仕事として「仕事31」と「仕事42」が抽出されます。これがaccumulate句の前半で行っていることで、accumulateの後半では抽出された「仕事6」と「仕事31」、「仕事6」と「仕事42」の日付に差を計算、そのうち最も小さいものを取得し$intervalLevelingMin変数にしれています。

これにより、「仕事6」は「5日間」と言う値が計算されますし、「仕事1」については「4日間」、「仕事21」についても「4日間」、「仕事31」については「2日間」、と言ったように間隔の値が求められます。

最後に、thenの中では事前に計算で求めている平均的な間隔の値との差分の二乗値をペナルティとして追加します。例えば平均的な間隔の値が「5日間」とすると

  • 「仕事1」については「4日間」と求められているので、差分が「1日間」で実際のペナルティ値は12で1
  • 「仕事21」については「4日間」と求められているので、差分が「1日間」で実際のペナルティ値は12で1
  • 「仕事6」については「5日間」と求められているので、差分が「0日間」で実際のペナルティ値は02で0
  • 「仕事31」については「2日間」と求められているので、差分が「3日間」で実際のペナルティ値は32で9

と、計11のペナルティが追加されることになります。

5行目のexistsは、後の仕事でかつ同じ人が担当している仕事が存在しない場合にaccumulate句が実行されないように入れています。「仕事41」や「仕事42」では後の仕事でかつ同じ人が担当している仕事が存在しないため意図しない動作をしたため、existsにて後の仕事でかつ同じ人が担当している仕事が存在していることを条件として追加しています。

ペナルティのウェイト

softに属する業務上の制約である負荷平準化や優先順位を上記のような方法でペナルティ値を算出する場合、完全な理想的な割当てとなりペナルティが0になることは稀だと思います。実際にシフトスケジュールを作成する際にメタヒューリスティックな解法を利用するということは、様々な条件によって簡単なフローで割当てができず、平準化を行おうとすると「あちらを立てればこちらが立たず」という事が発生してしまうような状態だと思います。つまり、これが「ペナルティが0にならない」という事です。

ですので、softのペナルティはある程度の値は残りながらより良い割当て状態を探すこととなりますが、「あちらを立てればこちらが立たず」と言うように「割当てを少し変えると仕事と仕事の間隔はより均一になるが、メンバー間の担当回数の差が開いてしまう」という状態をどのように解決するか、が問題です。

これはある程度は腹をくくり、業務上優先させたい制約を決めその制約のペナルティ値にはウェイトをかける方法があります。

サンプルでも担当回数の平準化には「-10000」という大きなウェイトをかけてあります。これにより、割当てを少し変えると仕事と仕事の間隔はより均一になるがメンバー間の担当回数の差が開いてしまう、と言う場合には、仕事と仕事の間隔がより均一になることによるペナルティ低下量よりもメンバー間の担当回数の差が開いてしまうことによるペナルティ増加量の方がはるかに大きくなりますから、よりメンバー間の担当回数を優先的に同じにしようと動作します。

設定ファイルの書き方

OptaPlannerの設定ファイルには様々なことが記述可能ですが、まずはサンプルを実行するために最低限必要な項目を解説します。

各クラスの指定

PlanningSolutionとPlanningEntityはJavaコードにアノテーションがつけられていますが、設定ファイルでも明示する必要があります。

PlanningSolutionアノテーションを付けたクラス名をsolutionClassタグの中に記述します。

<solutionClass>jp.co.ogis_ri.optaplanner.jobSolution.domain.JobSolution</solutionClass>

PlanningEntityアノテーションを付けたクラス名をentityClassタグの中に記述します。

<entityClass>jp.co.ogis_ri.optaplanner.jobSolution.domain.JobAssignment</entityClass>

(後に機会があれば、PlanningEntityが複数ある最適化問題の場合の記述方法も紹介したいと思います)

ペナルティ値の種類と計算方法の指定

ペナルティ値の種類とはPlanningSolutionクラスにある「スコアリングの定義」のことです。これもアノテーションで記述はしていますが、設定ファイルにもscoreDefinitionTypeタグで明示します。

<scoreDirectorFactory>
  <scoreDefinitionType>HARD_SOFT_BIG_DECIMAL</scoreDefinitionType>
</scoreDirectorFactory>
スコアリングの定義とscoreDefinitionTypeタグの値の対応
スコアリングの定義scoreDefinitionTypeタグの値
org.optaplanner.core.api.
score.buildin.simple.
SimpleScore
SIMPLE
org.optaplanner.core.api.
score.buildin.simplelong.
SimpleLongScore
SIMPLE_LONG
org.optaplanner.core.api.
score.buildin.simplebigdecimal.
SimpleBigDecimalScore
SIMPLE_BIG_DECIMAL
org.optaplanner.core.api.
score.buildin.hardsoft.
HardSoftScore
HARD_SOFT
org.optaplanner.core.api.
score.buildin.hardsoftlong.
HardSoftLongScore
HARD_SOFT_LONG
org.optaplanner.core.api.
score.buildin.hardsoftbigdecimal.
HardSoftBigDecimalScore
HARD_SOFT_BIG_DECIMAL
org.optaplanner.core.api.
score.buildin.hardmediumsoft.
HardMediumSoftScore
HARD_MEDIUM_SOFT
org.optaplanner.core.api.
score.buildin.bendable.
BendableScore
BENDABLE

次に、ペナルティ値を計算するために利用するDRLのファイルをscoreDrlタグで指定します。

<scoreDirectorFactory>
  <scoreDrl>jp/co/ogis_ri/optaplanner/jobSolution/solver/optaplannerJobSolutionScoreRules.drl</scoreDrl>
</scoreDirectorFactory>
※OptaPlanner 6.1.0 より、先頭に「/」は不要になっています。 OptaPlanner 6.0.1までのバージョンでは、先頭に「/」が必要なので、バージョン移行の際は修正してください。

計算終了条件の設定

メタヒューリスティックな解法では割当てを少しずつ変えながら何回もペナルティ値の比較を行っていきますので、終了条件がないと永遠に計算を行うことになります。ですので、ペナルティ値の比較を終了させる条件を指定しておきます。

終了条件は様々ありますが、主に経過時間を条件するものと、ペナルティ値(スコア値)を条件にするものがありますので適切なものを選択してください。下記の例では、1分間でペナルティ値の比較を終了しますので、1分間で見つけることが可能な最も良い割当て状態を探し出す、という動作になります。

<termination>
  <minutesSpentLimit>1</minutesSpentLimit>
</termination>

その他、以下のような条件が記述可能です。

各タグの意味
タグ名概要
millisecondsSpentLimit 指定したミリ秒で計算を停止します。
secondsSpentLimit 指定した秒で計算を停止します。
minutesSpentLimit 指定した分で計算を停止します。
hoursSpentLimit 指定した時間で計算を停止します。
unimprovedMillisecondsSpentLimit 指定したミリ秒の間、ベストスコアの更新が行わなければ探索を停止します。
unimprovedSecondsSpentLimit 指定した秒の間、ベストスコアの更新が行わなければ探索を停止します。
unimprovedMinutesSpentLimit 指定した分の間、ベストスコアの更新が行わなければ探索を停止します。
unimprovedHoursSpentLimit 指定した時間の間、ベストスコアの更新が行わなければ探索を停止します。
bestScoreLimit ベストスコアが一定以上になった場合に探索を停止させます。
SimpleScoreの場合
 <bestScoreLimit>0</bestScoreLimit>
HardSoftScoreの場合
 <bestScoreLimit>
  0hard/-5000soft
 </bestScoreLimit>
HardMediumSoftの場合
 <bestScoreLimit>
   0hard/0medium/-5000soft
 </bestScoreLimit>
BendableScoreの場合
 <bestScoreLimit>
   0/0/0/-5000
 </bestScoreLimit>
bestScoreFeasible
stepCountLimit 指定したステップ数で探索を停止します。
unimprovedStepCountLimit 指定したステップ数の間、ベストスコアの更新が行わなければ探索を停止します。

複数を記述することもでき、いずれかでも条件を満たすとメタヒューリスティックの計算を停止させます。また、条件を複数記述した場合に全ての条件が満たされた場合に計算を停止させるには、以下の記述を追加してください。

<terminationCompositionStyle>AND</terminationCompositionStyle>

時・分・秒を表すタグを同時に記述した場合、合算される仕様となっています。 例えば以下の記述では、計算を開始してから1時間30分で探索を終了します。

<termination>
  <hoursSpentLimit>1</hoursSpentLimit>
  <minutesSpentLimit>30</minutesSpentLimit>
</termination>

初期解の作成方法の設定

メタヒューリスティックな解法で問題を解く際、初期の割当てを作成しておく必要があります。 この初期の割当てがもともと良い割当て状態であれば、より短い時間でより良い割当てを探し出せる可能性が高くなります。よって、適切な初期の割当てを作成する必要があるのですが、OptaPlannerではひとまず一般的に良く利用されるより良い割当て状態を作成する手法を実装しているのでそれを利用すると良いと思います。

<constructionHeuristic>
  <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
</constructionHeuristic>

ただ、明確により良い初期の割当て状態を作成する方法が分かっている場合、自らその割当て状態を作成してからメタヒューリスティックな解法(後述のlocalSearch)を実行しても構いません。constructionHeuristicタグを記述しなければ、OptaPlannerによる初期解の作成はスキップされますので、自ら作成した初期解を基にメタヒューリスティックな解法を用いてより良い割当ての探索を行えます。

この点で注意したいのは、「メタヒューリスティックな解法」を利用するというのは明確に作成できる割当フローでは対応できないような制約が複雑な問題である場合だと思います。よって「より良い初期の割当て状態」を作るロジックもやり過ぎると非常に複雑で処理時間もかかってしまい、メタヒューリスティックな解法を活用する価値がなくなってしまうこともありますので、バランスも重要となります。

メタヒューリスティックな解法の指定

メタヒューリスティックな解法では少しずつ割当てを組替えながらより良い割当てを探索しますが、実際には様々なアルゴリズムが提唱されています。OptaPlannerでは主に3つのアルゴリズムを実装しており、どのアルゴリズムを利用するかを指定する必要があります。

利用するアルゴリズムはacceptorタグにどのタグを記述するかで決まりますので、適切を思われるタグを記述してください。また、アルゴリズムによっては組合せて利用できるものもありますので、詳細はOptaPlannerのドキュメントを参照してください。

アルゴリズムのタグ名と意味
タグ名アルゴリズム
entityTabuSize 禁断探索法を利用します。
simulatedAnnealingStartingTemperature 模擬焼きなまし法を利用します。
lateAcceptanceSize Late Acceptance Hill-Climbing法を利用します。

各アルゴリズムの概要については機会があれば紹介したいと思いますし、第一回目でも紹介した共立出版「メタヒューリスティクスの数理」で禁断探索法と擬焼きなまし法は解説されています。

禁断探索法の記述例

<acceptor>
<entityTabuSize>10</entityTabuSize>
<forager>
<acceptedCountLimit>1</acceptedCountLimit>
</forager>
</acceptor>

模擬焼きなまし法の記述例

<acceptor>
<simulatedAnnealingStartingTemperature>1hard/1000000soft</simulatedAnnealingStartingTemperature>
<forager>
<acceptedCountLimit>1</acceptedCountLimit>
</forager>
</acceptor>

Late Acceptance Hill-Climbing法の記述例

<localSearch>
<acceptor>
<lateAcceptanceSize>400</lateAcceptanceSize>
</acceptor>
<forager>
<acceptedCountLimit>1</acceptedCountLimit>
</forager>
</localSearch>

ここで大きな問題となるのは、解こうとしているシフトスケジューリング問題やその他の組合せ最適化問題で、どのアルゴリズムを利用すれば良いのか、パラメータはどの値が良いかをどうやって判断するかと言う点です。アルゴリズムにより探索時の動作が異なりますし、パラメータが異なることでもより良い組合せを見つけ出す効率が異なります。よって、アルゴリズムを選択しパラメータを設定できるようになるには、それなりの勉強と問題の性格の把握、経験が必要になると思いますが、実際にはかなり難しい事と思います。

そこで、OptaPlannerではどのアルゴリズムのどのパラメータ設定が最も適しているのかを、ベンチマークを取得することで把握できる機能が用意されています。このベンチマーク機能を利用すれば、複数の指定したアルゴリズム・パラメータの値で計算を実施し、ペナルティ値がどのように変化するかをグラフ化してくれます。このベンチマーク機能は今後の利用方法を紹介したいと思います。

探索範囲の指定

メタヒューリスティックな解法では変更前と変更後のペナルティ値を比較しより良い組合せを探索します。この際、デフォルトの設定では組み替えパターンの全てを試し最も良いスコアの組合せを選択していきます。例えば「10/1の仕事に割当てられたAさんと、10/2の仕事に割当てられたBさんを入れ替える」「10/1の仕事に割当てられたAさんと、10/3の仕事に割当てられたCさんを入れ替える」「10/1の仕事に割当てられたAさんと、10/4の仕事に割当てられたDさんを入れ替える」、と言ったように組み替えるパターンは様々存在します。ただ、問題の規模が大きくなると(仕事の数が多いなど)パフォーマンス上の問題も発生するため、試行するパターン数を制限することができます。

パターン数を制限するにはacceptedCountLimitエレメントを記述します。

<forager>
  <acceptedCountLimit>1000</acceptedCountLimit>
</forager>

また、各パターンのスコアを求めて最も良いものを選択する際も、実際に選択される組合せをどのタイミングで選択するかの設定も可能です。

<forager>
  <pickEarlyType>FIRST_BEST_SCORE_IMPROVING</pickEarlyType>
</forager>
pickEarlyTypeの値の意味
pickEarlyTypeの値
NEVER デフォルトの設定で、全てのパターン(acceptedCountLimitの設定がある場合は、そのパターン数まで)の組合せを作成し、スコアを計算して最も良いものを選択します。 同じスコアの物が複数ある場合は、ランダムに一つ選ばれます。
FIRST_BEST_SCORE_IMPROVING 組合せを一つ作り、スコアを計算してベストスコアを更新した場合にその組合せを選択し、そのステップを終了する
FIRST_LAST_STEP_SCORE_IMPROVING 組合せを一つ作り、スコアを計算して最終ステップのスコアを更新した場合にそのパターンを選択し、そのステップを終了する

まとめ

第二回目は、サンプルコードを基にOptaPlannerの各構成がどのような目的を持っているかを説明しました。 第三回目は、実際にこのサンプルコードを実行しどのように動作するのかを紹介したいと思います。

『Opta Planner』は、Redhat JBoss BRMS『Business Resource Planner』のコミュニティ版です