optaplanner - 防止在链式计划中触发不必要的影子变量更新

Question

我们将取货和交付的车辆路线问题建模为链式规划问题。最重要的是，我们有一个自定义的移动实现，它从车队中取消一个拾取-交付对并将其插入到其他地方。

我们的链以与 optaplanner 示例中的ArrivalTimeUpdatingVariableListener类似的方式更新，从更改的计划实体开始，然后逐步进行直到链的末尾。

我们面临的问题是链条经常不必要地更新。由于我们宣布每次移动对 scoreDirector 进行 4 次计划变量更改，因此变量侦听器会从这 4 个计划实体中的每一个开始执行完整的链更新。通常所有四个实体都位于同一个链中，从第一个更改的实体开始进行一次更新就足够了。

我们已经实现了提前退出：如果在链更新期间没有更新特定的影子变量，我们将跳过链的其余部分。但是，这仅在我们偶然首先处理来自第一个实体的链时才有效。

我们如何确保每次 Move 只更新链一次，从第一个更改的实体开始？

标签： optaplanner

Answer 1

通过调试和迭代更改我们向分数控制器宣布变量更改的顺序，我们设法摆脱了多余的链更新。

TL;DR: Optaplanner 似乎按照向评分主管宣布计划变量更新的顺序触发链更新。

考虑一个插入动作，它将取货-交付对插入到现有的访问链中（应用Optaplanner 示例中的术语）：

v1 <- v2 <- v3 <- v4
// insert p between v1&v2, d between v2&v3. Result:
v1 <- p <- v2 <- d <- v3 <- v4

此操作导致 4 个计划变量更改：

1. p.previousStandstill = v1
2. v2.previousStandstill = p
3. d.previousStandstill = v2
4. v3.previousStandstill = d

这些计划变量中的每一个更改都会向分数主管 ( scoreDirector.beforeVariableChanged(...), scoreDirector.afterVariableChanged(...)) 宣布，并且无需进一步调整，Optaplanner 将从每个更改的实体调用完整的链更新。这不是必需的，因为从 开始的单个链更新p足以更新所有相关的影子变量。

为了防止 Optaplanner 进行多余的链更新，我们需要确保：

1. （链中最早接触的实体）的计划变量更新p需要在所有其他计划变量更新之前通知 scoreDirector
2. 一旦影子变量在整个过程中保持不变，迭代链更新就会立即停止

在我们的案例中，正确实施这些步骤将我们花费在更新链上的 CPU 时间减少了 50% 以上。