問題タブ [bin-packing]

アイテムのセットを含むことができる最小のビンの寸法を見つけるために、3D シングル ビン パッキング アルゴリズムを一般化するにはどうすればよいですか?

分岐限定アルゴリズムを検討していますが、現在の最適解ではなく、分岐を切断できる条件はありますか?

十分に明確であることを願っています。

私は一種のビンパッキングの問題を調べていますが、まったく同じではありません。この問題は、総重量がビンの容量を超えないように、最小数のビンにn 個のアイテムを入れることを求めています。(古典的な定義)

違いは次のとおりです。各アイテムにはweightとboundがあり、ビンの容量はそのビン内のアイテムの最小境界によって動的に決定されます。

たとえば、4 つの項目 A[11,12]、B[1,10]、C[3,4]、D[20,22] ( [weight,bound] ) があります。ここで、アイテム A をビンに入れると、それを b1 と呼び、b1 の容量は 12 になります。次に、アイテム B を b1 に入れようとしましたが、総重量が 11+1 = 12 であり、容量がb1 は 10 になり、総重量よりも小さくなります。したがって、B はビン b2 に入れられ、その容量は 10 になります。今度は、アイテム C を b2 に入れます。総重量は 1+3 = 4 であり、b2 の容量は 4 になります。

この問題がいくつかの名前の領域で解決されたかどうかはわかりません。または、どこかで議論されているビンパッキングの変種です。これが質問を投稿するのに適切な場所であるかどうかはわかりません。助けていただければ幸いです。

「相対コストのある一次元ビンパッキング問題」をどうやって解くのか気になります。N 個のボリューム (指定されたサイズ) を M 個のビン (指定された容量) にパックし、各ビンごとに各ボリュームのコストの行列 (NxM) を取得します。したがって、総コストを最小限に抑える必要があります。

これを解決するためのアルゴリズムについてアドバイスをいただけますか? または、おそらく、これを行うためのオープンソース ライブラリはありますか?

ありがとう！

私は古典的なビン詰めの問題に似たヘッドスクラッチャーを持っていますが、それを突き止めることはできません. 助けていただければ幸いです...

問題：

すべて同じサイズの商品のセットがありますが、異なる色のバリエーションがあり、注文を構成するそれぞれの要求数量が異なります。

どのような組み合わせで梱包しても構いませんが、内容が異なる箱は規定の数までしか梱包できません。

各ボックスの異なる数量を提供できます。最適なソリューションは、要求された数量を超えて出荷される製品の数が最も少ないソリューションです。

例: 1 つの箱に 4 つの製品が収まります。内容の異なる 2 種類の箱が許可されており、100 * 赤、200 * 青、300 * 緑、400 * 黄で出荷する必要があります。

赤を 25 箱、青を 50 箱、緑を 75 箱、黄色を 100 箱詰めることはできません。これは、箱の異なる固有の内容が 2 つしか許可されていないためです。これは 4 つになります。

したがって、最適なソリューションは次のようになります。

1×赤、2×青、1×黄の100箱

2 * グリーンと 2 * イエローの 150 ボックス

この例では、すべての数量を正確に満たしているので、無駄はありません。

注文で 395 イエローのみが必要であるとします。上記の解決策は黄色を 5 個無駄にしますが、これより少ない解決策はありません。廃棄物が最も少ないソリューションが最適です。

複数のパッケージがあり、各パッケージには多数の要素が含まれているという概念的な問題があります。要素は typeAまたは typeBです。Aと の間の分布がビン間でB大きく異ならないように、有限数のビンにパッケージを配布したいと考えています。

この問題は非常に複雑なので、厳しい制約と概念的な例を使って説明しようと思います。

制約

例 (概念)

合計分布自体は 302 *Aと 191 *Bで、合計で 493 のサンプルが生成され、結果の比率は の 61.25%Aと 38.75% になります。B

望ましい結果:

各バッチには最大で 3 つのビン (長さ <= 92) が含まれ、ビンごとにタイプが 52 から 60 のA間、タイプが 32 から 40 の間B(合計が 92 を超えない) の最小化されたバッチのセット。

質問

この問題に取り組むためにどのようなアルゴリズムまたは方法が提案されるか、単純な提案されたスキームが実行されます (私がこれまで試みてきたこと (以下を参照) はそれほど遠くないことを考慮して)

これまでの試みの背景にある考え方

これは私が立ち往生している場所でもあります。これは現在、ビンの数を最小化しようとせず、比率をチェックしません。さらに、私がこれをやろうとしている方法は、そのような問題を解決するスマートな方法にはほど遠いというしつこい考えがあります。