最少行程次数

Question

我有latitude和longitude分N societies，order count这些社团，我也有latitude和longitude分卡车将从那里部署并将被发送到这些不同的社会（如亚马逊交付）的仓库。一辆卡车可以送货 maximum 350 orders（订单数 < 350）。因此无需考虑订单数量超过 350 件的商品（我们通常会派两辆卡车或一辆更大的卡车）。现在我需要确定一种模式，在这种模式下，卡车的部署方式应尽可能减少行程次数。

考虑到我们根据this脚本确定两个社团或仓库之间的距离是'X'是准确的，我们如何解决这个问题？我首先想到我们可以使用子集求和问题来解决它，也许吧？对我来说似乎是图形上的 dp，无限数量的推销员的旅行推销员问题。

卡车数量没有限制。

Answer 1

这是一个典型的旅行商问题 (TSP)，称为 NP 完全问题。这意味着如果您正在寻找最佳解决方案，则必须测试大多数组合。如您所知，!350 是巨大的。

不过，正如 Henry 所建议的，您可以寻找一个不一定是最好的解决方案。许多称为 "heuristic" 的算法可以让您以非常有效的方式找到一个好的解决方案。看看这里的一些例子 https://en.wikipedia.org/wiki/Travelling_salesman_problem.

最简单的启发式算法可能是一个贪婪的解决方案，比如总是把最近的未访问点作为下一个社会。