使用 Google OR-Tools 解决无人机的车辆路由问题 (VRP)

Question

我尝试使用 OR-Tools 来解决 VRP。问题是我不想找到每辆车的最短路线，而是找到消耗最少能量的路线。 解释：如果车辆必须转弯，它会比直线行驶的车辆消耗更多的能量。本文针对旅行商问题描述了此问题：https://par.nsf.gov/servlets/purl/10192402。

我使用此文档：https://developers.google.com/optimization/routing/vrp来获得第一个 VRP 求解器。

论文中的文档建议采用遗传算法方法，但我不太明白 OR-Tools 如何解决问题以及在哪里可以更改变量来实现我的目标。

我的结论是，即使阅读了整个文档，我仍然不明白 OR-Tools 如何解决 VRP。

欢迎任何帮助和解释。

最大

Answer 1

当使用多辆车时，OR-Tools 路由库解决的是 VRP，而不是 TSP。不同之处在于，在 TSP 中，距离矩阵描述了图，当两个节点之间有弧时，两个节点之间的距离是有限的，如果两个节点没有连接，则两个节点之间的距离是无限的。

如果是 VRP，距离矩阵大多是密集的，表示这两个节点之间的最短距离。

这意味着，在规划卡车车队时，转弯成本（例如在美国左转）必须整合到任意两个节点之间的最短路径中。

现在规划道路网络上的路径以最大化效率的问题是一个不同的问题，与路由库解决的 VRP 问题无关，并且最终无法通过该工具很好地解决。

Answer 2

您找到其他方法或工具了吗？