一、规划问题
1、什么是规划问题
规划问题基于有限资源和特定约束条件具有最佳目标。最佳目标可以是任何事情，例如：
-
最大化利润-最佳目标产生最高可能的利润。
-
最小化生态足迹-最佳目标对环境影响最小。
-
最大化员工或客户的满意度-最佳目标优先考虑员工或客户的需求。
实现这些目标取决于可用资源的数量，例如：
- 人数。
- 时间量。
- 预算。
- 具体资源（例如机械设备、车辆、计算机、建筑物等）。
还必须考虑与这些资源相关的特定约束条件，例如一个人工作的小时数、他们使用某些机器的能力，或者设备之间的兼容性。
2、硬约束和软约束
通常，规划问题至少具有两个级别的约束条件：
- 不能违反（负面）硬约束。例如：一个老师不能同时教授两个不同的课程。
- 如果可能的话，不应违反（负面）软约束。例如：A老师不喜欢在星期五下午上课。
有些问题也有正面约束，如果可能的话，应满足（积极的）软约束。例如：B老师喜欢在星期一早上上课；有些问题（如N皇后问题）只有硬约束；有些问题具有三个或更多级别的约束条件，例如硬约束、中等约束和软约束。这些约束条件定义了规划问题的评分计算（也称为适应度函数）。规划问题的每个解决方案都可以根据得分进行评估。
3、问题事实、规划实体和规划解决方案
在规划问题中，问题事实、规划实体和规划解决方案是三个核心概念，它们共同构成了解决规划问题的基础框架。
- 问题事实（Problem Fact）
-
定义
问题事实是由分数约束使用，但在计划期间不会改变的数据。这些数据是规划问题的基础，为规划过程提供了必要的背景信息。
-
特性
- 稳定性：在规划过程中，问题事实的属性值不会发生变化。
- 约束性：问题事实通常与约束条件相关联，用于定义规划实体之间的关系和限制。
- 引用性：问题事实可以引用其他问题事实，以构建更复杂的规划模型。
-
示例
在员工排班问题中，员工（Employee）、部门（Department）、时间段（Period）等可以视为问题事实。它们的属性值（如员工的技能、部门的业务需求、时间段的长度等）在规划过程中保持不变。
- 规划实体（Planning Entity）
-
定义
规划实体是在求解过程中发生变化的对象，它们代表规划问题中的实际对象，如任务、资源、时间窗口等。规划实体的变化是规划过程的核心。
-
特性
- 可变性：规划实体的属性值在规划过程中可以发生变化，以适应不同的解决方案。
- 规划变量：规划实体通常包含一个或多个规划变量（即问题事实），这些变量在规划过程中被优化算法调整，以找到最佳解决方案。
- 约束性：规划实体受到问题事实中定义的约束条件的限制，这些约束条件决定了规划实体在规划过程中的可行性和最优性。
-
示例
在员工排班问题中，排班表（ShiftAssignment）可以视为规划实体。它的属性值（如员工分配的班次、工作时间等）在规划过程中会发生变化，以适应部
门的业务需求和员工的可用性。同时，排班表受到员工技能、部门业务需求等问题事实的约束。
- 规划解决方案（Planning Solution）
-
定义
规划解决方案是规划过程的结果，它代表了一组满足所有约束条件并优化特定目标函数的规划实体的配置。规划解决方案是Optaplanner算法的输出，它提供了规划问题的最佳或接近最佳的解决方案。
-
特性
- 可行性：规划解决方案必须满足问题事实中定义的所有约束条件。
- 最优性：规划解决方案应优化特定的目标函数，以找到最佳或接近最佳的解决方案。
- 可表示性：规划解决方案通常以易于理解和表示的方式呈现给决策者或用户。
-
示例
在员工排班问题中，一个可行的排班表（即规划解决方案）应满足部门的需求和员工的可用性，并优化某些目标函数（如最小化员工的不满意度、最大化部门的运营效率等）。
二、Optaplanner常用的类和方法
1、注解
在Optaplanner中，问题事实、规划实体和规划解决方案都是普通的POJO类，这些类通过Optaplanner定义的注解来标记，从而实现既定目标。
| 注解 | 位置 | 作用 |
|---|---|---|
| @PlanningId | 字段上的注解 | 标记问题事实类和规划实体类中的唯一标识符字段 |
| @PlanningEntity | 类上的注解 | 标记规划实体类 |
| @PlanningVariable | 字段上的注解 | 标记规划实体类的一个或多个规划变量（即问题事实） |
| @PlanningSolution | 类上的注解 | 标记规划解决方案类 |
| @ProblemFactCollectionProperty | 字段上的注解 | 在规划解决方案类中，问题事实通常作为集合属性存在，并通过该注解来标识 |
| @ValueRangeProvider | 字段上的注解 | 和@ProblemFactCollectionProperty一起使用，用于定义规划变量（即问题事实）的可能值范围 |
| @PlanningEntityCollectionProperty | 字段上的注解 | 在规划解决方案类中，规划实体通常作为集合属性存在，并通过该注解来标识 |
| @PlanningScore | 字段上的注解 | 在规划解决方案类中，评分属性需要该注解来标识 |
-
两个问题事实类
@Data public class Room implements Serializable { private static final long serialVersionUID = 1L; @ApiModelProperty(value = "房间ID") @PlanningId private Long roomId; @ApiModelProperty(value = "名称") private String name; public Room() { } public Room(String name) { this.name = name; } public Room(Long roomId, String name) { this.roomId = roomId; this.name = name; } }@Data public class TimeSlot implements Serializable { private static final long serialVersionUID = 1L; @ApiModelProperty(value = "时间段ID") @PlanningId private Long slotId; @ApiModelProperty(value = "周几【1-周一 2-周二 3-周三 4-周四 5-周五 6-周六 7-周日】") private Integer dayOfWeek; @JsonFormat(pattern = "HH:mm") @ApiModelProperty(value = "开始时间") private LocalTime startTime; @JsonFormat(pattern = "HH:mm") @ApiModelProperty(value = "结束时间") private LocalTime endTime; public TimeSlot() { } public TimeSlot(Integer dayOfWeek, LocalTime startTime, LocalTime endTime) { this.dayOfWeek = dayOfWeek; this.startTime = startTime; this.endTime = endTime; } public TimeSlot(Long slotId, Integer dayOfWeek, LocalTime startTime, LocalTime endTime) { this.slotId = slotId; this.dayOfWeek = dayOfWeek; this.startTime = startTime; this.endTime = endTime; } } -
一个规划实体类
@Data @PlanningEntity public class Lesson implements Serializable { private static final long serialVersionUID = 1L; @ApiModelProperty(value = "课程ID") @PlanningId private Long lessonId; @ApiModelProperty(value = "科目") private String subject; @ApiModelProperty(value = "老师") private String teacher; @ApiModelProperty(value = "学生") private String studentGroup; @PlanningVariable private Room room; @PlanningVariable private TimeSlot timeSlot; public Lesson() { } public Lesson(String subject, String teacher, String studentGroup) { this.subject = subject; this.teacher = teacher; this.studentGroup = studentGroup; } public Lesson(Long lessonId, String subject, String teacher, String studentGroup, Room room, TimeSlot timeSlot) { this(subject, teacher, studentGroup); this.lessonId = lessonId; this.room = room; this.timeSlot = timeSlot; } public Lesson(String subject, String teacher, String studentGroup, Room room, TimeSlot timeSlot) { this.subject = subject; this.teacher = teacher; this.studentGroup = studentGroup; this.room = room; this.timeSlot = timeSlot; } } -
一个规划解决方案类
@PlanningSolution @Data public class TimeTable implements Serializable { @ProblemFactCollectionProperty @ValueRangeProvider private List<Room> roomList; @ProblemFactCollectionProperty @ValueRangeProvider private List<TimeSlot> timeSlotList; @PlanningEntityCollectionProperty private List<Lesson> lessonList; @PlanningScore private HardSoftScore score; @ApiModelProperty(value = "状态") private SolverStatus solverStatus; public TimeTable() { } public TimeTable(List<Room> roomList, List<TimeSlot> timeSlotList, List<Lesson> lessonList) { this.roomList = roomList; this.timeSlotList = timeSlotList; this.lessonList = lessonList; } }
如此，就建立了规划问题的数据模型。
2、常用的类
-
ConstraintProvider
该类定义了规划问题中的约束条件。ConstraintProvider是一个接口（或抽象类，具体取决于你使用的 Optaplanner 版本），用户需要实现这个接口来自定义规划问题的约束条件，同时返回 Constraint 对象的集合。
/** * 源码 */ public interface ConstraintProvider { Constraint[] defineConstraints(ConstraintFactory constraintFactory); }/** * 实现类 */ public class MyConstraintProvider implements ConstraintProvider { @Override public Constraint[] defineConstraints(ConstraintFactory constraintFactory) { return new Constraint[]{ // 这里就开始写约束规则,硬约束 firstConstraint(constraintFactory), secondConstraint(constraintFactory), thirdConstraint(constraintFactory), // 软约束 fourthConstraint(constraintFactory), fifthConstraint(constraintFactory), sixthConstraint(constraintFactory) }; } -
ConstraintFactory
该类的主要作用是允许用户通过声明式的方式定义约束条件。它的功能：
-
创建约束流
ConstraintFactory提供了多种方法来创建约束流（Constraint Streams），这些流定义了如何检查约束条件。
方法名 返回内容 forEach() UniConstraintStream forEachUniquePair() BiConstraintStream -
定义惩罚分数
在约束流中，当用户定义的约束条件不满足时，可以通过penalize或reward方法来定义惩罚分数或奖励分数。这些分数将用于评估解决方案的质量。
方法名 作用 示例 penalize() 扣分 stream.penalize(HardSoftScore.ONE_HARD).asConstraint("Room conflict") reward() 加分 stream.reward(HardSoftScore.ONE_SOFT).asConstraint("Teacher time efficiency")
- UniConstraintStream
该类是处理单个数据元素的约束流，它允许你为单个元素定义约束条件。当你需要为单个元素（如一个任务、一个员工、一个资源等）设置约束时，可以 使用它，例如：你可能希望确保任务只能由具有特定技能的员工执行。
Constraint requiredSkill(ConstraintFactory constraintFactory) {
UniConstraintStream<Shift> stream = constraintFactory.forEach(Shift.class); // 获取UniConstraintStream流
UniConstraintStream<Shift> filterStream = stream.filter(new Predicate<Shift>() {
@Override
public boolean test(Shift shift) {
return !shift.getEmployee().getSkillSet().contains(shift.getRequiredSkill());
}
}); // filter过滤得到技能不匹配的元素
return filterStream.penalize(HardSoftScore.ONE_HARD).asConstraint("Missing required skill"); // 技能不匹配的元素被扣分
}
| 操作 | 方法名 | 返回内容 |
|---|---|---|
| 过滤 | filter() | 满足条件的UniConstraintStream |
| 分组 | groupBy() | groupBy(一个参数)—BiConstraintStream；groupBy(二个参数)—TriConstraintStream ...... |
| 连接 | join() | BiConstraintStream |
-
BiConstraintStream
该类是处理两个数据元素之间关系的约束流。当你需要为两个元素之间的关系设置约束时，可以使用它。例如：你可能虚妄确保两个任务不能在同一时间段由一个员工执行。
Constraint teacherRoomStability(ConstraintFactory constraintFactory) { // 一个教师更喜欢在同一个房间上所有课程 return constraintFactory .forEachUniquePair(Lesson.class, Joiners.equal(lesson -> lesson.getTeacher())) // 获取到是同一个教师的约束流 .filter((lesson1, lesson2) -> lesson1.getRoom() != lesson2.getRoom()) // 过滤得到不是同一个教室的 .penalize(HardSoftScore.ONE_SOFT).asConstraint("Teacher room stability"); // 评分 } -
BiJoiner
该类主要用于在规划实体和规划变量（即问题事实）的关系定义，获取所有满足条件的 “规划实体- 规划变量” 组合。
default <A> BiConstraintStream<A, A> forEachUniquePair(Class<A> sourceClass, BiJoiner<A, A> joiner) { return forEachUniquePair(sourceClass, new BiJoiner[] { joiner }); } -
Joiners
Joiners 是一组用于在约束流（Constraint Stream）API 中连接不同事实（Facts）的工具，它总是返回一个BiJoiner。
| 方法名 | 作用 |
|---|---|
| equal() | 用于比较两个事实的特定属性是否相等，这依赖于hashCode() |
| greaterThan()...... | 用于比较两个事实的特定属性，判断一个事实的属性值是否大于另一个事实的属性值 |
| overlapping() | 用于判断两个事实的时间区间（或其他具有区间属性的情况）是否有重叠部分 |
public Constraint firstConstraint(ConstraintFactory constraintFactory) {
BiConstraintStream<Lesson, Lesson> stream = constraintFactory.forEachUniquePair(Lesson.class,
Joiners.equal(new Function<Lesson, TimeSlot>() {
@Override
public TimeSlot apply(Lesson lesson) {
return lesson.getTimeSlot();
}
}), // 得到在同一时间段内的课程对
Joiners.equal(new Function<Lesson, Room>() {
@Override
public Room apply(Lesson lesson) {
return lesson.getRoom();
}
}) // 得到选择在同一房间内的课程对
); // BiJoiner = 类似过滤
return stream.penalize(HardSoftScore.ONE_HARD).asConstraint("Room conflict"); // 评分
}
Constraint noOverlappingShifts(ConstraintFactory constraintFactory) {
return constraintFactory.forEachUniquePair(Shift.class,
Joiners.equal(Shift::getEmployee), // equal
Joiners.overlapping(new Function<Shift, ChronoLocalDateTime<?>>() { // overlapping
@Override
public ChronoLocalDateTime<?> apply(Shift shift) {
return shift.getStart();
}
}, new Function<Shift, ChronoLocalDateTime<?>>() {
@Override
public ChronoLocalDateTime<?> apply(Shift shift1) {
return shift1.getEnd();
}
}))
.penalize(HardSoftScore.ONE_HARD, new ToIntBiFunction<Shift, Shift>() {
@Override
public int applyAsInt(Shift shift1, Shift shift2) {
return getMinuteOverlap(shift1, shift2);
}
}).asConstraint("Overlapping shift"); // 评分
}