0

目前有没有办法将流量模式合并到 OptaPlanner 中，解决包裹和交付 VRP 问题？

例如。假设我需要在 30 辆汽车中优化今天和明天的 500 辆皮卡和交付，其中每辆皮卡有 1-4 小时的时间窗口。我想尽可能在​​高峰时间避开城市的繁忙地区。

也可以添加（或同时取消）新的取件。

我确定这是一个常见问题。OptaPlanner 中是否存在合适的解决方案？

谢谢！

4

1 回答 1

1

用户经常这样做，但没有开箱即用的例子。

有几种方法可以做到这一点，但一种方法是向 distanceMatrix 添加第 3 个维度，指示离开时间。通常使用 15 分钟、30 分钟或 1 小时的粒度。

这里有两个缩放问题：

  • 记忆。15 分钟意味着每天 24 * 4 = 96。鉴于有 2 个维度，10k 个位置 distanceMatrix 使用几乎 2 GB RAM，显然内存可能会成为一个问题。
  • 预计算时间。计算距离矩阵可能很耗时。“批量算法”可以在这里提供帮助。例如，graphhopper 社区不支持批量距离计算，但他们的企业版 - 以及 OSRM（免费）支持。从远程 Google Maps API 或远程企业 Graphhopper API 获取 3 维矩阵可能会导致带宽问题（见上文，距离矩阵的大小可能会变为数 GB，尤其是在 JSON 或 CSV 等非二进制格式中） .

在任何情况下，一个 3 维矩阵都在那里，只需调整 OptaPlanner 示例的ArrivalTimeUpdateListener使用即可getDistance(from, to, departureTime)。

于 2021-08-27T09:26:20.713 回答