OptaPlanner链式变量自定义阴影变量计算引发分数损坏问题

问题场景 #

基于带时间窗的车辆路径规划（VRPTW）场景，将地铁站调度任务分配给检查员，目标是完成所有任务并最小化任务间换乘次数。已配置链式规划变量previousSlot，并通过自定义阴影变量shadowStartTime基于前序分配计算任务开始时间，但当任务数>2时，构造启发式阶段触发阴影变量损坏异常。

核心代码 #

规划实体类 #

@PlanningEntity
public class Allocation implements ScheduleSlot {
    @AnchorShadowVariable(sourceVariableName = "previousSlot")
    private Inspector inspector;

    @PlanningVariable(
        graphType=PlanningVariableGraphType.CHAINED, 
        valueRangeProviderRefs={"inspector_range", "task_range"} )
    private ScheduleSlot previousSlot;

    @CustomShadowVariable(variableListenerClass = SlotUpdateVariableListerer.class,
        sources = { 
            @PlanningVariableReference(variableName = "inspector"),
            @PlanningVariableReference(variableName = "previousSlot") })
    private Long shadowStartTime;

    // 其他属性和方法
}

注：Inspector为规划事实兼锚点，ScheduleSlot是检查员与任务的公共接口

变量监听器类 #

public class SlotUpdateVariableListerer implements VariableListener<ScheduleProblemSolution, ScheduleSlot> {
    // 其他方法

    @Override
    public void afterEntityAdded(ScoreDirector<ScheduleProblemSolution> scoreDirector, ScheduleSlot slot) {
        updateTask(scoreDirector, slot);
    }

    @Override
    public void afterVariableChanged(ScoreDirector<ScheduleProblemSolution> scoreDirector, ScheduleSlot slot) {
        updateTask(scoreDirector, slot);
    }

    private void updateTask(ScoreDirector<ScheduleProblemSolution> scoreDirector, ScheduleSlot slot) {
        ScheduleSlot prevSlot = slot.getPreviousSlot();
        final Long startTime = prevSlot != null ? prevSlot.getFinishTime() + prevSlot.timeToNext(slot) : null;

        scoreDirector.beforeVariableChanged(slot, "shadowStartTime");
        ((Allocation)slot).setShadowStartTime(startTime);
        scoreDirector.afterVariableChanged(slot, "shadowStartTime");
    }
}

错误现象 #

异常信息 #

Exception in thread "main" java.lang.IllegalStateException:
VariableListener corruption after completedAction ([09:00:00,
09:31:44] Task 321652 ...):
The entity ([10:37:16, 11:14:24] Task 320522...)'s shadow variable (Allocation.shadowStartTime)'s corrupted value (1659940628000) changed
to uncorrupted value (1659944236000) after all VariableListeners were
triggered without changes to the genuine variables.

堆栈跟踪 #

Exception in thread "main" java.lang.IllegalStateException: 
VariableListener corruption after completedAction (...):
The entity (...)'s shadow variable (Allocation.shadowStartTime)'s corrupted value (...) changed to uncorrupted value (...) after all VariableListeners were triggered without changes to the genuine variables.
  Maybe the VariableListener class (SlotUpdateVariableListerer) for that shadow variable (Allocation.shadowStartTime) forgot to update it when one of its sources changed.

    at org.optaplanner.core.impl.score.director.AbstractScoreDirector.assertShadowVariablesAreNotStale(AbstractScoreDirector.java:520)
    at org.optaplanner.core.impl.phase.scope.AbstractPhaseScope.assertShadowVariablesAreNotStale(AbstractPhaseScope.java:160)
    at org.optaplanner.core.impl.phase.AbstractPhase.predictWorkingStepScore(AbstractPhase.java:147)
    at org.optaplanner.core.impl.constructionheuristic.DefaultConstructionHeuristicPhase.doStep(DefaultConstructionHeuristicPhase.java:82)
    at org.optaplanner.core.impl.constructionheuristic.DefaultConstructionHeuristicPhase.solve(DefaultConstructionHeuristicPhase.java:69)
    at org.optaplanner.core.impl.solver.AbstractSolver.runPhases(AbstractSolver.java:83)
    at org.optaplanner.core.impl.solver.DefaultSolver.solve(DefaultSolver.java:193)
    at com.iconsoft.metro.opt.solver.ScheduleProblemSolution.solve(ScheduleProblemSolution.java:203)
    at com.iconsoft.metro.opt.Main.main(Main.java:36)

触发时机 #

异常出现在锚点重新分配任务后，构造启发式步骤日志：

23:56:43.328 DEBUG     CH step (0), time spent (226), score (-59init/-5hard/0soft), selected move count (6), picked move (Task 320522: (uninitialized) {null -> Inspector #0}).
23:56:43.362 DEBUG     CH step (1), time spent (260), score (-58init/-4hard/0soft), selected move count (7), picked move (Task 320527: (uninitialized) {null -> Inspector #1}).
23:56:43.396 DEBUG     CH step (2), time spent (294), score (-57init/-3hard/0soft), selected move count (8), picked move (Task 321652: (uninitialized) {null -> Inspector #2}).
...
23:56:43.743 DEBUG     CH step (8), time spent (641), score (-51init/-10hard/0soft), selected move count (14), picked move (Task 326806: (uninitialized) {null -> Inspector #0})
Exception in thread "main" java.lang.IllegalStateException: VariableListener corruption after completedAction()...

问题根源与修复方案 #

问题根源 #

当前变量监听器仅更新了被修改的单个任务的shadowStartTime，但链式结构中，后续任务的shadowStartTime依赖前序任务的结束时间。当某个任务的时间变化时，整条链上的所有后续任务都需要重新计算shadowStartTime，否则会导致阴影变量值过时，触发OptaPlanner的一致性检查异常。

修复方案 #

修改变量监听器，在更新当前任务后，遍历并更新该任务后续的所有链式节点：

public class SlotUpdateVariableListener implements VariableListener<ScheduleProblemSolution, ScheduleSlot> {

    @Override
    public void afterEntityAdded(ScoreDirector<ScheduleProblemSolution> scoreDirector, ScheduleSlot slot) {
        updateChain(scoreDirector, slot);
    }

    @Override
    public void afterVariableChanged(ScoreDirector<ScheduleProblemSolution> scoreDirector, ScheduleSlot slot) {
        updateChain(scoreDirector, slot);
    }

    /**
     * 更新当前节点及其后续整条链的shadowStartTime
     */
    private void updateChain(ScoreDirector<ScheduleProblemSolution> scoreDirector, ScheduleSlot startingSlot) {
        ScheduleSlot currentSlot = startingSlot;
        while (currentSlot instanceof Allocation) {
            ScheduleSlot prevSlot = currentSlot.getPreviousSlot();
            // 计算当前任务的开始时间：锚点或前序任务的结束时间 + 换乘/移动时间
            Long startTime = prevSlot != null 
                ? prevSlot.getFinishTime() + prevSlot.timeToNext(currentSlot) 
                : null;

            // 更新阴影变量并通知ScoreDirector
            scoreDirector.beforeVariableChanged(currentSlot, "shadowStartTime");
            ((Allocation) currentSlot).setShadowStartTime(startTime);
            scoreDirector.afterVariableChanged(currentSlot, "shadowStartTime");

            // 找到当前任务的下一个节点（链式结构中的后继任务）
            currentSlot = findNextSlot(scoreDirector, currentSlot);
            if (currentSlot == null) {
                break;
            }
        }
    }

    /**
     * 从解决方案中找到以currentSlot为前序节点的任务
     */
    private ScheduleSlot findNextSlot(ScoreDirector<ScheduleProblemSolution> scoreDirector, ScheduleSlot currentSlot) {
        ScheduleProblemSolution solution = scoreDirector.getWorkingSolution();
        // 假设解决方案类提供获取所有任务的方法
        for (Allocation allocation : solution.getAllocations()) {
            if (currentSlot.equals(allocation.getPreviousSlot())) {
                return allocation;
            }
        }
        return null;
    }

    // 按需实现其他VariableListener方法，比如beforeVariableChanged、afterEntityRemoved等
}

额外注意事项 #

1. 锚点时间正确性：确保Inspector的getFinishTime()方法返回合理值（比如检查员的上班起始时间），因为直接挂在锚点下的任务会使用该值计算开始时间。
2. 变量监听器类名：原代码中类名SlotUpdateVariableListerer存在拼写错误（应为SlotUpdateVariableListener），需修正避免类加载问题。
3. 双向链优化：如果频繁遍历所有任务查找后继节点影响性能，可以考虑维护双向链式关系（在ScheduleSlot中添加nextSlot属性），但需确保双向链与previousSlot变量保持一致。

内容的提问来源于stack exchange，提问作者kol