多人多地点高效调度

Question

我正在尝试创建一个程序来安排异步拼车计划。例如，给定一条由这条线表示的长街：

A---------------B---------------C---------------D

如果Alice、Bob和Chad都需要同时在D点，并且分别从A点、B点和C点开始，但是Bob没有车，那么程序需要输出Alice接Bob的最佳解决方案。如果googlemapsapi用于确定两点之间的距离和时间（精度可能是近似值），那么确定最有效的操作集的最佳方法是什么？你知道吗

在这个简化的场景中，可能性的数量是相当有限的（Alice捡起Bob，Chad捡起Bob，Bob走路），并且根据旅行的时间或距离来迭代和评估它们是相当简单的，但是当可能性的数量达到数千或数百万时，这种方法不能很好地扩展。我已经工作了几个月，试图开发一个更复杂的算法，但由于我有限的知识，我一直不是很成功

Answer 1

我建议把这个问题概括一下，我是这样理解的：

给定一个描述地图上位置L={l_0, ..., l_n}之间连接的图G，以及一组参与者P = {p_0, ..., p_n}为每个参与者寻找最佳行程I={l_s, ..., l_d}，以便他们从各自的来源地l_s旅行到共同的目的地l_d，这样所有参与者到达目的地时都独立于他们的旅行方式。一些参与者可能需要绕道去接其他参与者，在这种情况下，我们希望找到总成本最低的解决方案（如所需的旅行时间）

下面是我将如何尝试解决这个问题的粗略草图：

1. 构建一个包含所有节点及其连接方式的图（例如，在您的示例中，该图是G = [(A,B),(B,C),(C,D)]）。

2. 在每条边上添加一个权重，以某种标准化的方式（公制、恒定速度/时间等）描述其距离。

3. 对于每个参与者，根据他们的出行方式（如汽车、自行车、步行），指定他们可用的最大速度。

4. 对于具有car（A，C）的参与者，使用最短路径算法（如A* (a star)）计算每个参与者从各自的源位置到达目标目的地所需的实际时间。这实际上是一个两步的过程，第一步：计算最短路径，第二步：计算每一条边所需的时间。

Google的mapapi可能已经提供了进行这些计算所需的全部或大部分数据（甚至可以为您进行计算）。你知道吗

因此，您可以为每位参与者提供最佳的行程安排。现在我们必须考虑没有车的参与者（这里，B）。为此，我们必须找到参与者绕道而行，以使绕道产生的成本最低。因此

1. 计算A、C两条最短路径中的每一条，即步骤1：源位置=>；绕行位置（B），步骤2：绕行位置（B）=>；目的地位置（D）

2. 选择最佳选项，即最小化总行程时间

因为您将此标记为Python问题，所以您可能希望签出NetworkX或graph-tool来实现。你知道吗

免责声明：显然，这遗漏了很多细节，甚至可能是完全关闭。感谢您的反馈。对于paraphrase Donald Knuth，我只考虑了这个问题，没有实现或测试它。你知道吗