Optaplanner：生成 VRP 的部分解决方案，其中卡车 and/or 停靠点可能根据时间 windows 保持未分配状态

Question

我正在解决车辆路径问题的变体。该模型一直有效，直到我实施了一项更改，其中某些车辆 and/or 停靠点可能仍未分配，因为施工过滤器由于时间 window 考虑不允许移动（不允许迟到）。

问题大小为 2 trucks/3 站。 truck_1 分配了 2 个停靠点（Stop_1 和 Stop_2），因此 1 辆卡车和 1 个停靠点仍未分配，因为 truck_2 将迟到 Stop_3。

我有以下错误：

INFO  o.o.c.i.c.DefaultConstructionHeuristicPhase - Construction Heuristic phase (0) ended: step total (2), time spent (141), best score (-164hard/19387soft).

java.lang.IllegalStateException: Local Search phase started with an uninitialized Solution. First initialize the Solution. For example, run a Construction Heuristic phase first.
    at org.optaplanner.core.impl.localsearch.DefaultLocalSearchPhase.phaseStarted(DefaultLocalSearchPhase.java:119)
    at org.optaplanner.core.impl.localsearch.DefaultLocalSearchPhase.solve(DefaultLocalSearchPhase.java:60)
    at org.optaplanner.core.impl.solver.DefaultSolver.runPhases(DefaultSolver.java:213)
    at org.optaplanner.core.impl.solver.DefaultSolver.solve(DefaultSolver.java:176)

我尝试将计划变量设置为 null (nullable = true)，但在链接变量的情况下似乎不允许这样做。我正在使用 Optaplanner 6.2。

请帮忙，谢谢，皮尤什

Answer 1

您的构造过滤器可能过于严格，它可能会阻止构造启发式创建初始化解决方案。您应该从构造过滤器中删除时间 window 约束，并将其作为硬分数约束添加到您的分数计算器中。

来自 Optaplanner docs:

Instead of implementing a hard constraint, it can sometimes be built in. For example: If Lecture A should never be assigned to Room X, but it uses ValueRangeProvider on Solution, so the Solver will often try to assign it to Room X too (only to find out that it breaks a hard constraint). Use a ValueRangeProvider on the planning entity or filtered selection to define that Course A should only be assigned a Room different than X.

This can give a good performance gain in some use cases, not just because the score calculation is faster, but mainly because most optimization algorithms will spend less time evaluating unfeasible solutions. However, usually this not a good idea because there is a real risk of trading short term benefits for long term harm:

Many optimization algorithms rely on the freedom to break hard constraints when changing planning entities, to get out of local optima.

Both implementation approaches have limitations (feature compatiblity, disabling automatic performance optimizations, ...), as explained in their documentation.

Optaplanner：生成 VRP 的部分解决方案，其中卡车 and/or 停靠点可能根据时间 windows 保持未分配状态

Optaplanner: Generating a partial solution to VRP where trucks and/or stops may remain unassigned based on Time windows

drools

optaplanner