OptaPlanner 过约束规划：理解与应用虚拟值策略

OptaPlanner 过约束规划概述

在资源规划问题中，我们经常会遇到需求超过可用资源的情况，这便是所谓的“过约束规划”（overconstrained planning）。例如，医院床位有限但患者数量更多，或可用时段不足以安排所有任务。optaplanner 提供了灵活的机制来应对此类挑战，其中最常见的两种策略是利用规划变量的 nullable=true 属性和引入“虚拟值”（virtual values）。选择哪种策略取决于业务对未分配实体的处理方式。

策略一：利用 nullable=true 处理未分配实体

当业务场景允许部分实体不被分配（即“拒绝服务”或由其他系统处理）时，nullable=true 是一种简单有效的策略。这种方法的核心思想是让OptaPlanner在现有资源范围内，最大化地进行有效分配，而未被分配的实体则不会触发硬性约束。

工作原理与适用场景

• 最大化现有资源利用率： OptaPlanner 会尽力将实体分配给可用的实际资源，以满足硬约束并优化软约束。
• 未分配实体被视为“拒绝服务”： 对于那些无法找到合适资源（或找到会违反硬约束）的实体，它们将被分配到 null。
• 适用场景： 当未分配的实体不是当前规划问题的直接责任，或者其处理成本可以通过中等约束（Medium Constraint）来衡量时，此策略非常适用。例如，医院在床位已满时，无法接收的患者由其他医院处理。

配置与约束设计

1. 规划变量配置： 将规划实体中表示资源分配的变量设置为 nullable = true。

   @PlanningEntity
   public class Task {
       // ... 其他属性
   
       @PlanningVariable(valueRangeProviderRefs = {"timeslotRange"}, nullable = true)
       private Timeslot timeslot; // 任务被分配到的时段，可能为null
   
       // ... Getter/Setter
   }

2. 约束设计： 需要添加一个中等（Medium）约束来惩罚那些未被分配（即 timeslot == null）的实体。OptaPlanner 通常使用 HardMediumSoftScore 或类似的复合分数类型来处理此类场景，其中中等分数用于衡量未分配实体的“成本”。

   // 示例：使用ConstraintFactory定义一个惩罚未分配任务的约束
   public Constraint unassignedTaskPenalty(ConstraintFactory constraintFactory) {
       return constraintFactory.forEach(Task.class)
               .filter(task -> task.getTimeslot() == null)
               .penalize(MediumConstraintStreamImpl.of(1), // 惩罚值为1，表示一个中等分数
                         "Unassigned task penalty",
                         task -> 1); // 每个未分配任务扣1个Medium分
   }

   特点：

   • 硬约束（Hard Constraint）和软约束（Soft Constraint）通常不作用于分配给 null 的实体。这意味着如果一个任务未被分配，它不会因为违反了某个硬约束而导致规划失败。

策略二：引入“虚拟值”应对资源不足

当未分配的实体仍然是当前规划问题的一部分，并且需要通过某种“外部”或“补充”资源来解决时，引入“虚拟值”策略更为合适。虚拟值代表了那些非实际存在的、但可以被“创造”出来以满足需求的资源（例如，租用外部床位、雇佣临时工等）。

工作原理与适用场景

• 未分配实体仍需解决： 即使实际资源不足，规划器仍需为所有实体找到一个“归宿”，即使这个归宿是虚拟的。
• 模拟外部资源成本： 分配给虚拟值的实体会产生一定的“成本”（通常是中等约束），这模拟了获取这些外部资源的开销。
• 适用场景： 当业务要求所有实体都必须被处理，且可以通过支付额外成本来获取补充资源时。例如，医院在床位不足时，可以选择租赁临时床位或将患者转至合作医院。

配置与约束设计

1. 定义虚拟值： 虚拟值是规划变量可能取值集合的一部分。你需要创建这些虚拟资源实例，并将它们添加到变量的值域中。

   // 假设Timeslot是规划变量的类型
   public class Timeslot {
       private String id;
       private boolean isVirtual; // 标记是否为虚拟时段
   
       // ... 构造函数，Getter/Setter
   }
   
   // 在规划解决方案中，创建并提供Timeslot实例，包括虚拟的
   @PlanningSolution
   public class TaskPlanningSolution {
       @ProblemFactCollectionProperty
       @ValueRangeProvider(id = "timeslotRange")
       private List timeslotList; // 包含实际时段和虚拟时段
   
       // ... 其他属性和方法
   }

   关键点： 如果使用虚拟值，规划变量不应设置为 nullable = true。所有实体都必须被分配到一个具体的 Timeslot，无论是实际的还是虚拟的。

   

   PNG Maker

   利用 PNG Maker AI 将文本转换为 PNG 图像。

   下载

2. 预估虚拟值数量： 虚拟值的数量需要根据领域特定逻辑进行预估，并通常会额外添加一些作为缓冲，以确保所有实体都有机会被分配。

   // 示例：在问题初始化时创建虚拟时段
   public List createTimeslots(int actualCount, int estimatedNeededVirtual) {
       List timeslots = new ArrayList<>();
       // 添加实际时段
       for (int i = 0; i < actualCount; i++) {
           timeslots.add(new Timeslot("Actual_" + i, false));
       }
       // 添加虚拟时段 (例如，预估需求的两倍)
       for (int i = 0; i < estimatedNeededVirtual * 2; i++) {
           timeslots.add(new Timeslot("Virtual_" + i, true));
       }
       return timeslots;
   }

3. 约束设计： 添加一个中等（Medium）约束来惩罚那些被分配给虚拟值的实体。

   // 示例：惩罚分配给虚拟时段的任务
   public Constraint virtualTimeslotPenalty(ConstraintFactory constraintFactory) {
       return constraintFactory.forEach(Task.class)
               .filter(task -> task.getTimeslot() != null && task.getTimeslot().isVirtual())
               .penalize(MediumConstraintStreamImpl.of(1), // 每个分配给虚拟时段的任务扣1个Medium分
                         "Virtual timeslot assignment penalty",
                         task -> 1);
   }

   特点：

   • 硬约束（Hard Constraint）和软约束（Soft Constraint）会作用于分配给虚拟值的实体。这意味着即使一个任务被分配给虚拟时段，它仍然必须遵守所有相关的硬约束（例如，容量限制、技能要求等）。这使得虚拟值能更好地融入现有约束体系。

两种策略的对比与选择

如何选择：

• 如果未分配的实体可以被完全忽略，或者由另一个独立的流程处理，并且你只想在现有资源内做到最好，请选择 nullable=true。 这种方法简单直接，适用于“服务拒绝”场景。
• 如果未分配的实体仍然是你的责任，需要通过支付额外成本来解决，并且希望这些实体在被“虚拟”分配后仍能遵守现有业务规则（硬约束），那么虚拟值策略是更好的选择。 这种方法更全面，能更好地模拟真实世界的资源补充机制。

注意事项

• 分数类型： 在过约束规划中，通常推荐使用 HardMediumSoftScore 或自定义的复合分数类型，以便清晰地区分硬性违规、中等成本和软性偏好。
• 虚拟值数量： 预估虚拟值的数量时，务必留有足够的余量，确保OptaPlanner有足够的回旋空间来找到解决方案。数量过少可能导致无法找到所有实体的分配方案，数量过多则可能增加搜索空间。
• 约束精确性： 无论是惩罚 null 还是虚拟值，中等约束的惩罚值应根据业务场景仔细权衡，以准确反映未分配或使用虚拟资源的真实成本。
• 与现有约束的集成： 虚拟值策略的一个优势是，分配给虚拟值的实体仍然受到硬约束的制约。这意味着即使你“租用”了一个虚拟时段，该时段也必须满足容量、技能等基本要求，这有助于保持规划结果的合理性。

总结

OptaPlanner 为过约束规划提供了 nullable=true 和虚拟值两种强大的策略。nullable=true 适用于处理可被“拒绝服务”的实体，旨在最大化现有资源利用率；而虚拟值策略则适用于所有实体都必须被处理，且可通过引入“补充资源”来解决的场景。理解这两种策略的差异和适用范围，并结合业务需求进行恰当的配置和约束设计，是构建高效、鲁棒的OptaPlanner解决方案的关键。