求解器太慢

Question

我仍然在使用OptaPlanner来优化一个类似于VehicleRoutingExample的链式计划问题。我的规划实体有一个规划变量，它是另一个规划实体。分数是用IncrementalScore计算的HardSoftScores。

目前我的问题是，求解器需要的时间仍然太长，无法找到一个可接受的解决方案。

我想优化具有固定数量的工人的问题，这些工人必须处理具有多个时间窗口的固定数量的订单。

订单是我的链式实体，而工人则被用作链条的锚点。我正在计算监听器的订单的开始和结束时间点。另一个监听器正在保存每个实体中的每个链的锚点(因为它需要很多时间来遍历一个可能比1000个实体…更长的链。)

我的目标是解决一个有大约3000个实体的问题，此时求解器需要超过2个小时才能得到一个可接受的解决方案。对于400个实体的较小问题，它需要近5分钟，这也太长了。10分钟对于较大的问题10分钟就可以了，对于较小的问题1分钟。

我已经使用基准测试找到了最佳的求解器配置…

有没有人看到一些让我的求解器更快的可能性？

附注: der是使用多线程的机会吗?或者optaplanner已经在使用它了吗？

Answer 1

看看6.2.0.CR2中的附近选择(还有CR1 )。

​

​

它还只有部分记录...而且还不是所有的移动类型(只需更改和交换移动)...耐心点。但是，一旦你达到2K个实体甚至更多，它就会好得离谱。没有它，它甚至比这个图中最糟糕的更糟糕：

​

​

以下是我的一个本地基准测试的快速而肮脏的复制和粘贴：

<#list [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 150, 200, 5000] as linearDistributionSizeMaximum>
  <solverBenchmark>
    <name>LA Nearby LinDist max${linearDistributionSizeMaximum}</name>
    <solver>
        <constructionHeuristic>
            <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
        </constructionHeuristic>
        <localSearch>
            <unionMoveSelector>
                <changeMoveSelector>
                    <entitySelector id="entitySelector1"/>
                    <valueSelector>
                        <nearbySelection>
                            <originEntitySelector mimicSelectorRef="entitySelector1"/>
                            <nearbyDistanceMeterClass>org.optaplanner.examples.vehiclerouting.domain.solver.nearby.CustomerNearbyDistanceMeter</nearbyDistanceMeterClass>
                            <linearDistributionSizeMaximum>${linearDistributionSizeMaximum}</linearDistributionSizeMaximum>
                        </nearbySelection>
                    </valueSelector>
                </changeMoveSelector>
                <swapMoveSelector>
                    <entitySelector id="entitySelector2"/>
                    <secondaryEntitySelector>
                        <nearbySelection>
                            <originEntitySelector mimicSelectorRef="entitySelector2"/>
                            <nearbyDistanceMeterClass>org.optaplanner.examples.vehiclerouting.domain.solver.nearby.CustomerNearbyDistanceMeter</nearbyDistanceMeterClass>
                            <linearDistributionSizeMaximum>${linearDistributionSizeMaximum}</linearDistributionSizeMaximum>
                        </nearbySelection>
                    </secondaryEntitySelector>
                </swapMoveSelector>
            </unionMoveSelector>
            <acceptor>
                <lateAcceptanceSize>200</lateAcceptanceSize>
            </acceptor>
            <forager>
                <acceptedCountLimit>1</acceptedCountLimit>
            </forager>
        </localSearch>
    </solver>
  </solverBenchmark>
</#list>
<#list [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 150, 200, 5000] as parabolicDistributionSizeMaximum>
  <solverBenchmark>
    <name>LA Nearby ParDist max${parabolicDistributionSizeMaximum}</name>
    <solver>
        <constructionHeuristic>
            <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
        </constructionHeuristic>
        <localSearch>
            <unionMoveSelector>
                <changeMoveSelector>
                    <entitySelector id="entitySelector1"/>
                    <valueSelector>
                        <nearbySelection>
                            <originEntitySelector mimicSelectorRef="entitySelector1"/>
                            <nearbyDistanceMeterClass>org.optaplanner.examples.vehiclerouting.domain.solver.nearby.CustomerNearbyDistanceMeter</nearbyDistanceMeterClass>
                            <parabolicDistributionSizeMaximum>${parabolicDistributionSizeMaximum}</parabolicDistributionSizeMaximum>
                        </nearbySelection>
                    </valueSelector>
                </changeMoveSelector>
                <swapMoveSelector>
                    <entitySelector id="entitySelector2"/>
                    <secondaryEntitySelector>
                        <nearbySelection>
                            <originEntitySelector mimicSelectorRef="entitySelector2"/>
                            <nearbyDistanceMeterClass>org.optaplanner.examples.vehiclerouting.domain.solver.nearby.CustomerNearbyDistanceMeter</nearbyDistanceMeterClass>
                            <parabolicDistributionSizeMaximum>${parabolicDistributionSizeMaximum}</parabolicDistributionSizeMaximum>
                        </nearbySelection>
                    </secondaryEntitySelector>
                </swapMoveSelector>
            </unionMoveSelector>
            <acceptor>
                <lateAcceptanceSize>200</lateAcceptanceSize>
            </acceptor>
            <forager>
                <acceptedCountLimit>1</acceptedCountLimit>
            </forager>
        </localSearch>
    </solver>
  </solverBenchmark>
</#list>