1

不是 100% 确定标题，请随意编辑以更通用且对所有用户都有帮助

我有一个订单捕获“门户”，可以捕获订单。部分订单是数量或订单。

我现在需要处理订单，以便可以构建一个托盘以优化使用托盘。

例如，一个包装好的托盘尺寸可以是 1.62 立方米 (1x1.2x1.35)

然后我在订单上有以下物品

产品编号、数量、总量

1、10、0.5立方米
2、3、0.2
立方米
3、5、1.2立方米 4、1、0.15立方米
5、15、0.6立方米

我想处理这个，我假设使用 mysql 事务，以便获得以下输出：

托盘 1：产品 1、2、5。总体积=1.3 立方米
托盘 2：产品 3,4。总体积=1.35立方米

因此，为了澄清，脚本将采用第一个 0.5 立方的托盘，然后在列表中查找最接近 0.85 的下一个订单以实现 1.35 立方米的目标。在这种情况下，它将是 0.6。现在总共 1.1 个立方体。剩余空间现在为 0.25 个立方体。列表中最接近的项目现在是产品 2 @ 0.2 立方体。现在总共 1.3 个立方体，并且不存在 0.05 个或更少的产品，因此托盘是完整的。下一个可用产品现在是产品 3 @ 1.2 立方体。因此需要 0.15 或更小的产品。产品 4 是准确的体积，因此添加到托盘并关闭。

我希望这有助于澄清我的要求。

是否有一个 mysql 事务可以帮助解决这个问题，或者这需要用 php.ini 处理吗？

对此的任何帮助将不胜感激，只是不确定如何构建此逻辑。

一如既往地感谢您的时间，

在此处输入图像描述

mysql表如下：

在此处输入图像描述

4

3 回答 3

2

这是经典的装箱问题，它是 NP 难的（也就是说，我们还没有弄清楚这个问题是否可以在多项式时间内解决）。找到最佳包装无异于尝试每一种可能的组合。

如果您不关心找到最佳解决方案，那么您在问题中描述的贪婪启发式（称为首次拟合递减）是一个合理的近似值；还有其他启发式方法可以保证总体上更优化的结果，但它们变得相当复杂。

您可以按如下方式在 PHP 中实现 FFD（使用 PDO 进行数据库访问）：

define('PALLET_SIZE', 1 * 1.2 * 1.35);

$dbh = new PDO("mysql:dbname=$dbname", $username, $password);

$qry = $dbh->prepare('
  SELECT   code, qty, volume
  FROM     orders
  WHERE    order_id = :order
  ORDER BY volume DESC
');

$qry->execute(array(':order' => 123));

$pallets = array();
while ($order = $qry->fetch()) {
  if ($order['volume'] > PALLET_SIZE) die('item too big');

  for ($i = 1; $i <= $order['qty']; $i++) { // remove this loop if not needed
    $placed = false;
    foreach ($pallets as &$pallet) {
      if ($pallet['remaining'] >= $order['volume']) {
        $pallet['remaining'] -= $order['volume'];
        $pallet['items'][] = $order['code'];
        $placed = true;
        break;
      }
    }
    if (!$placed) $pallets[] = array(
      'remaining' => PALLET_SIZE - $order['volume'],
      'items' => array($order['code'])
    );
  }
}

print_r($pallets);
于 2012-10-24T09:22:45.947 回答
1

有没有mysql事务

我假设你的意思是一个 mysql 函数。

不，mysql中没有任何东西可以帮助您解决这个问题。这是一个NP难题。解决它的最有效方法可能是遗传算法，但是您的数据中没有足够的信息来准确地实现这一点 - 包装取决于形状（即所有维度）与体积一样多。

如果您确实有尺寸，那么让人类设置包装而不是尝试在代码中进行包装仍然容易得多。

作为一个快速的解决方案，我会比较一组列表的 N 个副本，随机排序，遍历每个副本创建完整的托盘，然后选择具有最少托盘（或其他需要的特征）的列表。为 N 选择正确的值将取决于大小的分布，以及您希望花费多少时间处理数据。

于 2012-10-24T08:42:50.310 回答
1

这类似于背包问题；这是一个只有尝试所有可能的组合才能完美解决的问题。随着可能组合数量的增加，这很快成为一个问题。在您的示例中，将有 33 个！组合 - 相当大的数量。所以那条路线可能不是我们想要走的……

没有“开箱即用”的解决方案，尽管这里有背包问题的示例代码。这可能会有所帮助。

几年前我写了一个程序，它对类似的问题做了合理的工作；伪代码类似于：

for each order
  while (unallocated items on order)
    create new pallet 
    while not (pallet = full)
      allocate largest remaining item smaller than remaining capacity to pallet 
    loop
  loop
next order

这个算法做得不错——船厂里的人喜欢它，因为最大的物品总是在装箱单的顶部（因此最终在堆栈的底部）。企业承认算法不能保证是最优的；在实践中，这只会对大订单产生影响，因为算法的轻微改进可能会为我们节省一个托盘；在大多数情况下，使算法更有效意味着货物中的最后一个托盘几乎是空的。

于 2012-10-24T09:25:56.267 回答