OptaPlanner过约束规划概述
在资源有限的规划问题中，有时会出现需求量超过可用资源容量的情况，这被称为“过约束规划”（overconstrained planning）。例如，医院只有9张病床，却有10名患者需要住院。在这种情况下，我们不能简单地拒绝服务，而是需要一种机制来识别并管理这些超出容量的需求。optaplanner提供了两种主要策略来应对这类问题：将规划变量设为可空（nullable=true）或引入“虚拟值”（virtual values）。
策略一：使用可空（nullable=true）规划变量
当某些实体无法被分配到资源时，可以将其对应的规划变量设置为null。这种方法适用于以下场景：
业务目标：未分配的实体可以被视为“无法满足的需求”，其处理责任可能转移给其他系统或被直接拒绝。例如，如果一个任务无法被安排，它可能被推迟到下一个规划周期，或者被视为一个失败的请求。
-
工作原理：
- 将规划实体上的规划变量（例如，Task的timeslot）的nullable属性设置为true。
- 在分数计算中，对那些被分配到null值的实体施加一个中等（Medium）惩罚。这样，求解器会尝试最大化分配数量，同时满足所有硬约束。
-
约束处理：
- 当一个实体被分配到null时，与该实体相关的硬约束和软约束将不再对该实体生效。这意味着，如果一个任务没有被分配timeslot，那么关于该任务在timeslot上的任何时间冲突、资源限制等约束都将不被考虑。
- 求解器会优先满足所有硬约束，然后尽量减少分配到null的实体数量（通过减少中等惩罚）。
-
示例代码（概念性）：
// 规划实体类：Task @PlanningEntity public class Task { private String id; // timeslot是规划变量，可以为null @PlanningVariable(valueRangeProviderRefs = {"timeslotRange"}, nullable = true) private Timeslot timeslot; // ... 其他属性和方法 } // 分数计算器（Drools或ConstraintStreams） // 假设使用ConstraintStreams class MyConstraintProvider implements ConstraintProvider { @Override public Constraint[] defineConstraints(ConstraintFactory factory) { return new Constraint[] { // 硬约束：例如，一个timeslot不能同时处理两个任务 factory.forEachUniquePair(Task.class, // 两个任务不能在同一个timeslot且timeslot不为null Joiners.equal(Task::getTimeslot), Joiners.filtering((task1, task2) -> task1.getTimeslot() != null)) .penalize("Timeslot冲突", HardSoftScore.ONE_HARD), // 中等约束：惩罚未分配timeslot的任务 factory.forEach(Task.class) .filter(task -> task.getTimeslot() == null) .penalize("未分配任务", HardMediumSoftScore.ONE_MEDIUM) // 使用HardMediumSoftScore }; } }在这种模式下，求解器会尽量将任务分配给实际的timeslot，以避免MEDIUM惩罚，但如果无法满足所有硬约束，则允许部分任务被分配到null。
策略二：引入虚拟值（Virtual Values）
虚拟值是一种更高级的过约束处理机制，它模拟了“额外”或“外部”资源的存在，用于吸收超出实际容量的需求。这适用于以下场景：
业务目标：所有实体都必须得到处理，即使这意味着需要付出额外成本（例如，租用外部设施、雇佣临时工）。未分配的实体被视为“你的问题”，需要找到解决方案。
概念解释：虚拟值不是真正的资源，而是规划域中代表“应急”或“溢出”容量的抽象值。例如，如果医院有9张实际病床，但有10名患者，我们可以创建1个“虚拟病床”，表示第10名患者将被安排到外部合作医院的床位。
-
工作原理：
- 不将规划变量设为nullable=true。所有实体都必须被分配到一个值。
- 在规划变量的值域中，除了实际资源外，额外添加一些“虚拟值”。这些虚拟值需要有一个标识，表明它们是虚拟的。
- 在分数计算中，对那些被分配到虚拟值的实体施加一个中等（Medium）惩罚。
-
约束处理：
- 关键区别：即使实体被分配到虚拟值，所有硬约束和软约束仍然对其生效。这意味着，如果一个任务被分配到一个虚拟timeslot，它仍然必须遵守所有与timeslot相关的规则（例如，一个虚拟timeslot不能同时安排两个任务，或者虚拟timeslot也有其特定的容量限制）。
- 求解器会优先满足所有硬约束，然后尽量减少分配到虚拟值的实体数量（通过减少中等惩罚）。
-
如何估算虚拟值数量：
- 虚拟值的数量需要根据领域特定公式进行估算。通常建议多于理论最大溢出需求，例如，将需求量的两倍或更多作为虚拟值的数量，以确保求解器有足够的空间进行探索。
-
示例代码（概念性）：
// Timeslot类需要一个属性来标识是否是虚拟Timeslot public class Timeslot { private String id; private boolean isVirtual; // 标识是否为虚拟timeslot // ... 其他属性和方法 } // 规划实体类：Task @PlanningEntity public class Task { private String id; // timeslot是规划变量，不能为null，因为它必须被分配到真实或虚拟timeslot @PlanningVariable(valueRangeProviderRefs = {"timeslotRange"}, nullable = false) // 注意这里是false private Timeslot timeslot; // ... 其他属性和方法 } // 规划解决方案类：定义值域提供者 @PlanningSolution public class MyPlanningSolution { // ... 其他属性 private ListallTimeslots; // 包含真实和虚拟Timeslot @ValueRangeProvider(id = "timeslotRange") public List getTimeslotRange() { return allTimeslots; } // 假设在初始化时，allTimeslots会被填充 public void initializeTimeslots(List realTimeslots, int virtualTimeslotCount) { this.allTimeslots = new ArrayList<>(realTimeslots); for (int i = 0; i < virtualTimeslotCount; i++) { Timeslot virtual = new Timeslot("VIRTUAL_" + i, true); this.allTimeslots.add(virtual); } } // ... } // 分数计算器（Drools或ConstraintStreams） class MyConstraintProvider implements ConstraintProvider { @Override public Constraint[] defineConstraints(ConstraintFactory factory) { return new Constraint[] { // 硬约束：一个timeslot（无论是真实还是虚拟）不能同时处理两个任务 factory.forEachUniquePair(Task.class, Joiners.equal(Task::getTimeslot)) .penalize("Timeslot冲突", HardSoftScore.ONE_HARD), // 中等约束：惩罚分配到虚拟timeslot的任务 factory.forEach(Task.class) .filter(task -> task.getTimeslot().isVirtual()) .penalize("使用虚拟Timeslot", HardMediumSoftScore.ONE_MEDIUM) }; } } 在这种模式下，所有任务都会被分配到一个timeslot，但那些被分配到虚拟timeslot的任务会产生MEDIUM惩罚。由于硬约束仍然适用于虚拟timeslot，求解器必须确保即使使用虚拟资源，所有规则也得到遵守。
选择策略的考量
在决定使用nullable=true还是虚拟值时，应考虑以下几个关键因素：
-
业务目标与责任归属：
- 如果未分配的实体可以被“拒绝服务”或成为“别人的问题”（例如，客户的请求被拒绝），则nullable=true可能更合适。
- 如果所有实体都必须得到处理，即使这意味着额外的成本或资源（例如，所有患者都必须有床位，即使是外部租用的），则虚拟值是更好的选择。
-
约束的适用性：
- 核心差异：对于nullable=true，被分配到null的实体通常不参与硬约束和软约束的评估。
- 对于虚拟值，即使实体被分配到虚拟资源，所有硬约束和软约束仍然对其生效。这意味着虚拟资源本身也必须遵守规划规则（例如，一个虚拟床位不能同时给两个人）。
-
解决方案的解释性：
- 虚拟值提供了一个明确的“溢出”或“应急”资源视图，有助于理解哪些需求超出了常规容量，以及这些超出的需求将如何被满足（尽管是虚拟的）。
- nullable=true则简单地表示“未分配”，可能需要额外的逻辑来解释这些未分配的实体将如何被处理。
-
实现复杂性：
- nullable=true在实现上通常更简单，只需设置一个属性和添加一个惩罚约束。
- 虚拟值需要额外的数据模型设计（标识虚拟资源）、值域的构建（包含虚拟资源）以及相应的惩罚约束，相对复杂一些。
总结
OptaPlanner在处理过约束规划时，提供了nullable=true和虚拟值两种有效策略。nullable=true适用于那些可以被“拒绝服务”或转移责任的未分配实体，其核心特点是未分配实体不计入硬软约束。而虚拟值则适用于所有实体都必须得到处理的场景，即使这意味着引入“额外”成本，其关键优势在于即使是虚拟资源，也必须遵守所有规划规则。
在实际应用中，开发者应根据具体的业务需求、对未分配实体的处理方式以及对约束严格性的要求，审慎选择最合适的过约束规划策略。正确地应用这些策略，将有助于构建更健壮、更符合实际业务需求的OptaPlanner解决方案。
