计算在同一时间

Question

我有两个驱动程序和每个驾驶员都有一套约15个地点，他们需要把车开到单日最快的路线和一些点。计算两个驱动程序的最短路径不是问题（使用矩阵路由API）。

的驱动程序可以在他们的路线相同的位置。如果它们一样，那么它们都需要同时在那里。所以我需要制作计算最快路线的软件，但有时候司机需要同时在同一地点。

我的问题：我怎样才能使这个软件，并在那里我可以使用任何库？

实施例具有6个位置（软件需要计算15）：

驾驶员A的位置：

• 51.873215,4.606388（开始）
• 51.7498817,4.3705702
• 51.8395805,4.3535099（与驱动程序B相同）
• 51.8961411,4.4681101
• 52.0041504,4.48627
• 52.061006,4.486609（结束）

位置驱动B的：

• 51.873215,4.606388（开始）
• 51.7914314,4.6571202
• 51.8422203,4.33954
• 51.8670325,4.3453742
• 51.8395805,4.3535099（同驾驶员A）
• 51.7084897,4.6603792（结束）

软件需要对坐标进行排序以获得最快的路线。但司机必须在这个位置上的同一时间同一地点：51.8395805,4.3535099

预期的输出驱动器答：https://www.google.nl/maps/dir/51.873215,4.606388/51.8395805,4.3535099/51.7498817,4.3705702/51.8961411,4.4681101/52.0041504,4.48627/52.061006,4.486609/

预期的输出驱动器B： https://www.google.nl/maps/dir/51.873215,4.606388/51.8395805,4.3535099/51.8422203,4.33954/51.8670325,4.3453742/51.7914314,4.657120251.7084897,4.6603792/

Answer 1

你可以试试jsprit 。

如果您确定两个驱动程序在指定位置先验地彼此相遇的时间窗口，则很容易建模（只需查看wiki中的“简单示例”即可了解如何建模和解决此类问题一个问题）。 时间窗口定义如下：

Service.Builder.newInstance("service").setTimeWindow(TimeWindow.newInstance(10,20)) ... 

如果你不想设定时间窗口提前，你需要学习如何设置自己的状态和约束。它部分记录在here以及一些例子和邮件列表中。

从一个位置考虑您的最短路线到另一个（从你的矩阵路由API），只需使用core.util。VehicleRoutingTransportCostMatrix（jsprit.examples.CostMatrixExample演示它）并将矩阵分配给您的问题。

Answer 2

它看起来类似于一个vrp问题。您可以将问题分解为更小的问题，例如考虑驾驶员作为车厂遇到的位置。然后你可以用这个约束来使用vrp算法。