optaplanner - Optaplanner VRP 示例，同一时间窗口内每次停靠需要多辆车

Question

我们正在使用定制的VRP教程示例来优化服务工程师前往客户那里执行某些维修和安装任务的日常路线。我们确实有时间窗口，我们会在未来数周内优化 1000 多项任务。

我们的（简化的）领域模型包括：

• 工程师- 做所有工作的人
• 任务- 在某个位置完成的单个工作任务
• DailyRoute - 给定日期的工程师路线，由任务的链接列表组成

---

作为一项新要求，我们现在必须支持两名工程师在同一任务上并行工作。

我们目前的计划是通过为第二个工程师创建子任务来实现这一点，并实施一个规则，即他们的到达时间必须与主要任务相同。然而，这是有问题的，因为将相互依赖的任务之一移动到不同的时间（例如，不同的 DailyRoute）将主要违反上述约束。

到目前为止，我们已经提出了以下想法：

• 仅允许单个任务在与其他任务分配的路线 同一天移动到 DailyRoute
  • 可以通过 SelectionFilter 完成
• 使用CompositeMoves将两个并行任务同时移动到不同的日期
  • 我们是否需要自定义 MoveIteratorFactory 来选择连接的任务？
  • 或者这可以用 CartesianProductMoveSelector 代替吗？
  • 我们可以使用附近的选择来进行第二步，以选择与第一步的新指定日期相同的日期（当时是否已经完成了一步）？

标签： optaplannervehicle-routing

Answer 1

对于同时从事同一任务的两名工程师，请参阅文档“设计模式”，特别是“延迟到最后一个模式”。没有示例，但我们的支持服务已经帮助实施了几次 - 它有效。

对于同一位置的多个站点：我已经看到用户将此类访问分成更小的部分，以允许 optaplanner 选择要聚合的部分。它有效，但并不完美：碎片越细，搜索空间就越大 - 添加一个专注于将所有碎片移动在一起的自定义移动可能会有所帮助（但我不会从它开始）。一般来说：如果最小的车辆的容量为 100，我会进行一些实验，将容量分成一半 - 他们也尝试四分之一，只是为了通过 optaplanner-benchmark 进行基准测试来看看什么效果最好。