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

Question

问题:我要掉线 (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 的殖民地，都没有关系。我会欢迎意见，但我真的需要算法。

Answer 1

这是一个成本最小化问题，而不是一个旅行商问题。它与 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))

找到要服务的最便宜的网络后，对于所选网络中的每条路径:

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

用这些员工填充首选出租车

重复下一个最远的节点，直到您有一辆满载的出租车，然后将满载的出租车添加到列表中。如果你的员工用完了，你就完成了为路线分配出租车的工作。 (最远优先选择的好处是，如果路线的那部分在办公室的街区内，您可以要求空载出租车中的员工步行)。

上面的算法并不完美，但它会有很多可取的趋势。

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

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

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

考虑到升级到容量更大、更宽敞的出租车的相对成本，路线将使用尽可能少的出租车

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

每一步接近完美的成本都比前一步高出许多倍，因此如果解决方案提供了理想的功能，则 yield 递减是可以接受的。尽管该算法做出了一些潜在的次优权衡，但它们具有巨大的值(value)；您的出租车路线网络变得更容易修改。

If you'd like to make an optimal solution, the Knapsack Problem, Coin Problem, and Change-making Problem help determine the cost of taxis and routes.

Spanning Trees are the most effective way to determine routes. Center the spanning tree at the office and calculate the cost of each branch as the maximum distance from the office. Try to keep each branch servicing areas with high density to make it easier to add and remove taxi routes.

Studying pathfinding can help you learn how to determine good cost functions so that you can numerically compare different potential paths. Remember that your network consists of a set of paths, but will require its own cost function so that you can compare different layouts.

我为 this answer 编写了深入的寻路指南.寻路文章很少，只是没有深入解决很多问题空间。如果您有多个优先级，好的成本函数可以为您提供近乎完美的解决方案。不幸的是，好的成本函数是特定于领域的，因此您需要自己识别它们。如果您不确定如何制作具有某些特征的路径，请随时给我留言，我会帮助您找出一个好的成本函数。