Optaplanner/graphhopper:如何解决VRP minimax优化？

Question

我有一个由N辆车和> 2N个路点组成的路线规划问题。我想优化他们的路线，使所有车辆的最大时间/成本最小化。

在JVM中，唯一的选项要么是optaplanner，要么是options。

然而，这个问题并没有在他们的任何文档中得到证明。看起来这是一个被大多数用户忽略的边缘情况。有没有可能扩展这两个库中的任何一个来解决这样的问题？非常感谢你的建议。

Answer 1

请参阅OptaPlanner's page on Vehicle Routing

以下是一个使用比利时数据集的示例，在大约32小时的实际道路驾驶时间(不考虑交通)中，使用10辆车(并不是所有车辆)交付到50个地点(~您的路点)：

​

​

请参阅optaplanner-webexamples示例以查看实际操作(包括google地图和openstreetmap可视化)，并查看optaplanner-examples的车辆路径示例以处理更大的数据集、多站点案例和/或时间窗口。

上面的案例最小化了总持续时间(32小时)，但通过对vehicleRoutingScoreRules.drl进行一些更改，您可以将其更改为最小化每辆车的最大持续时间(只需将每辆车的持续时间相加并对该数字的平方进行惩罚，请参阅OptaPlanner文档中的“公平/负载平衡”)。