Hello World

Appearance

OptaPlanner ​

OptaPlanner 是一个AI(人工智能)约束求解器，它可以优化规划和调度问题，例如:车辆路线规划，人员排班，云端优化，任务分配，会议日程安排，生产车间调度，背包问题及很多其它规划类问题。每个组织都面临着以下挑战: 需要将一组有限的、受约束的资源（如员工，资产，时间 和/或资金）分配到产品或服务中去。OptaPlanner提供更高效的规划，从而降低生产成本并提高服务质量。

OptaPlanner是一款轻量级，可嵌入的规划引擎。通过它，我们使普通的Java™程序，即可有效地解决优化问题。它还与其它JVM语言（如Kotlin和Scala）兼容。这些约束被应用于普通业务领域对象，并可以调用现有代码。使用这个引擎，不需要将这些约束以数学规划模型的形式输入。在引擎内部，OptaPlanner将复杂的AI优化算法（如禁忌搜索，模拟退火，延迟接受和其他元启发式算法）与一些非常有效的约束评分计算技术，还有其他最先进的约束求解技术相结合起来。

OptaPlanner是一个基于Apache软件许可的开源软件。它使用100％纯Java™编写，可运行在任何JVM上，也可以在Maven中心库中找到。

什么是规划问题? ​

规划问题在有限的资源和特定的约束条件下有一个最优目标。最优目标可以是任意数量的东西，例如:

  • 利润最大化——最优目标导致最高可能的利润。
  • 最小化生态足迹——最优目标对环境的影响最小。
  • 员工或客户满意度最大化——最优目标优先考虑员工或客户的需求。

实现这些目标的能力取决于可用资源的数量，例如:

  • 人数。
  • 时间的总量。
  • 预算。
  • 实物资产，如机器、车辆、计算机、建筑物等。

还必须考虑到与这些资源有关的具体限制，例如一个人工作的小时数，他们使用某些机器的能力，或设备部件之间的兼容性。

OptaPlanner帮助Java程序员有效地解决约束满足问题。在底层，它结合了优化启发式和元启发式，具有非常高效的分数计算。

规划问题是NP-complete或NP-hard ​

上述所有用例可能都是NP-complete/NP-hard，用外行人的话来说就是:

  • 在合理的时间内验证给定的问题解决方案是很容易的。
  • 没有什么灵丹妙药能在合理的时间内找到问题的最优解。

这意味着非常可怕:解决你的问题可能比你想象的要难，因为两种常见的技术是不够的:

  • 蛮力算法(即使是更聪明的变体)将花费太长时间。
  • 一个快速的算法，例如在装箱中，首先放入最大的物品，将返回一个远不是最优的解决方案。

通过使用先进的优化算法，OptaPlanner能够在合理的时间内为此类规划问题找到接近最优的解决方案。

规划问题有(硬的和软的)约束 ​

通常，规划问题至少有两个层次的约束:

  • 一个(消极的)硬约束不能被打破。例如:一个老师不能同时教两门不同的课。
  • 如果可以避免，则不应打破(消极)软约束。A老师不喜欢在星期五下午上课。

有些问题也有积极的约束:

  • 如果可能的话，应该实现积极的软约束(或奖励)。B老师喜欢在星期一上午上课。

一些基本问题(如N个皇后)只有硬约束。有些问题有三个或更多层次的约束，例如硬约束、中等约束和软约束。

这些约束定义了规划问题的分数计算(又称适应度函数)。规划问题的每个解决方案都可以打分。使用OptaPlanner，分数约束是用面向对象的语言编写的，比如Java代码。这样的代码简单、灵活且可扩展。

规划问题有很大的搜索空间 ​

一个规划问题有许多解决方案。有几类解决方案:

  • 一个可能的解决方案是任何解决方案，无论它是否打破了任何数量的约束。规划问题往往有大量可能的解决方案。这些解决方案中的许多都是毫无价值的。

  • 可行的解决方案是不打破任何(消极的)硬约束的解决方案。可行解决方案的数量趋向于相对于可能解决方案的数量。有时没有可行的解决方案。每个可行的解决方案都是一个可能的解决方案。

  • 最优解是得分最高的解。规划问题往往有一个或几个最优解决方案。总有至少一个最优解，即使没有可行解且最优解不可行。

  • 找到的最佳解决方案是实现在给定时间内找到的得分最高的解决方案。找到的最佳解决方案很可能是可行的，而且只要有足够的时间，它就是最优解决方案。

与直觉相反的是，即使使用小数据集，可能的解决方案的数量也是巨大的(如果计算正确的话)。正如您在示例中看到的，大多数实例的可能解决方案比已知宇宙中的最小原子数(10^80)多得多。因为没有找到最优解决方案的灵丹妙药，任何实现都被迫评估所有这些可能解决方案的至少一个子集。

OptaPlanner支持多种优化算法，可以有效地处理大量可能的解决方案。根据用例的不同，一些优化算法会比其他算法表现得更好，但这是不可能提前判断的。使用OptaPlanner，通过在几行XML或代码中更改求解器配置，很容易切换优化算法。

快速入门 ​

快速入门都使用OptaPlanner来优化学生和教师的学校时间表。

Java快速入门 ​

构建一个简单的Java应用程序，使用OptaPlanner为学生和教师优化学校时间表。

你将建造什么？ ​

您将构建一个命令行应用程序，为学生和教师优化学校时间表:

log
...
INFO  Solving ended: time spent (5000), best score (0hard/8soft), ...
INFO  
INFO  |            | Room A     | Room B     | Room C     |
INFO  |------------|------------|------------|------------|
INFO  | MON 08:30  | 物理         | 语文         |            |
INFO  |            | 老师M        | 老师P        |            |
INFO  |            | 九年级        | 八年级        |            |
INFO  |------------|------------|------------|------------|
INFO  | MON 09:30  | 物理         | 语文         |            |
INFO  |            | 老师M        | 老师P        |            |
INFO  |            | 八年级        | 九年级        |            |
INFO  |------------|------------|------------|------------|
INFO  | MON 10:30  | 化学         | 语文         |            |
INFO  |            | 老师M        | 老师P        |            |
INFO  |            | 九年级        | 八年级        |            |
INFO  |------------|------------|------------|------------|
INFO  | MON 13:30  | 政治         |            | 数学         |
INFO  |            | 老师C        |            | 老师A        |
INFO  |            | 九年级        |            | 八年级        |
INFO  |------------|------------|------------|------------|
INFO  | MON 14:30  | 生物         |            | 数学         |
INFO  |            | 老师M        |            | 老师A        |
INFO  |            | 八年级        |            | 九年级        |
INFO  |------------|------------|------------|------------|
INFO  | TUE 08:30  | 地理         |            | 数学         |
INFO  |            | 老师C        |            | 老师A        |
INFO  |            | 九年级        |            | 八年级        |
INFO  |------------|------------|------------|------------|
INFO  | TUE 09:30  |            | 英语         | 数学         |
INFO  |            |            | 老师I        | 老师A        |
INFO  |            |            | 八年级        | 九年级        |
INFO  |------------|------------|------------|------------|
INFO  | TUE 10:30  | 化学         | 英语         |            |
INFO  |            | 老师M        | 老师I        |            |
INFO  |            | 八年级        | 九年级        |            |
INFO  |------------|------------|------------|------------|
INFO  | TUE 13:30  | 历史         | 英语         |            |
INFO  |            | 老师C        | 老师I        |            |
INFO  |            | 九年级        | 八年级        |            |
INFO  |------------|------------|------------|------------|
INFO  | TUE 14:30  | 历史         |            | 数学         |
INFO  |            | 老师C        |            | 老师A        |
INFO  |            | 八年级        |            | 九年级        |
INFO  |------------|------------|------------|------------|

您的应用程序将通过使用AI来坚持硬和软调度约束，自动将Lesson实例分配给Timeslot和Room实例，例如:

  • 一个教室最多只能同时上一节课。
  • 一个老师一次最多只能教一节课。
  • 一个学生一次最多只能上一节课。
  • 老师喜欢在同一个教室里教所有的课。
  • 老师喜欢连续上课，不喜欢课间的间隔。
  • 学生不喜欢同一学科上连续的课。

从数学上讲，学校课程表是一个NP-hard问题。这意味着它很难扩展。对于一个重要的数据集，即使是在超级计算机上，简单地暴力迭代所有可能的组合也需要数百万年的时间。幸运的是，OptaPlanner等人工智能约束求解器拥有先进的算法，可以在合理的时间内提供近乎最优的解决方案。

为领域对象建模 ​

你的目标是将每节课分配到一个timeslot和一个room。你将创建这些类:

问题事实 ​
Timeslot ​

Timeslot类表示授课的时间间隔，例如，周一10:30 - 11:30或周二13:30 - 14:30。为了简单起见，所有timeslot都有相同的持续时间，并且在午餐或其他休息时间没有timeslot。

timeslot没有日期，因为高中的时间表只是每周重复一次。所以不需要持续的规划。

  • Timeslot.java
java
package study.helloworld.optaplanner.schooltimetabling.domain;

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

public class Timeslot {

	private DayOfWeek dayOfWeek;

	private LocalTime startTime;

	private LocalTime endTime;

	public Timeslot() {
	}

	public Timeslot(DayOfWeek dayOfWeek, LocalTime startTime,
			LocalTime endTime) {
		this.dayOfWeek = dayOfWeek;
		this.startTime = startTime;
		this.endTime = endTime;
	}

	@Override
	public String toString() {
		return "Timeslot [dayOfWeek=" + dayOfWeek + ", startTime=" + startTime
				+ ", endTime=" + endTime + "]";
	}

	public DayOfWeek getDayOfWeek() {
		return dayOfWeek;
	}

	public void setDayOfWeek(DayOfWeek dayOfWeek) {
		this.dayOfWeek = dayOfWeek;
	}

	public LocalTime getStartTime() {
		return startTime;
	}

	public void setStartTime(LocalTime startTime) {
		this.startTime = startTime;
	}

	public LocalTime getEndTime() {
		return endTime;
	}

	public void setEndTime(LocalTime endTime) {
		this.endTime = endTime;
	}

}

因为在求解过程中没有Timeslot实例改变，所以Timeslot被称为问题事实(problem fact)。这样的类不需要任何OptaPlanner特定的注解。 注意，toString()方法使输出保持简短，因此更容易读取OptaPlanner的DEBUG或TRACE日志，如下所示。

Room ​

Room类表示授课的位置，例如教室a或教室b。为了简单起见，所有的room都没有容量限制，可以容纳所有的课程。

  • Room.java
java
package study.helloworld.optaplanner.schooltimetabling.domain;

public class Room {

	private String name;

	public Room() {
	}

	public Room(String name) {
		this.name = name;
	}

	@Override
	public String toString() {
		return name;
	}

	public String getName() {
		return name;
	}

}

room实例在解决过程中不会改变，所以room也是一个问题事实。

规划实体 ​
Lesson ​

在一节课中，老师向一群学生教授一门学科，例如，九年级的图灵教授数学，十年级的居里教授化学。如果同一科目每周由同一老师向同一学生组教授多次，则存在多个只能通过id区分的Lesson实例。例如，九年级每周有六节数学课。

在求解过程中，OptaPlanner更改了Lesson类的timeslot和room字段，将每节课分配到一个timeslot和一个room。因为OptaPlanner更改了这些字段，所以Lesson是一个规划实体:

前面图表中的大多数字段都包含输入数据，除了橙色字段:课程的timeslot和room字段在输入数据中是未分配的(null)，而在输出数据中是分配的(非null)。OptaPlanner在求解过程中更改这些字段。这样的字段称为规划变量。为了让OptaPlanner识别它们，timeslot和room字段都需要一个@PlanningVariable注解。包含它们的类Lesson需要一个@PlanningEntity注解。

  • Lesson.java
java
package study.helloworld.optaplanner.schooltimetabling.domain;

import org.optaplanner.core.api.domain.entity.PlanningEntity;
import org.optaplanner.core.api.domain.lookup.PlanningId;
import org.optaplanner.core.api.domain.variable.PlanningVariable;

@PlanningEntity
public class Lesson {

	@PlanningId
	private Long id;

	private String subject;

	private String teacher;

	private String studentGroup;

	@PlanningVariable(valueRangeProviderRefs = "timeslotRange")
	private Timeslot timeslot;

	@PlanningVariable(valueRangeProviderRefs = "roomRange")
	private Room room;

	public Lesson() {
	}

	public Lesson(Long id, String subject, String teacher,
			String studentGroup) {
		this.id = id;
		this.subject = subject;
		this.teacher = teacher;
		this.studentGroup = studentGroup;
	}

	@Override
	public String toString() {
		return subject + "(" + id + ")";
	}

	public Long getId() {
		return id;
	}

	public String getSubject() {
		return subject;
	}

	public String getTeacher() {
		return teacher;
	}

	public String getStudentGroup() {
		return studentGroup;
	}

	public Timeslot getTimeslot() {
		return timeslot;
	}

	public void setTimeslot(Timeslot timeslot) {
		this.timeslot = timeslot;
	}

	public Room getRoom() {
		return room;
	}

	public void setRoom(Room room) {
		this.room = room;
	}

}

Lesson类有一个@PlanningEntity注解，所以OptaPlanner知道这个类在求解过程中发生了变化，因为它包含一个或多个规划变量。

timeslot字段有一个@PlanningVariable注解，所以OptaPlanner知道它可以改变它的值。为了找到潜在的timeslot实例来分配给这个字段，OptaPlanner使用变量类型连接到一个值范围提供程序，该提供程序提供了一个List<timeslot>供选择。

出于同样的原因，room字段也有一个@PlanningVariable注解。

定义约束并计算分数 ​

分数代表特定解决方案的质量。越高越好。OptaPlanner寻找最佳解决方案，即在可用时间内找到的得分最高的解决方案。这可能是最优的解决方案。

因为这个用例有硬约束和软约束，所以使用HardSoftScore类来表示分数:

  • 硬约束不能被打破。一个教室最多只能同时上一节课。
  • 不应打破软约束。老师喜欢在一个单独的room里教书。

硬约束对其他硬约束进行加权。相对于其他软约束，软约束也被加权。硬约束总是大于软约束，不管它们各自的权重如何。

创建一个ConstraintProvider实现类来执行增量分数计算。它使用OptaPlanner的ConstraintStream API，灵感来自Java Streams和SQL:

  • TimeTableConstraintProvider.java
java
package study.helloworld.optaplanner.schooltimetabling.solver;

import java.time.Duration;

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;

import study.helloworld.optaplanner.schooltimetabling.domain.Lesson;

public class TimeTableConstraintProvider implements ConstraintProvider {

	@Override
	public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
		return new Constraint[] {
				// 硬约束
				roomConflict(constraintFactory),
				teacherConflict(constraintFactory),
				studentGroupConflict(constraintFactory),
				// 软约束
				teacherRoomStability(constraintFactory),
				teacherTimeEfficiency(constraintFactory),
				studentGroupSubjectVariety(constraintFactory) };
	}

	/**
	 * 一个教室最多只能同时上一节课。
	 * 
	 * @param constraintFactory
	 * @return
	 */
	private Constraint roomConflict(ConstraintFactory constraintFactory) {
		// 选择一节课
		return constraintFactory.forEach(Lesson.class)
				// 并与另一节课配对
				.join(Lesson.class,
						// 在同一时间段
						Joiners.equal(Lesson::getTimeslot),
						// 在同一个教室
						Joiners.equal(Lesson::getRoom),
						// 并且对是唯一的(不同的id，没有反向对)
						Joiners.lessThan(Lesson::getId))
				// 然后用硬约束惩罚每一对。
				.penalize(HardSoftScore.ONE_HARD).asConstraint("Room conflict");
	}

	/**
	 * 一个老师一次最多只能教一节课。
	 * 
	 * @param constraintFactory
	 * @return
	 */
	private Constraint teacherConflict(ConstraintFactory constraintFactory) {
		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");
	}

	/**
	 * 一个学生一次最多只能上一节课。
	 * 
	 * @param constraintFactory
	 * @return
	 */
	private Constraint studentGroupConflict(
			ConstraintFactory constraintFactory) {
		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");
	}

	/**
	 * 老师喜欢在同一个教室里教所有的课。
	 * 
	 * @param constraintFactory
	 * @return
	 */
	Constraint teacherRoomStability(ConstraintFactory constraintFactory) {
		return constraintFactory
				.forEachUniquePair(Lesson.class,
						Joiners.equal(Lesson::getTeacher))
				.filter((lesson1,
						lesson2) -> lesson1.getRoom() != lesson2.getRoom())
				.penalize(HardSoftScore.ONE_SOFT)
				.asConstraint("Teacher room stability");
	}

	/**
	 * 老师喜欢连续上课，不喜欢课间的间隔。
	 * 
	 * @param constraintFactory
	 * @return
	 */
	Constraint teacherTimeEfficiency(ConstraintFactory constraintFactory) {
		return constraintFactory.forEach(Lesson.class)
				.join(Lesson.class, Joiners.equal(Lesson::getTeacher), Joiners
						.equal((lesson) -> lesson.getTimeslot().getDayOfWeek()))
				.filter((lesson1, lesson2) -> {
					Duration between = Duration.between(
							lesson1.getTimeslot().getEndTime(),
							lesson2.getTimeslot().getStartTime());
					return !between.isNegative()
							&& between.compareTo(Duration.ofMinutes(30)) <= 0;
				}).reward(HardSoftScore.ONE_SOFT)
				.asConstraint("Teacher time efficiency");
	}

	/**
	 * 学生不喜欢同一学科上连续的课。
	 * 
	 * @param constraintFactory
	 * @return
	 */
	Constraint studentGroupSubjectVariety(ConstraintFactory constraintFactory) {
		return constraintFactory
				.forEach(
						Lesson.class)
				.join(Lesson.class, Joiners.equal(Lesson::getSubject),
						Joiners.equal(Lesson::getStudentGroup),
						Joiners.equal((lesson) -> lesson.getTimeslot()
								.getDayOfWeek()))
				.filter((lesson1, lesson2) -> {
					Duration between = Duration.between(
							lesson1.getTimeslot().getEndTime(),
							lesson2.getTimeslot().getStartTime());
					return !between.isNegative()
							&& between.compareTo(Duration.ofMinutes(30)) <= 0;
				}).penalize(HardSoftScore.ONE_SOFT)
				.asConstraint("Student group subject variety");
	}

}

在规划解决方案中聚集域对象 ​

TimeTable包含单个数据集的所有Timeslot、Room和Lesson实例。此外，因为它包含了所有的课程，每个课程都有一个特定的规划变量状态，所以它是一个规划解决方案，它有一个分数:

  • 如果课程仍然未分配，那么它是一个未初始化的解决方案，例如，分数为-4init/0hard/0soft的解决方案。

  • 如果它打破了硬约束，那么它就是一个不可行的解决方案，例如，一个得分为-2hard/-3soft的解决方案。

  • 如果它遵循所有硬约束，那么它就是一个可行的解决方案，例如，得分为0hard/-7soft的解决方案。

  • TimeTable.java

java
package study.helloworld.optaplanner.schooltimetabling.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;

	public TimeTable() {
	}

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

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

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

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

	public HardSoftScore getScore() {
		return score;
	}

}

TimeTable类有一个@PlanningSolution注释，所以OptaPlanner知道这个类包含所有的输入和输出数据。

具体来说，这个类是问题的输入:

  • 包含所有timeslot的timeslotList字段

    • 这是一个问题事实列表，因为它们在解决过程中不会改变。

  • 包含所有room的roomList字段

    • 这是一个问题事实列表，因为它们在解决过程中不会改变。

  • 包含所有课程的lessonList字段

    • 这是一个规划实体列表，因为它们在求解过程中会发生变化。
    • 对于每一个Lesson：
      • timeslot和room字段的值通常仍然为空，因此未分配。它们是计划变量。
      • 填充其他字段，如subject、teacher和studentGroup。这些字段是问题属性。

然而，这个类也是解决方案的输出:

  • 一个lessonList字段，其中每个Lesson实例在求解后具有非空的timeslot和room字段

  • 表示输出解决方案质量的得分字段，例如，0hard/-5soft

值范围提供者 ​

timeslotList字段是一个值范围提供者。它保存着timeslot实例，OptaPlanner可以从中挑选并将其分配给Lesson实例的timeslot字段。timeslotList字段有一个@ValueRangeProvider注释，通过将规划变量的类型与值范围提供者返回的类型进行匹配，将@PlanningVariable与@ValueRangeProvider连接起来。

问题事实和规划实体属性 ​

此外，OptaPlanner需要知道它可以更改哪些课程实例，以及如何检索TimeTableConstraintProvider用于计算分数的Timeslot和Room实例。

timeslotList和roomList字段有一个@ProblemFactCollectionProperty注释，所以你的TimeTableConstraintProvider可以从这些实例中进行选择。

lessonList有一个@PlanningEntityCollectionProperty注释，所以OptaPlanner可以在求解过程中改变它们，你的TimeTableConstraintProvider也可以从中选择。

创建应用程序 ​

现在您已经准备好将所有内容放在一起并创建Java应用程序。main()方法执行以下任务:

  1. 创建SolverFactory来为每个数据集构建求解器。
  2. 加载数据集。
  3. 用solve.solve()求解。
  4. 可视化该数据集的解决方案。

通常，应用程序有一个SolverFactory来为每个要解决的问题数据集构建一个新的Solver实例。SolverFactory是线程安全的，但Solver不是。在这种情况下，只有一个数据集，所以只有一个Solver实例。

  • TimeTableApp.java
java
package study.helloworld.optaplanner.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.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;

import study.helloworld.optaplanner.schooltimetabling.domain.Lesson;
import study.helloworld.optaplanner.schooltimetabling.domain.Room;
import study.helloworld.optaplanner.schooltimetabling.domain.TimeTable;
import study.helloworld.optaplanner.schooltimetabling.domain.Timeslot;
import study.helloworld.optaplanner.schooltimetabling.solver.TimeTableConstraintProvider;

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
						// dataset.
						// 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++, "数学", "老师A", "八年级"));
		lessonList.add(new Lesson(id++, "数学", "老师A", "八年级"));
		lessonList.add(new Lesson(id++, "物理", "老师M", "八年级"));
		lessonList.add(new Lesson(id++, "化学", "老师M", "八年级"));
		lessonList.add(new Lesson(id++, "生物", "老师M", "八年级"));
		lessonList.add(new Lesson(id++, "历史", "老师C", "八年级"));
		lessonList.add(new Lesson(id++, "英语", "老师I", "八年级"));
		lessonList.add(new Lesson(id++, "英语", "老师I", "八年级"));
		lessonList.add(new Lesson(id++, "语文", "老师P", "八年级"));
		lessonList.add(new Lesson(id++, "语文", "老师P", "八年级"));

		lessonList.add(new Lesson(id++, "数学", "老师A", "九年级"));
		lessonList.add(new Lesson(id++, "数学", "老师A", "九年级"));
		lessonList.add(new Lesson(id++, "数学", "老师A", "九年级"));
		lessonList.add(new Lesson(id++, "物理", "老师M", "九年级"));
		lessonList.add(new Lesson(id++, "化学", "老师M", "九年级"));
		lessonList.add(new Lesson(id++, "政治", "老师C", "九年级"));
		lessonList.add(new Lesson(id++, "地理", "老师C", "九年级"));
		lessonList.add(new Lesson(id++, "历史", "老师C", "九年级"));
		lessonList.add(new Lesson(id++, "英语", "老师I", "九年级"));
		lessonList.add(new Lesson(id++, "语文", "老师P", "九年级"));

		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:

java
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
				// dataset.
				// It's recommended to run for at least 5 minutes ("5m")
				// otherwise.
				.withTerminationSpentLimit(Duration.ofSeconds(5)));

这将注册@PlanningSolution类、@PlanningEntity类和ConstraintProvider类，所有这些都是您在前面创建的。

如果没有终止设置或terminationEarly()事件，求解器将永远运行。为了避免这种情况，求解器将求解时间限制为5秒。

五秒钟后，main()方法加载问题，解决它，并打印解决方案:

java
// 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-hard问题的性质，最佳解决方案可能不是最优的，特别是对于较大的数据集。增加终止时间可能会找到更好的解决方案。

generateDemoData()方法生成要解决的学校时间表问题。

printTimetable()方法将时间表很好地打印到控制台，因此很容易从视觉上确定它是否是一个好的时间表。

构建和运行应用 ​

验证控制台输出。它是否符合所有硬约束?如果在TimeTableConstraintProvider中注释掉roomConflict约束会发生什么?

log
...
INFO  Solving ended: time spent (5000), best score (0hard/8soft), ...
INFO  
INFO  |            | Room A     | Room B     | Room C     |
INFO  |------------|------------|------------|------------|
INFO  | MON 08:30  | 物理         | 语文         |            |
INFO  |            | 老师M        | 老师P        |            |
INFO  |            | 九年级        | 八年级        |            |
INFO  |------------|------------|------------|------------|
INFO  | MON 09:30  | 物理         | 语文         |            |
INFO  |            | 老师M        | 老师P        |            |
INFO  |            | 八年级        | 九年级        |            |
INFO  |------------|------------|------------|------------|
INFO  | MON 10:30  | 化学         | 语文         |            |
INFO  |            | 老师M        | 老师P        |            |
INFO  |            | 九年级        | 八年级        |            |
INFO  |------------|------------|------------|------------|
INFO  | MON 13:30  | 政治         |            | 数学         |
INFO  |            | 老师C        |            | 老师A        |
INFO  |            | 九年级        |            | 八年级        |
INFO  |------------|------------|------------|------------|
INFO  | MON 14:30  | 生物         |            | 数学         |
INFO  |            | 老师M        |            | 老师A        |
INFO  |            | 八年级        |            | 九年级        |
INFO  |------------|------------|------------|------------|
INFO  | TUE 08:30  | 地理         |            | 数学         |
INFO  |            | 老师C        |            | 老师A        |
INFO  |            | 九年级        |            | 八年级        |
INFO  |------------|------------|------------|------------|
INFO  | TUE 09:30  |            | 英语         | 数学         |
INFO  |            |            | 老师I        | 老师A        |
INFO  |            |            | 八年级        | 九年级        |
INFO  |------------|------------|------------|------------|
INFO  | TUE 10:30  | 化学         | 英语         |            |
INFO  |            | 老师M        | 老师I        |            |
INFO  |            | 八年级        | 九年级        |            |
INFO  |------------|------------|------------|------------|
INFO  | TUE 13:30  | 历史         | 英语         |            |
INFO  |            | 老师C        | 老师I        |            |
INFO  |            | 九年级        | 八年级        |            |
INFO  |------------|------------|------------|------------|
INFO  | TUE 14:30  | 历史         |            | 数学         |
INFO  |            | 老师C        |            | 老师A        |
INFO  |            | 八年级        |            | 九年级        |
INFO  |------------|------------|------------|------------|

信息日志显示了OptaPlanner在这五秒钟内做了什么:

log
...
INFO  Solving started: time spent (206), best score (-40init/0hard/0soft), environment mode (REPRODUCIBLE), move thread count (NONE), random (JDK with seed 0).
INFO  Construction Heuristic phase (0) ended: time spent (730), best score (-1hard/-11soft), score calculation speed (1226/sec), step total (20).
INFO  Local Search phase (1) ended: time spent (5000), best score (0hard/8soft), score calculation speed (18505/sec), step total (10007).
INFO  Solving ended: time spent (5000), best score (0hard/8soft), score calculation speed (15871/sec), phase total (2), environment mode (REPRODUCIBLE), move thread count (NONE).
...

Released under the MIT License.

Copyright © 2020-2024 Panda