Timefold：能否过滤PlanningListVariable的所有无意义2opt移动？

问题背景 #

使用PlanningListVariable求解旅行商问题（TSP），配置2-Opt移动选择器如下：

<kOptListMoveSelector>
  <minimumK>2</minimumK>
  <maximumK>2</maximumK>
</kOptListMoveSelector>

日志中出现无意义的2-Opt移动，这类移动的端点索引满足abs(firstEndpointIndex - secondEndpointIndex) <= 1，示例如下：

2023-12-07 14:03:20,831 DEBUG [ai.tim.sol.cor.imp.loc.DefaultLocalSearchPhase] (pool-7-thread-1)     LS step (91293), time spent (60096), score (0hard/-20852279soft),     best score (0hard/-20852279soft), accepted/selected move count (1/192), picked move (2-Opt(firstEntity=salesman.mainModel.domain.Route@5ad597bf, secondEntity=salesman.mainModel.domain.Route@5ad597bf, firstEndpointIndex=99, secondEndpointIndex=99)).
2023-12-07 14:03:20,831 DEBUG [ai.tim.sol.cor.imp.loc.DefaultLocalSearchPhase] (pool-7-thread-1)     LS step (91294), time spent (60096), score (0hard/-20852279soft),     best score (0hard/-20852279soft), accepted/selected move count (1/51), picked move (2-Opt(firstEntity=salesman.mainModel.domain.Route@5ad597bf, secondEntity=salesman.mainModel.domain.Route@5ad597bf, firstEndpointIndex=8, secondEndpointIndex=7)).
2023-12-07 14:03:20,831 DEBUG [ai.tim.sol.cor.imp.loc.DefaultLocalSearchPhase] (pool-7-thread-1)     LS step (91295), time spent (60096), score (0hard/-20852279soft),     best score (0hard/-20852279soft), accepted/selected move count (1/92), picked move (2-Opt(firstEntity=salesman.mainModel.domain.Route@5ad597bf, secondEntity=salesman.mainModel.domain.Route@5ad597bf, firstEndpointIndex=96, secondEndpointIndex=95)).

这类移动对解无实际优化作用，需过滤，但KOptListMove为非公开类，无法通过实现SelectionFilter接口处理，需替代方案。

解决方案 #

方案1：使用ScriptFilter（推荐） #

OptaPlanner支持脚本过滤器（ScriptFilter），可在配置中直接过滤移动，无需依赖内部类。通过MVEL表达式直接访问移动的字段（即使类非公开）：

修改kOptListMoveSelector配置，添加scriptFilter：

<kOptListMoveSelector>
  <minimumK>2</minimumK>
  <maximumK>2</maximumK>
  <scriptFilter>
    <scriptType>MVEL</scriptType>
    <script>
      Math.abs(move.firstEndpointIndex - move.secondEndpointIndex) > 1
    </script>
  </scriptFilter>
</kOptListMoveSelector>

MVEL可直接访问对象字段，字段名称可从日志中的move描述确认（firstEndpointIndex、secondEndpointIndex），配置简洁且性能足够。

方案2：自定义MoveSelector包装器 #

若脚本过滤器不满足需求，可自定义MoveSelector包装kOptListMoveSelector，通过反射过滤无效移动：

1. 实现自定义MoveSelector：

public class FilteredKOptMoveSelector implements MoveSelector {
    private final MoveSelector delegate;

    public FilteredKOptMoveSelector(MoveSelector delegate) {
        this.delegate = delegate;
    }

    @Override
    public boolean isCountable() {
        return delegate.isCountable();
    }

    @Override
    public boolean isNeverEnding() {
        return delegate.isNeverEnding();
    }

    @Override
    public long getSize() {
        return delegate.getSize();
    }

    @Override
    public Iterator<Move> iterator() {
        return new FilteredMoveIterator(delegate.iterator());
    }

    @Override
    public SelectionCacheType getCacheType() {
        return delegate.getCacheType();
    }

    private class FilteredMoveIterator implements Iterator<Move> {
        private final Iterator<Move> delegateIterator;
        private Move nextValidMove;

        public FilteredMoveIterator(Iterator<Move> delegateIterator) {
            this.delegateIterator = delegateIterator;
            advanceToNextValid();
        }

        private void advanceToNextValid() {
            nextValidMove = null;
            while (delegateIterator.hasNext()) {
                Move move = delegateIterator.next();
                try {
                    Field firstIndexField = move.getClass().getDeclaredField("firstEndpointIndex");
                    firstIndexField.setAccessible(true);
                    int firstIndex = (int) firstIndexField.get(move);

                    Field secondIndexField = move.getClass().getDeclaredField("secondEndpointIndex");
                    secondIndexField.setAccessible(true);
                    int secondIndex = (int) secondIndexField.get(move);

                    if (Math.abs(firstIndex - secondIndex) > 1) {
                        nextValidMove = move;
                        break;
                    }
                } catch (NoSuchFieldException | IllegalAccessException e) {
                    e.printStackTrace();
                }
            }
        }

        @Override
        public boolean hasNext() {
            return nextValidMove != null;
        }

        @Override
        public Move next() {
            Move current = nextValidMove;
            advanceToNextValid();
            return current;
        }
    }
}

2. 在配置中使用自定义MoveSelector：

<customMoveSelector>
  <moveSelectorClass>com.yourpackage.FilteredKOptMoveSelector</moveSelectorClass>
  <delegateMoveSelector>
    <kOptListMoveSelector>
      <minimumK>2</minimumK>
      <maximumK>2</maximumK>
    </kOptListMoveSelector>
  </delegateMoveSelector>
</customMoveSelector>

此方案通过反射绕过KOptListMove非公开限制，但需注意OptaPlanner版本更新可能导致字段名称变化，需同步调整代码。

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