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で処理する必要がありますか？

このロジックを構築する方法がわからない場合でも、これに関するヘルプをいただければ幸いです。

いつもお時間をいただきありがとうございます、

ここに画像の説明を入力してください

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 に答える