java - 同时计算最快路线和一些点

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

预期输出驱动器A: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 说明了这一点)并将矩阵分配给您的问题。