两家运输公司中哪一家的交货时间最短？

Question

我正在处理一个算法问题。我有一个已知的图形算法，其中有一个中心节点。目标是通过两个运输者将货物从这个中心节点交付到其他指定节点。每个运输者每次只能携带最多一单位的货物，因此在每次节点访问后，他们会回到中心节点进行下一步操作。我应该计算完成此操作所需的最短时间。

我的方法是使用dijkstra算法来查找中心节点到所有其他节点的最短路径，考虑节点之间的不同距离。然后对于所有运输员应该去的节点（有时甚至需要多次到达特定节点），我将值加倍，因为需要往返距离。我将值分为两组，使它们的总和尽可能接近，因为有两个运输员，并打印较大的值。

然而，这个解决方案似乎并不完美。我需要增加另一项功能来完善它。如果第一位运输员知道他比预计提前8个单位结束工作，他可以在途中的某个时候为第二位运输员准备好货物，这样他就不必一直等到中央节点了，但要少一点时间。这样他们的总时间将相等，但会更短。不幸的是，这并不总是可能的（例如只有一个节点的一个交付等）。我需要将这个方面添加到我的程序中。

- ludgo

---

你有一个完整的例子吗，展示这个操作是如何实现最佳时间的？ - David Eisenstat

我思考了这个简单的例子。想象一下，他们需要从中心1向节点2、3、3交付三种货物。根据我的解决方案，他们的时间将是16,12。在更好的解决方案中，第一个人将5个单位的物品运往3号节点，把它留在那里，回到中心并处理2号节点。第二个人先处理3号节点，然后完成另一个3号节点任务。两者的时间都是14。问题是如何确定对于给定的已知图形，在所有可能的情况下，是否可以进行此优化。 - ludgo

这两个运输器在最后需要返回中央节点吗？如果不需要，你可以让它们最后供应远离中央节点的节点，以节省时间。 - j_random_hacker

这是一个车辆路径问题，底层需要通过Dijkstra算法从路由引擎计算成本矩阵。这两个问题都可以使用开源软件解决，对于车辆路径规划软件，请参见jsprit: https://github.com/graphhopper/jsprit，对于路由引擎，请参见https://github.com/graphhopper/graphhopper（注意：我参与构建此内容）。 - Karussell

Answer 1

实际上，您正在处理一个“车辆路径规划”问题，我们可以通过一些方法来解决，例如启发式算法或构造性方法。

您可以在这里找到一些有用的资料（我希望如此）关于这些方法。

- mama23n