本文深入探讨 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 中包含虚拟时间段@PlanningSolutionpublic class MyPlanningSolution { @ValueRangeProvider(id = "timeslotRange") public List 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 过约束规划：理解虚拟值与可空变量的策略选择的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/220881.html
微信扫一扫 
支付宝扫一扫 
