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

Question

问题:我需要删除(N)从办公室员工家园(坐标可用).我有(x) 7座和(y) 4座驾驶室.

1. 我必须设计一种算法,让所有员工在最短距离内离开家.

2. 此外,该算法必须告诉我必须选择多少7座或/和4座车辆以便行驶最小距离.

例如.如果我有15名员工,那么算法可能会告诉我使用1(7座)驾驶室和2(4座)驾驶室并让每个驾驶室的员工如下:

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

方法:我认为这是一个旅行推销员问题,有多个推销员,每个人都可以旅行的城市数量上限.销售人员也不需要回到原点.我想到了Ant的殖民地问题,但我无法明智地选择哪种算法可供选择

要求:我真的需要ALGORITHM.无论是TSP还是Ant的殖民地,都无关紧要.我会欢迎意见,但我真的需要算法.

Answer 1

这是成本最小化问题,而不是旅行商问题.它与TSP有关,因为TSP是一个非常具体的成本最小化问题.

解决方案包括三个步骤:

1. 生成员工下车点(节点)列表

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

   • 总距离是防止浪费的一道防线,确保路线不会太长.
   • 距离总和有助于算法汇聚于许多员工居住的社区(如果可能).
   • 因为硬币问题的这种变化允许不完美的解决方案,所以它简化为背包问题的变体.每辆出租车的实用性是capacity.如果您还希望选择最便宜的方式来运送您的员工,utility(taxi) = capacity/cost.由此我们最简单的解决方案是贪婪; 谁在乎空旷空间？如果您真的非常关心完全填写出租车(而不是经济有效),那么您需要一个更复杂的解决方案.您只需将最小距离指定为指标(每增加一次出租车乘以成本).我认为这是代表'我不想付出太多'.因此:taxi_cost(nodes) = math.floor(amount(nodes)/max(utility(taxis)+1).这个等式选择最便宜,最宽敞的出租车,并计算出完全为这条路线提供服务所需的出租车数量.
   • 请务必计算您检查的每个网络的成本 sum(cost(path))
3. 找到最便宜的网络后,对于所选网络中的每条路径:
   • 列出前往最远节点的员工列表
   • 与这些员工一起填写首选出租车
   • 重复下一个最远的节点,直到你有一辆完整的出租车,然后将装满的出租车添加到列表中.如果您的员工用尽,您已完成为该路线分配出租车.(最远的第一选择的好处是,如果路线的那部分位于办公室的区域内,您可以要求未填充的出租车的员工走路).

上面的算法并不完美,但它会有许多理想的倾向.

• 路线将尽可能短并覆盖尽可能大的区域(通过不循环或分支)
• 路线将倾向于服务社区,而不是试图重叠责任.这部分算法不是最优的,但是有效.这使得删除服务路线非常容易,无需重新计算运输网络.
• 选择的出租车将具有成本效益,有助于避免支付超过必要的费用.
• 考虑到升级到更高容量的更宽敞的出租车的相对成本,路线将使用尽可能少的出租车
• 因为最远的出租车将会满员,如果您决定取消对其他出租车的服务,则对您的员工上班能力的影响较小.

接近完美的每一步都比前一步花费了许多倍,因此如果解决方案提供了理想的功能,则可以接受减少的回报.尽管该算法进行了一些潜在的次优权衡,但它们具有巨大的价值; 您的出租车路线网络变得更容易修改.

如果您想制定最佳解决方案,背包问题,硬币问题和变更问题有助于确定出租车和路线的成本.

生成树是确定路线的最有效方法.将生成树置于办公室中心,并将每个分支的成本计算为距离办公室的最大距离.尽量保持每个分支服务区域的高密度,以便更容易添加和删除出租车路线.

研究寻路可以帮助您学习如何确定良好的成本函数,以便您可以在数字上比较不同的潜在路径.请记住,您的网络由一组路径组成,但需要自己的成本函数,以便您可以比较不同的布局.

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

Answer 2

从我的角度来看，你的算法应该解决两个问题：每种类型的汽车数量和最短距离（如何对员工进行编号取决于你，或者你应该提供更多详细信息）。抱歉，我正在使用手机，无法使用该网站的所有功能。

对于汽车数量，您可以使用以下算法。要解决与距离相关的问题，您应该提供有关路径及其长度的更多信息。然后可以将图算法与此相结合来实现这一目的。这里11=7+4。

Begin

Integer temp:= n/11
Integer rem:= n mod 11
If rem=0

    x:=temp
    y:=temp

Else if rem<=4

    x:=temp
    y:=temp+1

Else if rem<=7

    x:=temp+1
    y:=temp

Else

    x:=temp+1
    y:=temp+1

Endif

End