理解过约束规划
在资源规划问题中，过约束（overconstrained planning）指的是当可用资源无法满足所有需求时的情况。例如，医院只有9张床位，却有10位或更多患者需要住院。在这种情况下，optaplanner不能简单地拒绝分配，而是需要一种机制来识别和量化“未满足”的需求，并将其纳入评分体系，从而找到一个最优的“次优”解决方案。处理过约束问题，通常有两种主要策略：使用可空规划变量（nullable=true）和引入虚拟值（virtual values）。
策略一：使用可空规划变量 (nullable=true)
当规划实体无法被分配到任何合适的资源时，nullable=true 允许其规划变量保持为空（null）。这种方法的核心思想是，未分配的实体被视为“外部问题”或其服务被简单地拒绝。
适用场景：
AI 舌诊面诊问诊医疗系统 + 诊疗商城系统源码是一套结合 AI 辅助诊断与商品转化的健康类程序，基于浩创云、ThinkPHP（PHP）开发，支持微信服务号与 H5 端，适合做中医舌诊面诊问答、健康建议推送以及配套诊疗商品的运营。
- 服务拒绝： 当资源不足时，未被分配的实体直接被拒绝服务，且这不直接导致额外的成本或需要你解决的后续问题。例如，有限的停车位，未分配到车位的车辆就无法停车，这不是规划系统需要进一步解决的问题。
- 责任转移： 未分配的实体被认为是其他系统或部门的问题。
实现方式：
-
规划变量设置： 在你的规划实体中，将规划变量标记为可空。
// 示例：一个任务（Task）需要分配一个时间段（Timeslot） @PlanningEntity public class Task { // ... 其他属性 @PlanningVariable(valueRangeProviderRefs = {"timeslotRange"}, nullable = true) private Timeslot timeslot; // ... getter/setter } -
约束设置： 添加一个中等（Medium）约束来惩罚那些未被分配到任何时间段的实体。
// 伪代码：使用ConstraintFactory创建约束 public Constraint unassignedTaskPenalty(ConstraintFactory factory) { return factory.forEach(Task.class) .filter(task -> task.getTimeslot() == null) .penalize(HardMediumSoftScore.ONE_MEDIUM, "每个未分配任务的惩罚") .asConstraint("Unassigned Task Penalty"); }
特点：
- 最大化利用率： OptaPlanner会尽力在现有资源下最大化分配数量，同时满足硬约束。
- 约束作用范围： 硬约束和软约束通常不适用于未分配（null）的实体。这意味着，如果一个任务未被分配时间段，它就不会因为违反了与时间段相关的硬约束而受到惩罚。
策略二：引入虚拟值 (Virtual Values)
虚拟值是一种更复杂的过约束处理方式，它模拟了“额外”的、通常带有成本的资源。当实际资源不足时，实体可以被分配给这些虚拟值，表示其需求得到了满足，但需要付出额外的代价。
适用场景：
- 问题仍需解决： 未分配的实体仍然是你的问题，需要通过额外成本（如加班、外包、租赁额外资源）来解决。例如，医院床位不足，患者可以被安排到合作医院的床位（虚拟床位），但这会产生额外的租赁费用。
- 成本量化： 你需要量化因资源不足而产生的额外成本或不便。
实现方式：
-
领域模型扩展： 在你的领域模型中定义虚拟资源。这些虚拟资源与实际资源属于同一类型，或者实现相同的接口。
// 示例：Timeslot接口和其实现类 public interface Timeslot {} public class RealTimeslot implements Timeslot { // ... 实际时间段属性 } public class VirtualTimeslot implements Timeslot { // ... 虚拟时间段属性，例如成本因子 private int costFactor; // 表示使用该虚拟时间段的额外成本 // ... } // 在规划实体中，规划变量现在可以分配给RealTimeslot或VirtualTimeslot @PlanningEntity public class Task { // ... 其他属性 @PlanningVariable(valueRangeProviderRefs = {"timeslotRange"}) // 注意：这里nullable=false或不设置 private Timeslot timeslot; // ... getter/setter } -
规划问题定义： 在你的问题域中，预先创建并包含一定数量的虚拟值。这些虚拟值的数量需要根据业务逻辑进行估计，通常是最大可能需求的两倍或更多，以确保有足够的“备用”资源。
// 示例：在问题初始化时创建时间段列表 List<Timeslot> allTimeslots = new ArrayList<>(); // 添加实际时间段 allTimeslots.addAll(realTimeslots); // 添加虚拟时间段，例如，假设我们最多需要额外50个时间段 for (int i = 0; i < 50; i++) { allTimeslots.add(new VirtualTimeslot(i + 1)); // 虚拟时间段可以有自己的标识或成本 } // 将allTimeslots作为timeslotRange提供给规划变量 -
约束设置： 添加一个中等约束来惩罚那些被分配给虚拟值的实体。这个惩罚可以根据虚拟值的类型或数量进行调整。
// 伪代码：使用ConstraintFactory创建约束 public Constraint virtualTimeslotAssignmentPenalty(ConstraintFactory factory) { return factory.forEach(Task.class) .filter(task -> task.getTimeslot() instanceof VirtualTimeslot) // 惩罚可以根据VirtualTimeslot的costFactor或其他属性来计算 .penalize(HardMediumSoftScore.ONE_MEDIUM, task -> ((VirtualTimeslot) task.getTimeslot()).getCostFactor(), "分配给虚拟时间段的惩罚") .asConstraint("Virtual Timeslot Assignment Penalty"); }
特点：
- 问题内部解决： 未分配的实体通过分配给虚拟值，将问题“内部化”，并量化其成本。
- 约束作用范围： 硬约束和软约束仍然作用于分配给虚拟值的实体。这意味着，即使任务被分配给了虚拟时间段，它仍然需要遵守与时间段相关的其他硬约束（例如，虚拟时间段不能同时处理两个冲突任务），否则将产生硬惩罚。
两种策略的对比与选择
| 特性 | nullable=true 策略 | 虚拟值 (Virtual Values) 策略 |
|---|---|---|
| 问题归属 | 未分配实体被视为外部问题，不直接由规划系统解决。 | 未分配实体仍是规划系统的问题，通过额外资源解决，并量化成本。 |
| 资源建模 | 仅使用实际资源，null 代表无资源分配。 | 实际资源 + 模拟的额外（有成本的）虚拟资源。 |
| 约束作用 | 硬约束和软约束通常不作用于未分配（null）的实体。 | 硬约束和软约束作用于分配给虚拟值的实体。 |
| 成本量化 | 只能通过惩罚 null 来间接表示未分配的成本。 | 可以精确量化使用额外资源的成本。 |
| 复杂性 | 相对简单，只需设置 nullable=true 和 null 惩罚。 | 需要扩展领域模型，预估并生成虚拟值，约束逻辑稍复杂。 |
| 搜索空间 | 搜索空间较小，因为 null 是一个固定状态。 | 搜索空间可能增大，因为虚拟值增加了可选的资源数量。 |
何时选择：
- 选择 nullable=true： 当你的业务场景中，资源不足导致的需求未被满足时，这被认为是可接受的，或者后续处理不由当前规划系统负责。你主要关注在现有资源下最大化分配，且未分配实体不应触发与资源相关的其他硬约束。
- 选择虚拟值： 当你的业务场景中，资源不足导致的需求仍需被满足，但需要付出额外成本。你需要量化这些额外成本，并且这些“额外满足”的需求仍需遵守某些规划约束（例如，即使是虚拟床位，也可能需要考虑患者类型或护理人员可用性）。
注意事项
- 分数类型： 在两种策略中，惩罚未分配或分配给虚拟值的实体通常使用 HardMediumSoftScore 的中等（Medium）分数。这确保了在满足所有硬约束的前提下，尽可能减少未分配或使用虚拟值的数量。
- 虚拟值的数量： 预估和创建足够多的虚拟值至关重要。如果虚拟值数量不足，系统仍可能面临无法分配所有实体的局面；如果过多，则可能不必要地增加搜索空间。
- 约束设计： 仔细设计约束，确保硬约束和软约束在两种策略下都能正确反映业务逻辑。特别是对于虚拟值，要明确哪些硬约束仍适用于分配给虚拟值的实体。
- 性能考量： 引入大量虚拟值可能会增加OptaPlanner的搜索空间，从而影响求解性能。在实际应用中，需要权衡虚拟值的数量与求解效率。
总结
OptaPlanner提供了灵活的机制来处理过约束规划。nullable=true 策略简洁明了，适用于未分配实体被视为外部问题或直接拒绝的场景；而虚拟值策略则更为强大，能够将资源不足的成本内部化并量化，适用于未分配实体仍需解决且需遵守特定约束的复杂场景。理解这两种策略的优缺点及适用场景，是构建高效且符合业务逻辑的OptaPlanner解决方案的关键。开发者应根据具体业务需求，权衡问题归属、成本量化和约束作用范围，选择最合适的策略。
