algorithm - 对于有多个销售人员且没有返回但已知顶点和端点的 TSP 的解决方案是什么？

Question

我不知道我的措辞是否正确，我什至不确定这是否是 TSP 问题，但情况就是这样。

我正在设计并尝试优化送货服务的路线规划器。我有多个司机(销售员)，他们都在中央仓库(起点)取包裹，然后在回家的路上送货。他们的家乡位置(终点)是已知的， map 上的所有交付目的地(顶点)也是已知的。送货完毕后，司机直接回家，不再返回站点。

这是什么样的问题，我应该研究什么样的解决方案？我一直将其视为不返回的多 TSP，但仍然无法确定任何接近最佳的旅行。我也尝试过最短长度的哈密顿路径，但一旦我引入第二个驱动程序，我很快就会陷入困境。

也欢迎任何资源、算法和启发式建议。

Answer 1

杰弗里是对的。这是一个车辆路径问题。但是，它不是经典的有能力 (CVRP) 的只有一个站点的，因为您的司机可能在家里而不是在站点开始和结束。因此，您的问题变得有点困难，变成了取货和送货问题 (VRPPD)。

简而言之:如果您的司机只是在站点开始和结束，那就是 CVRP。如果他们在家中开始和结束，则为 VRPPD。

对于 CVRP，您可以找到许多开源算法，例如 OptaPlanner它是用 Java 编写的(Geoffrey 对此了解更多)或 VRPH这是一个 C++ 库。当谈到 VRPPD 时，可用的开源算法的数量会减少。也许你可以用 OptaPlanner 来做(我不是百分百确定)。但是你肯定可以用 jsprit 解决它我用Java实现的。

如果您的问题很大并且您需要快速响应时间(计算时间)，您最好将 VRPPD 转换为 CVRP，方法是假设司机先从家骑车到车站，最后再从车站骑车到家。但是这样你肯定会失去优化潜力。