我正在使用 OptaPlanner 来优化与提供的示例非常相似的车辆路径问题。
我面临以下挑战，并且会欣赏一些想法。
某些对客户的访问与其他访问存在关联，例如:
- 一次访问必须与另一次访问同时开始。
- 一次访问必须在另一次访问结束后 2 小时开始。
- 一次访问必须分配给分配给另一次访问的同一辆车。
挑战是:如何允许访问移动，而在移动其中一个访问时不会导致分数降低？
每次访问可能在不同的机器上(分配给不同的车辆)，因此所有提供的移动选择器很可能提供仅改变一次访问的移动。由于依赖性，此类移动很可能会导致分数较低，并且永远不会被选择。
相同的开始场景:任何改变单次访问开始时间的举动都会导致分数降低。 相同车辆场景:任何将一次访问更改为不同车辆的移动都会导致较低的分数。
目前我正在使用 Tabu Search，结果令人满意。 延迟接受可能是答案。
谢谢。
最佳答案
您所描述的是 score trap 的一种形式。虽然当分数陷阱存在时，延迟接受可能会比禁忌搜索产生更好的结果(并且只需更改 2 行即可切换到它)，但它仍然会严重影响结果。
那些docs描述摆脱分数陷阱的 2 个答案:
1) 提高评分函数粒度在这种情况下不起作用。
2) 在这种情况下，粗粒度移动将发挥作用。例如，您可以添加自定义移动工厂(但也保留原始 moveSelectors - 或者更好的是在使用和不使用原始 moveSelectors 的情况下进行基准测试)。让自定义移动工厂生成不太可能打破这些限制的移动。例如:如果访问 A 和 B 需要相同的车辆，则将 A 移动到另一个车辆链中，同时将 B 移动到同一车辆链中的其他位置(重用 CompositeMove)。
我很快就会记录第三种方法(但我认为它不容易应用于此案例):
3)在某些情况下，可以将此类硬约束烘焙到模型的类图中(这使它们成为内置硬约束)。例如，在考试安排中，如果需要在同一时间段进行 2 个或更多考试，则只有 1 个考试是“领导者”并且具有时间段变量。其他考试是“群体”考试，这意味着当领导者发生变化时，它们的时间段会通过影子变量进行调整。
关于java - OptaPlanner 车辆路线和客户拜访之间的关系，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19501486/