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

Question

我不知道我的措辞是否正确，我也不确定这是否是TSP问题，但情况如下。

我正在设计并试图优化送货服务的路径规划器。我有多个司机(推销员)，他们都在中央仓库(原厂)取包裹，在回家的路上送货。他们的家的位置(终点)是已知的，所有交付目的地(顶点)在地图上也是已知的。送货完毕后，司机们就回家了，而不是回到仓库。

这是什么样的问题，我应该研究什么样的解决方案？我一直把它当作一个多TSP没有返回，但仍然不能确定任何接近最佳的旅游。我也尝试过最短长度哈密顿路径，但是一旦我介绍了第二个驱动程序，我很快就会遇到一个整体。

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

Answer 1

杰弗里是对的。这是一个车辆路径问题。然而，这并不是经典的有能力(CVRP)的单一车场，因为你的司机可能开始和结束在家里，而不是在仓库。因此，您的问题变得更加困难，并转向一个皮卡和送货问题(VRPPD)。

简而言之:如果你的司机只是在车场开始和结束，这是一个CVRP。如果他们开始和结束在家里，这是一个VRPPD。

对于CVRP，您可以找到许多开源算法，例如用Java编写的OptaPlanner (杰弗里知道更多)或VRPH，它是一个C++库。当涉及到VRPPD时，可用的开源算法的数量会减少。也许你可以用OptaPlanner来做这件事(我不是百分之百肯定)。但是您肯定可以用jsprit来解决这个问题，我用Java实现了它。

如果你的问题很大，而且你需要快速的响应时间(计算时间)，你最好把你的VRPPD转换成CVRP，假设司机先从家里开车到另一个车场，最后再从车场到家。但通过这种方式，您肯定会释放优化潜力。

Answer 2

这被称为车辆路径问题( Vehicle Routing Problem )。

在这个主题上有很多可用的资源，比如视频(获能和/或时间窗)和文档。

VRP网很好地解释了不同的变体。

Answer 3

• 这篇文章似乎考虑了完全相同的问题，并称之为：“K车辆风农村邮递员问题”。 作者: Benavent，Corber，Sanchis和Plana。
• 一些像这一个这样的文章用一个销售员OVRP (OVRP)调用“不返回条件变量”(OVRP)。 作者:d Aksen，Z zyurt和N Aras2.
• 2013年关于VRP而不返回的论文：http://www.hindawi.com/journals/tswj/2013/874349/ 作者: Tantikorn Pichpibul Ruengsak Kawtummachai.