OptaPlanner 过约束规划：理解虚拟值与可空变量的策略选择-java教程-PHP中文网

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

聖光之護

发布： 2025-08-23 14:52:01

原创

1013人浏览过

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

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

什么是过约束规划？

在资源受限的规划问题中，我们经常会遇到需求量超过可用资源量的情况，这被称为“过约束规划”。例如，医院只有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 List<Timeslot> getTimeslotList() {
        // 包含实际时间段和预估的虚拟时间段
        return Stream.concat(
            actualTimeslots.stream(),
            virtualTimeslots.stream()
        ).collect(Collectors.toList());
    }
    // ...
}

登录后复制

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

百度虚拟主播
百度智能云平台的一站式、灵活化的虚拟主播直播解决方案

36

查看详情

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

// 伪代码示例：惩罚分配给虚拟时间段的任务
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 和虚拟值。理解它们之间的差异，特别是在硬约束和软约束对未分配实体的影响方面，是做出正确选择的关键。通过合理地运用中等约束来惩罚未分配或分配给虚拟值的实体，您可以引导规划器生成最符合业务目标和成本效益的解决方案，即使在资源不足的情况下也能提供有意义的规划结果。

以上就是OptaPlanner 过约束规划：理解虚拟值与可空变量的策略选择的详细内容，更多请关注php中文网其它相关文章！