2

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

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

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

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

挑战是：如何在移动访问时允许移动访问而不导致分数降低？

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

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

目前我正在使用禁忌搜索，结果令人满意。迟到可能是答案。

谢谢。

4

1 回答 1

2

您所描述的是一种分数陷阱。尽管当分数陷阱存在时，Late Acceptance 可能比禁忌搜索产生更好的结果（并且它只是更改了 2 行来切换到它），但它仍然会对结果产生严重影响。

这些文档描述了摆脱分数陷阱的 2 个答案：

1）在这种情况下，提高评分函数的粒度是行不通的。

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

我将很快记录第三种方式（但我认为它不容易适用于这种情况）：

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

于 2013-10-22T07:32:45.137 回答