最小体力劳动算法

Question

我目前正在为下面的问题寻找一个合适的算法。

仓库里有一堆托盘，上面装着同样的产品。一个完整的托盘包含80个盒子。但有很多托盘和较少的盒子。当订单进来时，一些托盘需要合并成一个完整的80箱托盘。这个动作是手工完成的，所以这是体力劳动。

现在我正在寻找将仓库中的托盘分配给订单的最佳方法，以便将体力劳动的数量降到最低。

示例：

boxes

• order
  1. 托盘A: 80盒
  2. 托盘B: 40盒
  3. 托盘C: 39
  4. 托盘C:39盒
  5. 订单2: 79盒

  F 215

可能的解决方案

• 订单1:托盘A- 30盒
• 订单2:托盘B+托盘C

=>总体力劳动:移动69箱

• 订单1:托盘B+ 10盒从托盘C
• 订单2:托盘A-1盒

=>总体力劳动:移动11箱

第二种解决方案是可取的，因为所涉及的劳动力较少。

我看过匈牙利算法，但我认为这不是解决这个问题的适当办法。

你有什么建议吗？

Answer 1

匈牙利算法给出了一个2-近似(最多移动两倍于需要的盒子)。我们将托盘与订单相匹配，其中将托盘与订单匹配的成本是需要移动到或离开托盘的盒数的一半。(我想，通常情况下，托盘比订单多，所以如果你的匈牙利算法实现需要一个方阵，那么就制作与任何托盘匹配的零成本的假订单。)这是一个2-近似，因为，为了扩展我的评论，我们保存一个盒子，只有当我们可以找到一个托盘与太多的盒子和托盘太少。

换句话说，我们支付的最大数量(需要移出托盘的框数)和(需要移动到托盘上的框数)。这一观察激发了以下两种想法。

1. 我们可以构造一个混合整数程序(然后应用一个求解程序库)。对于每个托盘i和j阶有一个0-1变量x(i，j)，我们对x(i，j) =1(所有订单都有一个指定托盘)的I和x(i，j)≤1(所有托盘至多有一个指定顺序)有约束。被最小化的目标是一个自由变量z，其中我们将z≥和约束在i上，j对max(p(i)−o(j)，0) x(i，j)；z≥和在i，j上(o(J)−p(i)，0) x(i，j)。

如果您出于任何原因不想做混合整数规划(尽管我认为您确实应该这样做)，我们可以使用拉格朗日对偶，引入参数 0，1，并支付1−α将一个盒子从订单托盘中移出，α将一个盒子移到订单托盘上。要做到这一点，最简单的方法是使用匈牙利算法尝试一组不同的α，得到最好的匹配结果。聪明的方法是解决上述整数程序线性松弛的对偶，然后根据z上约束的对偶变量设置α，但实际上应该使用混合整数规划。

如果你告诉我你的约束，我可以给出解决办法的建议。