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

Question

我有两个司机，每个司机都有一组大约 15 个他们需要在一天内开车去的地点。为两个司机计算最短路线不是问题(使用矩阵路由 api)。

司机可以在他们的 route 有相同的位置。如果它们相同，则它们需要同时存在。所以我需要制作计算最快路线的软件，但有时司机需要同时在同一地点。

我的问题:我如何制作这个软件，有没有我可以使用的库？

有 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 说明它)并将矩阵分配给您的问题。