algorithm - 有多个推销员的旅行推销员，每个推销员的城市数量有限制吗？

问题:我需要将(n)个雇员从办公室放到他们的家中(可用坐标)。我有(x) 7人座和(y) 4人座出租车。

我必须设计一种算法，以使所有员工在最小行驶距离时都可以回家。

另外，算法必须告诉我必须选择多少辆7座或4座汽车才能行驶最小距离。

例如。如果我有15名员工，则算法可能会告诉我使用1个(7人座)驾驶室和2个(4人座)驾驶室，并且每个驾驶室中都有员工，如下所示:

[(E2，E4，E6，E8)，(E1，E3，E5，E7，E9，E10，E12)，(E11，E13，E14，E15)]

方法:我认为这是一个旅行推销员问题，有多个推销员，每个城市可以旅行的城市数量上限。同样，推销员也无需回到原点。我想到了 Ant 的殖民地问题，但我无法真正明智地选择哪种算法

要求:我真的需要算法。无论是TSP还是 Ant 的殖民地，都没有关系。我欢迎您提出意见，但我确实需要算法。

最佳答案

这是成本最小化的问题，而不是旅行商的问题。从某种意义上说，它与TSP有关，TSP是一个非常具体的成本最小化问题。

该解决方案包括三个步骤:

生成员工下岗点(节点)列表

创建不交叉也不分支的不同路径。这些将是您的路线，有助于防止浪费的路线重叠。使用cost(path) = distance(furthest node and origin) + taxi_cost(nodes) + sum(distance between nodes)比较路径和/或蛮力所有潜在的网络。网络是路径的布局。请勿分路!!

总距离是防止浪费的防线，可确保路线不会太长。

距离总和有助于算法收敛到许多员工居住的社区(如果可能)。

因为硬币问题的这种变化允许不完善的解决方案，所以将其简化为Knapsack Problem的变化。每辆出租车的实用程序是capacity。如果您还希望选择最便宜的方式来运送员工，请使用utility(taxi) = capacity/cost。因此，我们最简单的解决方案就是贪婪。谁在乎空的空间？如果您真的想完美地填充出租车(而不是节省成本)，那么您将需要一个更加复杂的解决方案。您只需指定最小距离作为度量标准(每增加一个出租车费用乘以成本)。我认为这是说“我不想支付太多”的代理。
因此:taxi_cost(nodes) = math.floor(amount(nodes)/max(utility(taxis)+1)。该方程式选择最便宜，最宽敞的出租车，并计算出要完全​​服务该路线需要多少出租车。

确保将您检查的每个网络的成本计算为sum(cost(path))

找到最便宜的服务网络后，请选择所选网络中的每个路径:

列出前往最远节点的员工列表

用这些雇员填补首选的出租车。

与下一个最远的节点重复，直到您有一辆完整的出租车，然后将已填充的出租车添加到列表中。如果您的员工用完了，那么您已经完成了向该路线分配出租车的工作。 (最先选择的好处是，如果那部分路线在办公室范围内，您可以要求空车上的员工走路。)

上面的算法不是完美的，但是它将具有许多理想的趋势。

路线将尽可能短，并覆盖最大可能的区域(不循环或分支)

路线将倾向于为社区服务，而不是试图重叠职责。该算法的这部分不是最优的，但是很有效。这使得删除服务路线非常容易，而无需重新计算运输网络。

所选出租车将具有成本效益，从而避免支付不必要的费用。

考虑到升级到容量更大的更宽敞的出租车的相对成本，

路线将使用尽可能少的出租车

因为最远距离的出租车将满员，所以如果您决定取消对空出租车的服务，对员工上类能力的影响较小。

每一步接近完美的成本都比上一步高出许多倍，因此，如果解决方案提供所需的功能，那么返回率降低是可以接受的。尽管该算法进行了一些潜在的次优折衷，但它们具有巨大的值(value)。您的出租车路线网络变得更容易修改。



我已经为this answer写了深入的寻路指南。寻路文章很少，只是没有深入探讨很多问题空间。如果您有多个优先级，那么好的成本函数可以为您提供近乎完美的解决方案。不幸的是，好的成本函数是特定于域的，因此您需要自己识别它们。如果您不确定如何创建具有某些特征的路径，请随时告诉我，我将帮助您找到一个好的成本函数。