本記事では、OSSの組合せ最適化ソルバーであるTimefoldを紹介していきます。
Timefoldとは
Javaで実装されたOSSの組合せ最適化ソルバー(以下、ソルバー)です。
ソルバーとは、組合せ最適化問題を解く目的で利用できるツールのことです。
組合せ最適化問題とは、様々な制約の下で多くの選択肢の中から、定義されたスコアによる評価が最も高くなる組合せを求める問題のことです。
巡回セールスマン問題などが広く知られております。
Javaで作られたソルバーとしては、Optaplannerなどが有名です。
今回紹介するTimefoldはOptaplannerをforkしたもので、もともとOptaplannerのコミッターであったエンジニアの方々が開発に携わっています。
サンプルアプリ
Timefoldを使って、簡単な組合せ最適化問題を解いていきます。
サンプルアプリのコード全量はGithubにアップしています。
題材
今回は組合せ最適化の例題として取り上げられることの多い、シフトスケジュールの問題を解きます。
以下のようなケースを考えてみましょう。
- ある会社の1部署(Aさん～Pさんの16人が所属)では、ほとんどの社員が在宅で勤務している
- 宅配などの庶務作業や電話対応のために、毎日何人かの社員はオフィスに出社している必要がある
- それぞれの社員がいつ出社するかを決めるために、当番表を作りたい
- 各社員の都合をヒアリングし、当番表は以下の制約を満たすようにする
| # | 制約 |
|---|---|
| 1 | 1営業日に社員は2人以上出社しなければならない |
| 2 | 全営業日に誰かが出社している必要がある |
| 3 | Fさんは足を怪我しているため、出社できない |
| 4 | Aさんは子供の学校への送迎のため、月火水が望ましい |
| 5 | Dさんは仕事の後飲みに行きたいので金曜日が望ましい |
モデリング
ソルバーを使うには、まずは解決したい問題に関するデータをプログラム上で表現できるように、モデリングする必要があります。
題材の状況において、「出社当番表を作ること」は「社員と営業日との最適な組合せ」を求めることになります。
最適化問題に登場するデータを洗い出し、それぞれの関係性について整理したのが下のモデル図になります。
社員と営業日との組合せを表すデータは、出社当番(Shift)と名付けています。
データクラス定義
モデリングで整理した結果をもとに、データをJavaのクラスとして定義していきます。
まずは、営業日と社員データです。
public class BusinessDay {
private DayOfWeek dayOfWeek;
private LocalDate date;
...
public class Employee {
private String name;
...
次に、営業日と社員の組合せを表現するShiftクラスを定義します。
Timefoldは、入力した営業日・社員データの組合せをShiftデータとして保持して、解の探索に利用します。
Timefoldに組合せを検討してほしいクラスには、@PlanningEntityというアノテーションを付与する必要があります。
また、組合せの選択肢となる営業日・社員のフィールドには、@PlanningVariableを付与します。
@PlanningEntity
public class Shift {
@PlanningId
private Long id;
@PlanningVariable
private BusinessDay businessDay;
@PlanningVariable
private Employee employee;
...
最後にShiftScheduleクラスとなります。
本クラスが、最適化問題の入力データとその解を保持するクラスになります。
businessDays, employeesフィールドには、組合せを考えたい営業日・社員のデータが詰められます。
(最適化問題のInputデータであることをTimefoldに認識させるため、@ValueRangeProvider, @ProblemFactCollectionPropertyアノテーションを付与しています。)
shiftsフィールドには、最適化問題の解となるShiftオブジェクトのリストが詰められます。
(最適化問題の解であることをTimefoldに認識させるため、@PlanningEntityCollectionPropertyアノテーションを付与しています。)
scoreフィールドは、最適化問題の解(今回はList<Shift> shiftsの値)を評価するスコアを保持します。
Timefoldはランダムに生成したShiftの組合せに対して、後述する制約条件を満たしているかを精査し、充足する条件数に応じたスコアを計算します。
スコアが高いほど、当該組合せは望ましい解と認識され、最終的に最もスコアの高くなる解が返されます。
@PlanningSolution
public class ShiftSchedule {
@ValueRangeProvider
@ProblemFactCollectionProperty
private List<BusinessDay> businessDays;
@ValueRangeProvider
@ProblemFactCollectionProperty
private List<Employee> employees;
@PlanningEntityCollectionProperty
private List<Shift> shifts;
@PlanningScore
private HardSoftScore score;
...
制約定義
Javaプログラム上で、最適化問題の制約を定義していきます。
先ほど紹介した社員の要望や、組合せを考えるうえで満たすべきと思われる制約を一覧化します。
| # | 制約種類 | 制約 |
|---|---|---|
| 1 | Hard | 1営業日に同一社員を複数カウントできない |
| 2 | Hard | 1営業日に社員は2人以上出社しなければならない |
| 3 | Hard | 1社員の出社数は4以下でないといけない |
| 4 | Hard | 全営業日に誰かが出社している必要がある |
| 5 | Hard | Fさんは足を怪我しているため、出社できない |
| 6 | Soft | Aさんは子供の学校への送迎のため、月火水が望ましい |
| 7 | Soft | Dさんは仕事の後飲みに行きたいので金曜日が望ましい |
Timefoldでは制約に優先度をつけることができ、Hard制約のほうがSoft制約より優先されます。
実際に上記制約をJavaで実装したものが、次のコードです。
public class ShiftScheduleConstraintProvider implements ConstraintProvider {
@Override
public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
return new Constraint[] {
// Hard constraints
employeeConflict(constraintFactory),
lessThanTwoEmployees(constraintFactory),
penalizeEmployeeShiftTooMany(constraintFactory),
allBusinessDaysAreShifted(constraintFactory),
penalizeFShift(constraintFactory),
// Soft constraints
rewordAShift(constraintFactory),
rewordDShift(constraintFactory),
};
}
private Constraint employeeConflict(ConstraintFactory constraintFactory) {
return constraintFactory
.forEachUniquePair(Shift.class,
Joiners.equal(Shift::getEmployee),
Joiners.equal(shift -> shift.getBusinessDay().getDate()))
.penalize(HardSoftScore.ONE_HARD)
.asConstraint("1営業日に同一社員を複数カウントできない");
}
private Constraint lessThanTwoEmployees(ConstraintFactory constraintFactory) {
return constraintFactory
.forEach(Shift.class)
.groupBy(Shift::getBusinessDay, count())
.filter((businessDay, count) -> count < 2)
.penalize(HardSoftScore.ONE_HARD)
.asConstraint("1営業日に社員は2人以上出社しなければならない");
}
private Constraint penalizeEmployeeShiftTooMany(ConstraintFactory constraintFactory) {
return constraintFactory
.forEach(Shift.class)
.groupBy(Shift::getEmployee, count())
.filter((businessDay, count) -> count > 4)
.penalize(HardSoftScore.ONE_HARD)
.asConstraint("1社員の出社数は4以下でないといけない");
}
private Constraint allBusinessDaysAreShifted(ConstraintFactory constraintFactory) {
return constraintFactory
.forEach(BusinessDay.class)
.join(Shift.class, equal(Function.identity(), Shift::getBusinessDay))
.concat(
constraintFactory.forEach(BusinessDay.class)
.ifNotExists(Shift.class, equal(Function.identity(), Shift::getBusinessDay))
)
.groupBy((businessDay, shift) -> businessDay,
conditionally((businessDay, shift) -> shift != null, countBi())
)
.filter((businessDay, shiftCount) -> shiftCount < 1)
.penalize(HardSoftScore.ONE_HARD)
.asConstraint("全営業日に誰かが出社している必要がある");
}
private Constraint penalizeFShift(ConstraintFactory factory) {
return factory.forEach(Shift.class)
.filter(shift -> shift.getEmployee().getName().equals("F"))
.penalize(HardSoftScore.ONE_HARD)
.asConstraint("Fさんは足を怪我しているため、出社不可");
}
private Constraint rewordAShift(ConstraintFactory factory) {
return factory.forEach(Shift.class)
.filter(shift -> shift.getEmployee().getName().equals("A")
&& (
shift.getBusinessDay().getDayOfWeek().equals(DayOfWeek.MONDAY)
|| shift.getBusinessDay().getDayOfWeek().equals(DayOfWeek.TUESDAY)
|| shift.getBusinessDay().getDayOfWeek().equals(DayOfWeek.WEDNESDAY)
))
.reward(HardSoftScore.ONE_SOFT)
.asConstraint("Aさんは子供の学校への送迎のため、月火水が望ましい");
}
private Constraint rewordDShift(ConstraintFactory factory) {
return factory.forEach(Shift.class)
.filter(shift -> shift.getEmployee().getName().equals("D")
&& shift.getBusinessDay().getDayOfWeek().equals(DayOfWeek.FRIDAY))
.reward(HardSoftScore.ONE_SOFT)
.asConstraint("Dさんは仕事の後飲みに行きたいので金曜日が望ましい");
}
}
メイン処理
Timefoldで最適化問題の解を求める部分のコードは、次のようになります。
public class Main {
public static void main(String[] args) {
SolverFactory<ShiftSchedule> solverFactory = SolverFactory.create(new SolverConfig()
.withSolutionClass(ShiftSchedule.class)
.withEntityClasses(Shift.class)
.withConstraintProviderClass(ShiftScheduleConstraintProvider.class)
.withTerminationSpentLimit(Duration.ofSeconds(5)));
// Load Demo Data
ShiftSchedule problem = DemoDataFactory.createDemoData();
// Solve the problem
Solver<ShiftSchedule> solver = solverFactory.buildSolver();
ShiftSchedule solution = solver.solve(problem);
solution.exportShifts();
}
}
SolverFactoryの生成箇所では、ソルバーを使う前準備として以下を実施しています。
- 問題の解となるクラスの指定
- 制約を定義したクラスの指定
- 答えを探索する時間(例では5秒)
DemoDataFactory.createDemoData()では、16人の社員データと2024年2月の営業日データを作成しています。
データ作成コード(長いので折りたたみ)
public class DemoDataFactory {
public static ShiftSchedule createDemoData() {
List<Employee> employees = createEmployees();
List<BusinessDay> businessDays = createBusinessDays();
// 1営業日に二人社員が出社するので、営業日×2分のShiftを作成
List<Shift> shifts = new ArrayList<>();
long nextId = 0L;
for(int i = 0; i < businessDays.size() * 2; i++) {
shifts.add(new Shift(nextId++));
}
return new ShiftSchedule(businessDays, employees, shifts);
}
private static List<Employee> createEmployees() {
List<Employee> employees = new ArrayList<>();
employees.add(new Employee("A"));
employees.add(new Employee("B"));
employees.add(new Employee("C"));
employees.add(new Employee("D"));
employees.add(new Employee("E"));
employees.add(new Employee("F"));
employees.add(new Employee("G"));
employees.add(new Employee("H"));
employees.add(new Employee("I"));
employees.add(new Employee("J"));
employees.add(new Employee("K"));
employees.add(new Employee("L"));
employees.add(new Employee("M"));
employees.add(new Employee("N"));
employees.add(new Employee("O"));
employees.add(new Employee("P"));
return employees;
}
private static List<BusinessDay> createBusinessDays() {
List<BusinessDay> businessDays = new ArrayList<>();
businessDays.add(new BusinessDay(DayOfWeek.THURSDAY, LocalDate.of(2024, 2, 1)));
businessDays.add(new BusinessDay(DayOfWeek.FRIDAY, LocalDate.of(2024, 2, 2)));
businessDays.add(new BusinessDay(DayOfWeek.MONDAY, LocalDate.of(2024, 2, 5)));
businessDays.add(new BusinessDay(DayOfWeek.TUESDAY, LocalDate.of(2024, 2, 6)));
businessDays.add(new BusinessDay(DayOfWeek.WEDNESDAY, LocalDate.of(2024, 2, 7)));
businessDays.add(new BusinessDay(DayOfWeek.THURSDAY, LocalDate.of(2024, 2, 8)));
businessDays.add(new BusinessDay(DayOfWeek.FRIDAY, LocalDate.of(2024, 2, 9)));
businessDays.add(new BusinessDay(DayOfWeek.TUESDAY, LocalDate.of(2024, 2, 13)));
businessDays.add(new BusinessDay(DayOfWeek.WEDNESDAY, LocalDate.of(2024, 2, 14)));
businessDays.add(new BusinessDay(DayOfWeek.THURSDAY, LocalDate.of(2024, 2, 15)));
businessDays.add(new BusinessDay(DayOfWeek.FRIDAY, LocalDate.of(2024, 2, 16)));
businessDays.add(new BusinessDay(DayOfWeek.MONDAY, LocalDate.of(2024, 2, 19)));
businessDays.add(new BusinessDay(DayOfWeek.TUESDAY, LocalDate.of(2024, 2, 20)));
businessDays.add(new BusinessDay(DayOfWeek.WEDNESDAY, LocalDate.of(2024, 2, 21)));
businessDays.add(new BusinessDay(DayOfWeek.THURSDAY, LocalDate.of(2024, 2, 22)));
businessDays.add(new BusinessDay(DayOfWeek.MONDAY, LocalDate.of(2024, 2, 26)));
businessDays.add(new BusinessDay(DayOfWeek.TUESDAY, LocalDate.of(2024, 2, 27)));
businessDays.add(new BusinessDay(DayOfWeek.WEDNESDAY, LocalDate.of(2024, 2, 28)));
businessDays.add(new BusinessDay(DayOfWeek.THURSDAY, LocalDate.of(2024, 2, 29)));
return businessDays;
}
}
solveメソッドで答えの探索を開始します。
最後に、solution.exportShifts()メソッドにて、Timefoldが生成した当番表のデータをCSV形式で出力しています。
実行結果
メイン関数を実行すると、以下のようなイメージのファイルが出力されます。
2024-02-01,木,N
2024-02-01,木,O
2024-02-02,金,D
2024-02-02,金,M
...
※ サンプルGithub Link
これだけだとぱっと見で分かりづらいので、htmlとJavaScriptで当番表を描画してみます。
以下リンクのhtmlをブラウザで開いて、csvファイルをアップロードすると、当番表が表示されるようになっています。
表示される当番表の例は画像の通りです。(土日祝日はグレーアウト)
社員ごとで当番数にばらつきがあったり、連続して当番になっている社員がいたりと、改善点もありそうですが、ひとまずそれらしい結果がでるようになりました。
参考
Timefold公式ドキュメント
Timefold公式ブログ
紹介したサンプルプログラム