algorithm - 为我的童子军营地规划启发式

Question

我正在计划一个童子军营地，需要自动化计划。

我有一组侦察兵需要被分组到具有一定能力的帐篷中，受到许多限制。

在这些限制中：

• 帐篷的可用性（它们在整个夏天都设置和取消设置）
• 侦察员的可用性
• 帐篷的颜色
• 球探喜欢的颜色
• 等等

我有超过 500 名侦察员和大约 20 个帐篷。

我正在寻找一个好的算法来解决这个问题。
我可以将其建模为 MILP，但它太大而无法有效解决，并且无法给出近似解，这基本上使它成为不行。

关于我应该看什么的任何建议？禁忌？模拟退火？其他启发式方法？

Answer 1

好吧，如果您说有很多限制，那么 MILP 将是解决此问题的最佳方法。但是，如果您提到的约束是唯一的，那么可以考虑以下方法。

将此建模为运输问题。

首先，您过滤掉不可用的帐篷和不可用的侦察兵。

对于每种颜色的帐篷，计算每个颜色帐篷的总容量 = summation( tentCapacity )。这些颜色应为目的地。

根据学生喜欢的帐篷颜色对他们进行分组。这些应该是来源。

在源/目的地矩阵中，将学生运送到其首选颜色帐篷的成本为零，其他颜色的成本为 1。

IMO 这可以使用运输问题解决技术来解决：http ://www.me.utexas.edu/~jensen/models/network/net8.html

编辑：上面描述的运输问题公式是一种非常通用的方法，您可以在其中处理不同优先级的多个偏好。如果每个侦察兵只有一个偏好，那么我认为问题是微不足道的，只需先将所有喜欢的彩色帐篷填满，然后将剩余的侦察兵分配给其他不喜欢的帐篷。

Answer 2

这与医院床位规划（以及监狱床位分配和酒店房间分配）非常相似。基本上，病人是侦察兵，床是睡袋，房间是帐篷。寻找 INRC2011 的实现，例如这个：

模拟退火、禁忌搜索和延迟验收都适用于医院病床规划。一般来说，延迟验收在OptaPlanner目前针对该用例的基准测试中获胜。