java - OptaPlanner 车辆路线与客户拜访之间的关系

Question

我正在使用 OptaPlanner 优化与提供的示例非常相似的车辆路径问题。

我面临着以下挑战，并且会欣赏一些想法。

一些对客户的访问与其他访问有关系，例如:

• 一次访问必须与另一次访问同时开始。
• 一次访问必须在另一次访问结束后 2 小时开始。
• 必须将一次访问分配给分配给另一次访问的同一车辆。

挑战是:如何在移动其中一个访问时允许移动访问而不会导致较低的分数？

每次访问都可能在不同的机器上(分配给不同的车辆)，因此所有提供的移动选择器很可能会提供仅改变一次访问的移动。由于依赖性，此类移动很可能导致较低的分数，并且永远不会被选择。

相同的开始场景:任何改变一次访问开始时间的移动都会导致较低的分数。相同的车辆场景:任何改变一次访问不同车辆的移动都会导致较低的分数。

目前我正在使用 Tabu Search，结果令人满意。延迟接受可能是答案。

谢谢。

Answer 1

您所描述的是 score trap 的一种形式 。尽管在存在分数陷阱时延迟接受可能会产生比禁忌搜索更好的结果(并且它只是更改 2 行以切换到它)，但它仍然会对结果产生严重影响。

那些docs描述 2 个答案以摆脱分数陷阱:

1) 改进评分函数粒度在这种情况下不起作用。

2) Course grained moves 将在这种情况下起作用。例如，您可以添加自定义移动工厂(但也保留原始 moveSelectors - 或者更好的是使用和不使用原始 moveSelectors 进行基准测试)。让自定义移动工厂生成不太可能打破这些约束的移动。例如:如果访问 A 和 B 需要相同的车辆，则将 A 移动到另一辆车的链中，同时将 B 移动到同一车辆链中的其他位置(重复使用 CompositeMove )。

还有第三种方法，我很快就会记录下来(但我认为它不太适用于这种情况):

3) 在某些情况下，可以将此类硬约束烘焙到模型的类图中(这使它们成为内置的硬约束)。例如在考试安排中，如果 2 个或更多考试需要在同一个时间段进行，则只有 1 个考试是“领导者”并且有一个时间段变量。其他考试是“羊群”，这意味着当领导者改变时，他们的时间段会根据影子变量进行调整。