什么是过约束规划？
在资源受限的规划问题中，我们经常会遇到需求量超过可用资源量的情况，这被称为“过约束规划”。例如，医院只有9张病床，却有10名患者需要住院；或者一个任务需要一个时间段，但所有现有时间段都已被占用。OptaPlanner 提供了灵活的机制来处理这类问题，允许规划器在无法满足所有需求时，通过不同的策略来“失败”，但这种失败是可控且有代价的。
OptaPlanner 处理过约束的两种核心策略
OptaPlanner 提供了两种主要策略来应对过约束场景，它们在设计理念和适用场景上有所不同：
- 使用可空规划变量 (nullable=true)：当未分配的实体可以被视为“外部问题”或服务简单地被拒绝时。
- 引入虚拟值 (Virtual Values)：当未分配的实体仍然是需要解决的“内部问题”，并且需要量化和管理这些未满足的需求时。
这两种策略都通常会配合使用 HardMediumSoftScore 等分数类型，通过中等约束（Medium Constraint）来惩罚未分配或分配给虚拟值的实体。
策略一：使用可空规划变量 (nullable=true)
当您希望 OptaPlanner 尽可能地利用现有资源，并且对于那些无法分配的实体，您可以接受它们保持未分配状态（例如，它们将由其他系统处理，或者服务直接被拒绝）时，nullable=true 是一个理想的选择。
适用场景
- 最大化现有资源利用率：目标是让尽可能多的实体被分配到现有资源上。
- 未分配实体是“外部问题”：系统不关心未分配实体的后续处理，或者它们被视为无法服务。
- 示例：一家呼叫中心有固定数量的座席，超出座席能力的来电会被直接挂断或转入语音留言，系统只负责分配现有座席。
实现机制
-
设置规划变量为可空：在您的规划实体中，将相关的规划变量标记为 nullable = true。这意味着该变量可以被赋值为 null。
@PlanningVariable(valueRangeProviderRefs = {"timeslotRange"}, nullable = true) public Timeslot getTimeslot() { return timeslot; } -
添加中等约束惩罚 null 赋值：创建一个中等约束，对任何被分配到 null 的实体施加惩罚。规划器会尝试最小化这种惩罚，从而最大化分配数量。
// 伪代码示例：惩罚未分配的任务 rule "penalizeUnassignedTask" when Task(timeslot == null) then // 每有一个未分配任务，扣除1个中等分数 scoreHolder.addMediumConstraintMatch(kcontext, -1); end
关键特性
- 硬约束和软约束不适用于未分配实体：当一个实体被分配为 null 时，它通常不会触发针对特定资源或时间段的硬约束或软约束。因为 null 并不代表一个具体的资源。
- 专注于现有资源：这种方法促使求解器在不违反硬约束的前提下，尽可能多地将实体分配给实际存在的资源。
策略二：引入虚拟值 (Virtual Values)
当未分配的实体仍然是您需要明确识别、量化和解决的问题时，引入虚拟值是一种更强大的策略。它将“缺失的资源”具象化为虚拟值，从而让规划器能够像处理实际资源一样处理它们。这适用于需要对未满足的需求进行成本核算或后续处理的场景。
适用场景
- 未分配实体是“内部问题”：您需要知道有多少需求未被满足，并且可能需要为此付出代价（例如，雇佣临时工、租用外部设备）。
- 量化和管理未满足的需求：虚拟值允许您对这些未满足的需求施加约束和成本。
- 示例：医院病床不足时，可以将额外的患者分配到“虚拟病床”，这代表需要租用外部病房或转院，并为此付出额外的成本。
实现机制
-
定义虚拟资源：在您的领域模型中，除了实际存在的资源外，定义一些“虚拟”资源。这些虚拟资源应该与实际资源属于同一类型。
// 假设 Timeslot 是您的资源类型 public class Timeslot { private String id; private boolean isVirtual; // 标记是否为虚拟时间段 // ... 其他属性 } // 在 ValueRangeProvider 中包含虚拟时间段 @PlanningSolution public class MyPlanningSolution { @ValueRangeProvider(id = "timeslotRange") public ListgetTimeslotList() { // 包含实际时间段和预估的虚拟时间段 return Stream.concat( actualTimeslots.stream(), virtualTimeslots.stream() ).collect(Collectors.toList()); } // ... } 预估虚拟值的数量：您需要根据业务逻辑预估可能需要的虚拟值数量。通常会预估一个比最大可能需求量稍大的数字，以确保所有实体都有潜在的分配目标。
-
添加中等约束惩罚分配给虚拟值：创建一个中等约束，对任何被分配到虚拟值的实体施加惩罚。规划器会尝试最小化这种惩罚，但同时会考虑这些虚拟值上的其他硬约束。
// 伪代码示例：惩罚分配给虚拟时间段的任务 rule "penalizeTaskAssignedToVirtualTimeslot" when Task(timeslot != null, timeslot.isVirtual == true) then // 每有一个任务分配给虚拟时间段，扣除1个中等分数 scoreHolder.addMediumConstraintMatch(kcontext, -1); end 不要设置规划变量为 nullable=true：在使用虚拟值时，您的规划变量不应该再设置为 nullable=true。所有实体都应该被分配到一个具体的（实际或虚拟的）资源上。
关键特性
- 硬约束和软约束适用于分配给虚拟值的实体：这是与 nullable=true 最主要的区别。当一个实体被分配到虚拟值时，它仍然会触发针对该虚拟值的任何硬约束或软约束。例如，如果虚拟病床也有容量限制，或者虚拟时间段之间不能重叠，这些约束仍然有效。这使得虚拟值在规划中扮演了“真实”的角色。
- 明确量化未满足的需求：最终解决方案中，分配给虚拟值的实体数量直接反映了资源缺口。
选择哪种策略？
选择 nullable=true 还是虚拟值，取决于您的业务需求和对未分配实体的处理方式：
-
选择 nullable=true 当：
- 您只关心如何最好地利用现有资源。
- 未分配的实体可以被系统“忽略”或由其他流程处理，而无需在 OptaPlanner 内部进行管理或成本核算。
- 您不希望硬约束或软约束应用于这些未分配的实体。
-
选择虚拟值当：
- 未分配的实体仍然是您需要明确解决的问题，并且需要对其进行量化和管理。
- 您需要对未满足的需求施加额外的约束（例如，虚拟资源的容量限制）。
- 您希望在规划结果中清晰地看到有多少需求未被现有资源满足，并可能为其分配成本。
重要提示： 在同一个规划变量上，不要同时使用 nullable=true 和虚拟值。这两种方法是互斥的，选择其中一种即可。
总结
OptaPlanner 为过约束规划提供了两种强大且灵活的策略：nullable=true 和虚拟值。理解它们之间的差异，特别是在硬约束和软约束对未分配实体的影响方面，是做出正确选择的关键。通过合理地运用中等约束来惩罚未分配或分配给虚拟值的实体，您可以引导规划器生成最符合业务目标和成本效益的解决方案，即使在资源不足的情况下也能提供有意义的规划结果。
