分配工作人员任务

Question

在模拟中,工作人员必须在地图上移动执行任务.

每个模拟'tick',它们可以移动一个方格.

一旦它们与它相邻就执行任务需要10个滴答.

任务方块无法通过.与工人在一起的广场不能通过.不止一个工人可以在广场上工作.

工人不互相竞争; 目标是尽快完成所有任务.

补充说:理想情况下,算法应该直观易懂,易于实现.这不是每个人都想要的吗？如果它有效,例如模型可以更新和重复使用,而不是经常从头开始重新计算,这是一个很大的优势.理想情况下,它可以使用本地最优,所以它不会试图暴力破坏NP问题,但避免过于贪婪并提前思考,而不是基本上随意的漫游,工人们很少注意别人的计划.

这是一个例子:

工人1和2必须完成方形A,B,C和D上的任务.

你如何决定哪个工人做哪个任务？

似乎不言而喻,1应该做A,2应该做C.

1是距离A 4个方格,因此将在14个刻度中完成.1应该去哪里,为什么？

如果有另一个任务 - E - 直接放在B上面怎么办？

工人用什么逻辑来决定接下来要去哪里？

我尝试过的:

这是一个业余爱好的RTS游戏,我已经尝试过这样做,以便闲置的工作人员继续前进到最近的任务,或者继续前进到最近的任务,这是其他工作人员没有做的.

事实证明,这种贪婪的方法效率低下,而且玩家测试清楚地表明它是站不住脚的.因为战略采矿/建筑/农业是游戏的关键,并且因为我不希望玩家微观管理和路由所有工人,所以我正在寻找一种相当公平且合理的最佳算法,工人可以使用它.

Answer 1

即使有一个工人,这也是NP完全优化问题(然后它成为旅行商问题),所以让我们忘记"最优".

如果你知道工人1将处理任务A1,A2,...,工人2将处理任务B1,B2,......等等,那么你可以在做出决定后,尝试解决独立的旅行推销员问题一个接一个,你得到了所有工人的时间表和路径.

然而,问题在于,在解决了该集合的旅行商问题之前,您无法知道为工人完成一组任务A1,A2,...需要多长时间,因为步行时间会影响总时间.执行任务.

因为它只是一个游戏,而工人可以被认为不是最佳思想家,我会使用一个随机过程:

1. 随机为所有工作人员分配所有任务
2. 使用贪婪算法计算工作人员任务组中每个工作人员的步行时间的上限
3. 尝试随机移动,将一个任务从一个工作者移动到另一个工作者,或者在两个工作者之间交换任务
4. 接受基于禁忌搜索或模拟退火原则的移动,取决于移动是否减少最大执行时间的上限(步行时间+任务执行时间),因此目标是尽可能早地完成最后一项任务
5. 在N次迭代之后,停止并计算出旅行商问题的更好解决方案,例如使用随机搜索,或明确是否问题很小(例如每个工人少于10个任务)

Answer 2

不要贪婪地将工作人员分配到最近的任务,而是贪婪地将最远的任务分配给其"最近的"工作人员 - 也就是说,路径紧密通过并且有足够的松弛时间来处理它的工人.这样你就有了一个(贪婪的)概念,即完成所有任务所需的最短时间.

例如:

D是"最遥远的任务",即使没有定义该术语,所以将D分配给1.它是15 + 10个单位,所以set t= 25,松弛在2到25之间.

现在,这是分配下一个任务的距离成本,考虑最短的路线.

    A   B   C   D  
1  10  22  24   -
2  29  19  18   -

但根据贪婪的想法,这是真正的成本; 增加到最大时间t.

    A   B   C   D  
1  10  22  24   -
2   4  0    0   -

由于C具有最高的成本(从贪婪的角度来看,这是最危险的任务),因此将C指定为2.

下一个成本如下

    A   B   slack    A  B
1  10  22     0     10 22
2  21  11  (-)7     14  4

分配B因为22是最大时间的最大增量t.将其分配给工人2.

...

背包问题有很多种方法,但如果需要简单,这可能是接下来要尝试的方法.也许存储任务之间的最短路径.这是一种过于贪婪的方式,可以提前思考一下!

Answer 3

这确实听起来很像(已经提到的)多个座席的旅行推销员问题(TSP,http://en.wikipedia.org/wiki/Travelling_salesman_problem).这实际上是类似于多背包(MKP,http://en.wikipedia.org/wiki/Knapsack_problem#Multiple_knapsack_problem)或甚至Bin包装(http://en.wikipedia.org/wiki/Bin_packing_problem)的问题.

有一组算法可能适用于这种情况,它被称为"蚁群优化"(ACO,http://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms).

要结合这两者,有一些实现使用ACO来解决MKP问题; 在这种情况下,这似乎是一种很好的方法,例如:

http://www.researchgate.net/publication/221246039_Probabilistic_Model_of_Ant_Colony_Optimization_for_Multiple_Knapsack_Problem