OptaPlanner 过约束规划：理解虚拟值与可空变量的策略选择

本文深入探讨 OptaPlanner 中处理过约束规划的两种核心策略：使用可空规划变量（NULLable=true）和引入虚拟值。我们将详细阐述这两种方法的适用场景、实现机制及其对解决方案的影响，并通过中等约束（Medium Constraint）的运用，帮助您根据实际业务需求选择最合适的规划策略，有效解决资源不足问题。

什么是过约束规划？

在资源受限的规划问题中，我们经常会遇到需求量超过可用资源量的情况，这被称为“过约束规划”。例如，医院只有9张病床，却有10名患者需要住院；或者一个任务需要一个时间段，但所有现有时间段都已被占用。OptaPlanner 提供了灵活的机制来处理这类问题，允许规划器在无法满足所有需求时，通过不同的策略来“失败”，但这种失败是可控且有代价的。

OptaPlanner 处理过约束的两种核心策略

OptaPlanner 提供了两种主要策略来应对过约束场景，它们在设计理念和适用场景上有所不同：

1. 使用可空规划变量 (Nullable=true)：当未分配的实体可以被视为“外部问题”或服务简单地被拒绝时。
2. 引入虚拟值 (Virtual Values)：当未分配的实体仍然是需要解决的“内部问题”，并且需要量化和管理这些未满足的需求时。

这两种策略都通常会配合使用 HardMediumSoftScore 等分数类型，通过中等约束（Medium Constraint）来惩罚未分配或分配给虚拟值的实体。

策略一：使用可空规划变量 (nullable=true)

当您希望 OptaPlanner 尽可能地利用现有资源，并且对于那些无法分配的实体，您可以接受它们保持未分配状态（例如，它们将由其他系统处理，或者服务直接被拒绝）时，nullable=true 是一个理想的选择。

适用场景

• 最大化现有资源利用率：目标是让尽可能多的实体被分配到现有资源上。
• 未分配实体是“外部问题”：系统不关心未分配实体的后续处理，或者它们被视为无法服务。
• 示例：一家呼叫中心有固定数量的座席，超出座席能力的来电会被直接挂断或转入语音留言，系统只负责分配现有座席。

实现机制

1. 设置规划变量为可空：在您的规划实体中，将相关的规划变量标记为 nullable = true。这意味着该变量可以被赋值为 null。

   @PlanningVariable(valueRangeProviderRefs = {"timeslotRange"}, nullable = true) public Timeslot getTimeslot() {     return timeslot; }

2. 添加中等约束惩罚 null 赋值：创建一个中等约束，对任何被分配到 null 的实体施加惩罚。规划器会尝试最小化这种惩罚，从而最大化分配数量。

   // 伪代码示例：惩罚未分配的任务 rule "penalizeUnassignedTask"     when         Task(timeslot == null)     then         // 每有一个未分配任务，扣除1个中等分数         scoreHolder.addMediumConstraintMatch(kcontext, -1); end

关键特性

• 硬约束和软约束不适用于未分配实体：当一个实体被分配为 null 时，它通常不会触发针对特定资源或时间段的硬约束或软约束。因为 null 并不代表一个具体的资源。
• 专注于现有资源：这种方法促使求解器在不违反硬约束的前提下，尽可能多地将实体分配给实际存在的资源。

策略二：引入虚拟值 (Virtual Values)

当未分配的实体仍然是您需要明确识别、量化和解决的问题时，引入虚拟值是一种更强大的策略。它将“缺失的资源”具象化为虚拟值，从而让规划器能够像处理实际资源一样处理它们。这适用于需要对未满足的需求进行成本核算或后续处理的场景。

适用场景

• 未分配实体是“内部问题”：您需要知道有多少需求未被满足，并且可能需要为此付出代价（例如，雇佣临时工、租用外部设备）。
• 量化和管理未满足的需求：虚拟值允许您对这些未满足的需求施加约束和成本。
• 示例：医院病床不足时，可以将额外的患者分配到“虚拟病床”，这代表需要租用外部病房或转院，并为此付出额外的成本。

实现机制

1. 定义虚拟资源：在您的领域模型中，除了实际存在的资源外，定义一些“虚拟”资源。这些虚拟资源应该与实际资源属于同一类型。

   // 假设 Timeslot 是您的资源类型 public class Timeslot {     private String id;     private boolean isVirtual; // 标记是否为虚拟时间段     // ... 其他属性 }  // 在 ValueRangeProvider 中包含虚拟时间段 @PlanningSolution public class MyPlanningSolution {     @ValueRangeProvider(id = "timeslotRange")     public List<Timeslot> getTimeslotList() {         // 包含实际时间段和预估的虚拟时间段         return Stream.concat(             actualTimeslots.stream(),             virtualTimeslots.stream()         ).collect(Collectors.toList());     }     // ... }

2. 预估虚拟值的数量：您需要根据业务逻辑预估可能需要的虚拟值数量。通常会预估一个比最大可能需求量稍大的数字，以确保所有实体都有潜在的分配目标。

3. 添加中等约束惩罚分配给虚拟值：创建一个中等约束，对任何被分配到虚拟值的实体施加惩罚。规划器会尝试最小化这种惩罚，但同时会考虑这些虚拟值上的其他硬约束。

   // 伪代码示例：惩罚分配给虚拟时间段的任务 rule "penalizeTaskAssignedToVirtualTimeslot"     when         Task(timeslot != null, timeslot.isVirtual == true)     then         // 每有一个任务分配给虚拟时间段，扣除1个中等分数         scoreHolder.addMediumConstraintMatch(kcontext, -1); end

4. 不要设置规划变量为 nullable=true：在使用虚拟值时，您的规划变量不应该再设置为 nullable=true。所有实体都应该被分配到一个具体的（实际或虚拟的）资源上。

关键特性

• 硬约束和软约束适用于分配给虚拟值的实体：这是与 nullable=true 最主要的区别。当一个实体被分配到虚拟值时，它仍然会触发针对该虚拟值的任何硬约束或软约束。例如，如果虚拟病床也有容量限制，或者虚拟时间段之间不能重叠，这些约束仍然有效。这使得虚拟值在规划中扮演了“真实”的角色。
• 明确量化未满足的需求：最终解决方案中，分配给虚拟值的实体数量直接反映了资源缺口。

选择哪种策略？

选择 nullable=true 还是虚拟值，取决于您的业务需求和对未分配实体的处理方式：

• 选择 nullable=true 当：

  • 您只关心如何最好地利用现有资源。
  • 未分配的实体可以被系统“忽略”或由其他流程处理，而无需在 OptaPlanner 内部进行管理或成本核算。
  • 您不希望硬约束或软约束应用于这些未分配的实体。

• 选择虚拟值当：

  • 未分配的实体仍然是您需要明确解决的问题，并且需要对其进行量化和管理。
  • 您需要对未满足的需求施加额外的约束（例如，虚拟资源的容量限制）。
  • 您希望在规划结果中清晰地看到有多少需求未被现有资源满足，并可能为其分配成本。

重要提示： 在同一个规划变量上，不要同时使用 nullable=true 和虚拟值。这两种方法是互斥的，选择其中一种即可。

总结

OptaPlanner 为过约束规划提供了两种强大且灵活的策略：nullable=true 和虚拟值。理解它们之间的差异，特别是在硬约束和软约束对未分配实体的影响方面，是做出正确选择的关键。通过合理地运用中等约束来惩罚未分配或分配给虚拟值的实体，您可以引导规划器生成最符合业务目标和成本效益的解决方案，即使在资源不足的情况下也能提供有意义的规划结果。