使用 Optaplanner 解决具有大量客户和复杂约束的 VRPTW
Using Optaplanner to solve VRPTW with large number of customers and sophisticated constraints
我正在使用 OptaPlanner 开发 VRPTW 问题的求解器，当需要为大量客户提供服务时，我遇到了一个问题。我所说的大数字是指多达 10,000 个客户。我已经尝试 运行 求解器大约 48 小时，但没有找到可行的解决方案。
我使用高度定制的 VRPTW 领域模型，该模型引入了所谓的额外规划实体 "Workbreak"。工间休息就像客户，但他们可以有一个位置，这实际上是另一个规划值 - 因为每天工人都可以 return 回家或去酒店。工间休息有固定的出发时间（通常是第二天早上）和可变的到达时间（因为它取决于链中的前一个实体）。硬约束关心在特定时间点后不允许 "arrive" 到 Workbreak。还有其他硬约束，例如：
- 每个客户的多次服务时间windows
- 每周最后一位顾客必须是特殊顾客"storage space visit"（工作人员需要在下周之前收集材料）
- 长作业管理（当客户需要的服务时间超过指定时间时，应在一天中的特定时间之前提供服务）
- 每个工作日的最大作业数
- 每个工作日的最大总工作持续时间（因为工人的工作时间不能超过指定时间）
- 工间不能有离工人家太近的旅馆。
- 周日不提供作业
...以及更多 - 总共有 19 个必须应用的硬约束。还有 3 个软约束。
所有上述约束最初都写成 Drools 规则，但由于许多基于累积的约束（每天最大工作数、每天最大小时数、每周加班小时数），求解器的整体速度（基准）是大约 400 step/sec。
起初我认为求解器的速度太慢，无法在合理的时间内得出可行的解决方案，所以我将所有规则重写为 easy score calculator，并且速度不错 - 大约 4600 steps/sec .我知道这只会对极少数客户产生最佳效果，但我想知道 Drools 是否是性能不佳的原因。然后我将所有这些规则重写到增量分数计算器中（并在分数错误损坏的痛苦中幸存下来，直到所有这些规则都被成功修复）。令人惊讶的是，与简易分数计算器相比，增量分数计算对于少数客户来说有点慢，但这不是问题，因为总体速度约为 4000 steps/sec - 无论我有多少实体。
最让我烦恼的是超过一定数量的客户（问题从 1000 个客户开始）求解器无法找到可行的解决方案。目前我正在使用延迟接受和计步算法，因为它们对这类问题的表现非常好（至少对较少的客户而言）。我也使用了模拟退火，但没有成功，主要是因为我找不到算法特定参数的好值。
我也实现了一些自定义动作：
- 当使用 change/swap 移动之类的其他移动更改同级实体时更改工作间断位置的复合移动（它有助于逃避许多分数陷阱，因为改进步骤通常需要在一个步骤中执行至少两个移动)
- 移动工厂以获得更好的长期工作分配（它会生成试图将服务时间较长的客户置于工作日链前端的移动）
- 工间休息分配移动工厂（它生成有助于按正确顺序安排工间休息的移动）
现在我摸不着头脑，想知道应该如何诊断问题的根源。我怀疑它可能遇到了分数陷阱，但我已经修改了求解器，因此它每分钟都会保存最佳分数的快照。看完这些快照后，我意识到分数还在下降。硬约束的数量能起到作用吗？我怀疑需要执行许多动作才能找出提高分数的动作。事实上，对于这种问题，48 小时可能并不算多，它应该计算一整周？不幸的是我没有什么可以比较的。
我想知道如何确定它是单纯的性能问题，还是求解器（算法、自定义移动、hard/soft 分数）配置问题。
真的很抱歉我的英语不好
TL；DR 但 FWIW：
- 要扩展到超过 1k 个位置，您需要使用 NearBy selection。
- 要扩展到超过 10k 个位置，添加 Partitioned Search。
我正在使用 OptaPlanner 开发 VRPTW 问题的求解器，当需要为大量客户提供服务时，我遇到了一个问题。我所说的大数字是指多达 10,000 个客户。我已经尝试 运行 求解器大约 48 小时，但没有找到可行的解决方案。
我使用高度定制的 VRPTW 领域模型，该模型引入了所谓的额外规划实体 "Workbreak"。工间休息就像客户，但他们可以有一个位置，这实际上是另一个规划值 - 因为每天工人都可以 return 回家或去酒店。工间休息有固定的出发时间（通常是第二天早上）和可变的到达时间（因为它取决于链中的前一个实体）。硬约束关心在特定时间点后不允许 "arrive" 到 Workbreak。还有其他硬约束，例如：
- 每个客户的多次服务时间windows
- 每周最后一位顾客必须是特殊顾客"storage space visit"（工作人员需要在下周之前收集材料）
- 长作业管理（当客户需要的服务时间超过指定时间时，应在一天中的特定时间之前提供服务）
- 每个工作日的最大作业数
- 每个工作日的最大总工作持续时间（因为工人的工作时间不能超过指定时间）
- 工间不能有离工人家太近的旅馆。
- 周日不提供作业
...以及更多 - 总共有 19 个必须应用的硬约束。还有 3 个软约束。
所有上述约束最初都写成 Drools 规则，但由于许多基于累积的约束（每天最大工作数、每天最大小时数、每周加班小时数），求解器的整体速度（基准）是大约 400 step/sec。
起初我认为求解器的速度太慢，无法在合理的时间内得出可行的解决方案，所以我将所有规则重写为 easy score calculator，并且速度不错 - 大约 4600 steps/sec .我知道这只会对极少数客户产生最佳效果，但我想知道 Drools 是否是性能不佳的原因。然后我将所有这些规则重写到增量分数计算器中（并在分数错误损坏的痛苦中幸存下来，直到所有这些规则都被成功修复）。令人惊讶的是，与简易分数计算器相比，增量分数计算对于少数客户来说有点慢，但这不是问题，因为总体速度约为 4000 steps/sec - 无论我有多少实体。
最让我烦恼的是超过一定数量的客户（问题从 1000 个客户开始）求解器无法找到可行的解决方案。目前我正在使用延迟接受和计步算法，因为它们对这类问题的表现非常好（至少对较少的客户而言）。我也使用了模拟退火，但没有成功，主要是因为我找不到算法特定参数的好值。
我也实现了一些自定义动作：
- 当使用 change/swap 移动之类的其他移动更改同级实体时更改工作间断位置的复合移动（它有助于逃避许多分数陷阱，因为改进步骤通常需要在一个步骤中执行至少两个移动)
- 移动工厂以获得更好的长期工作分配（它会生成试图将服务时间较长的客户置于工作日链前端的移动）
- 工间休息分配移动工厂（它生成有助于按正确顺序安排工间休息的移动）
现在我摸不着头脑，想知道应该如何诊断问题的根源。我怀疑它可能遇到了分数陷阱，但我已经修改了求解器，因此它每分钟都会保存最佳分数的快照。看完这些快照后，我意识到分数还在下降。硬约束的数量能起到作用吗？我怀疑需要执行许多动作才能找出提高分数的动作。事实上，对于这种问题，48 小时可能并不算多，它应该计算一整周？不幸的是我没有什么可以比较的。
我想知道如何确定它是单纯的性能问题，还是求解器（算法、自定义移动、hard/soft 分数）配置问题。
真的很抱歉我的英语不好
TL；DR 但 FWIW：
- 要扩展到超过 1k 个位置，您需要使用 NearBy selection。
- 要扩展到超过 10k 个位置，添加 Partitioned Search。