OptaPlanner 车辆路线规划细粒度移动

Question

我正在处理一个与 coachshuttlegathering 示例几乎相同的问题。我有垃圾箱和应该收集垃圾箱的车辆。每个垃圾桶都有一个有效载荷，每辆车都有一个容量。

我设置了我的解决方案，如 coachshuttlegathering 示例所示，这基本上有效，但我最终处于局部最优状态，因为默认移动不够粗粒度。具体来说，我需要一次将来自 2 辆不同车辆的 2 个垃圾箱链分配给不同的车辆。

我尝试将现有的 subChainChangeMoveSelector 与 cartesianProductMoveSelector 结合使用，如下所示：

<cartesianProductMoveSelector>
    <subChainChangeMoveSelector>
        <entityClass>...Wastebin</entityClass>
        <subChainSelector>
            <valueSelector>
                <variableName>previousRouteComponent</variableName>
            </valueSelector>
        </subChainSelector>
        <valueSelector>
            <variableName>previousRouteComponent</variableName>
        </valueSelector>
        <selectReversingMoveToo>false</selectReversingMoveToo>
    </subChainChangeMoveSelector>
    <subChainChangeMoveSelector>
        <entityClass>...Wastebin</entityClass>
        <subChainSelector>
            <valueSelector>
                <variableName>previousRouteComponent</variableName>
            </valueSelector>
        </subChainSelector>
        <valueSelector>
            <variableName>previousRouteComponent</variableName>
        </valueSelector>
        <selectReversingMoveToo>false</selectReversingMoveToo>
    </subChainChangeMoveSelector>
    <fixedProbabilityWeight>1.5</fixedProbabilityWeight>
</cartesianProductMoveSelector>

当我运行使用此配置的求解器时，出现以下异常：

The entity (Wastebin{id=3}) has a variable (previousRouteComponent) with value (Wastebin{id=3}) which has a sourceVariableName variable (nextWastebin) with a value (Wastebin{id=1}) which is not null.
Verify the consistency of your input problem for that sourceVariableName variable.

知道这里出了什么问题吗？一件奇怪的事情是规划实体显然指向自己。我在想，也许移动选择了 2 个重叠的子链，这在某些时候会导致不一致？

编辑

打开 FULL_ASSERT 会产生更多详细信息：

Caused by: java.lang.IllegalStateException: UndoMove corruption: the beforeMoveScore (0/0/23/-2245/-12) is not the undoScore (0/0/23/-1358/-2) which is the uncorruptedScore (0/0/23/-1358/-2) of the workingSolution.
  1) Enable EnvironmentMode FULL_ASSERT (if you haven't already) to fail-faster in case there's a score corruption.
  2) Check the Move.createUndoMove(...) method of the moveClass (class org.optaplanner.core.impl.heuristic.move.CompositeMove). The move ([[Wastebin{id=3}..Wastebin{id=3}] {Wastebin{id=3} -> Vehicle{id=2}}, [Wastebin{id=3}..Wastebin{id=3}] {Wastebin{id=3} -> Wastebin{id=1}}]) might have a corrupted undoMove (Undo([[Wastebin{id=3}..Wastebin{id=3}] {Wastebin{id=3} -> Vehicle{id=2}}, [Wastebin{id=3}..Wastebin{id=3}] {Wastebin{id=3} -> Wastebin{id=1}}])).
  3) Check your custom VariableListeners (if you have any) for shadow variables that are used by the score constraints with a different score weight between the beforeMoveScore (0/0/23/-2245/-12) and the undoScore (0/0/23/-1358/-2).
    at org.optaplanner.core.impl.phase.scope.AbstractPhaseScope.assertExpectedUndoMoveScore(AbstractPhaseScope.java:145)
    at org.optaplanner.core.impl.localsearch.decider.LocalSearchDecider.doMove(LocalSearchDecider.java:153)
    at org.optaplanner.core.impl.localsearch.decider.LocalSearchDecider.decideNextStep(LocalSearchDecider.java:121)
    at org.optaplanner.core.impl.localsearch.DefaultLocalSearchPhase.solve(DefaultLocalSearchPhase.java:72)
    at org.optaplanner.core.impl.solver.DefaultSolver.runPhases(DefaultSolver.java:215)
    at org.optaplanner.core.impl.solver.DefaultSolver.solve(DefaultSolver.java:176)

不幸的是，输出包含两次 move，我为此问题创建了 PLANNER-599。我从调试器中得到了正确的撤消移动：

[Wastebin{id=3}..Wastebin{id=3}] {Wastebin{id=3} -> Vehicle{id=1}}
[Wastebin{id=3}..Wastebin{id=3}] {Wastebin{id=3} -> Vehicle{id=1}}

我没有任何自定义 VariableListeners

Answer 1

"The entity (Wastebin{id=3}) has a variable (previousRouteComponent) with value (Wastebin{id=3})"

也就是说Wastebin-3指向了它自己？这将违反链式变量原则。从理论上讲，笛卡尔生产移动不应该导致这种情况 - 但如果您的输入问题是有效的，那一定会发生......

开启环境模式FULL_ASSERT看看它是否早点失败。

Answer 2

这是a known issue in OptaPlanner 6.4.0.Final. It happens with complex CompositeMoves and it's due to the design of the Move interface. Fixing it is not trivial, see PLANNER-611。

更新：已为 7.0.0.CR1 修复。

OptaPlanner 车辆路线规划细粒度移动

OptaPlanner vehicle routing course grained moves

optaplanner

编辑