如何修复OptaPlanner中的施工启发式?



求解器必须处理一个计划实体和两个计划变量。它将 TimeGrain 和会议室分配给会议。由于构造启发式的搜索空间非常大,我不得不实现顺序移动选择。

<constructionHeuristic>
<constructionHeuristicType>FIRST_FIT</constructionHeuristicType>
<changeMoveSelector>
<valueSelector variableName="startingTimeGrain"/>
</changeMoveSelector>
<changeMoveSelector>
<valueSelector variableName="room"/>
</changeMoveSelector>
</constructionHeuristic>

这样做的问题是,求解器有时会分配一个没有可用房间的 TimeGrain ,因此当需要分配房间时,求解器找不到不破坏硬约束的房间。

然后,本地搜索阶段能够找到一个不会破坏任何硬约束的解决方案,但我必须运行很长时间才能获得良好的解决方案质量。例如,求解器将返回远程会议作业,即使我有一个旨在尽快返回作业的软限制。

如何修改或优化构造启发式,使其不会选择没有任何可用空间的 TimeGrain ?

通常约束如下所示:

when
MyEntity(myFirstVar != null, mySecondVar != null, ...)
...
then ...

现在,当第一个 var 已按顺序分配但第二个 var 未分配时,此规则将永远不会与实体匹配。所以第一步是只做:

when
MyEntity(myFirstVar != null, ...)
...
then ...

接下来,您可以添加一个约束来专门执行类似操作来影响 CH:

when
accumulate(
MyEntity(myFirstVar != null, mySecondVar == null, ...)
sum(roomUsage) > capacity
then ...

最新更新