java - 多辆没有容量和成本矩阵的车辆

Question

我正在尝试使用两辆相同类型且从同一位置开始的车辆来创建 VRP。我希望解决方案以最具成本效益的方式为问题中的每辆车创建一条路线。我正在使用 GraphHopper 计算每个服务位置之间的道路距离和时间，并使用该信息创建一个运输成本矩阵。

我的问题是所有服务都放在一条路线上，而第二辆车从未使用过。在输出中，我可以看到问题包含两辆车，但解决方案只显示了一条路线，一辆车。

如果我设置车辆的容量和服务的大小，我可以同时使用这两种车辆。我知道如果我不指定它们，它们将被忽略，但这会导致所有服务使用相同的车辆吗？

我错过了什么吗？

如果需要，我可以发布代码示例。

谢谢！

Answer 1

在没有容量限制的情况下，使用单辆车总是最优的（如果满足三角不等式，即道路距离）。换句话说，没有容量限制的 VRP = TSP。

可以这样想：假设您有两条路线，一条在城市 A 结束（在返回站点之前），另一条在城市 B 开始（在离开站点之后）。现在想象删除从 A 到 depot 的路段和从 depot 到 B 的路段，并添加从 A 到 B 的路段。根据三角不等式，c_AB <= c_A,depot + C_depot,B，所以新的解决方案比旧的。