本文深入探讨了OptaPlanner中处理过约束规划的两种核心策略：使用虚拟值和将规划变量设为可空（NULLable）。文章详细阐释了虚拟值的概念及其在资源不足但需求必须满足场景下的应用，并对比了两种方法在业务目标、约束处理逻辑及适用场景上的差异，旨在指导开发者根据实际业务需求选择最合适的过约束解决方案。
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 List<Timeslot> allTimeslots; // 包含真实和虚拟Timeslot @ValueRangeProvider(id = "timeslotRange") public List<Timeslot> getTimeslotRange() { return allTimeslots; } // 假设在初始化时，allTimeslots会被填充 public void initializeTimeslots(List<Timeslot> 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解决方案。
