40

私は 3 次元のビン パッキングの問題に直面しており、現在どのアルゴリズム/ヒューリスティックが最良の結果をもたらしているかについて予備的な調査を行っています。問題はNP困難であるため、すべての場合に最適な解決策が見つかるとは思っていませんが、疑問に思っていました:

1) 最適な正確なソルバーは何ですか? 分岐限定？妥当なコンピューティング リソースで解決できる問題のインスタンス サイズはどれくらいですか?
2) 最高のヒューリスティック ソルバーは何ですか?
3) いくつかの実験を行うための既製のソリューションには、どのようなものがありますか?

4

6 に答える 6

7

既製のソリューションに関しては、トラックへの積み込み用のMAXLOADPROをチェックしてください。任意の長方形のボリュームをロードするように構成できる可能性がありますが、まだ試していません。一般に、3D ビンパッキングの問題には、オブジェクトをさまざまな位置に回転させることができるという複雑さが追加されているため、特定の長さ、幅、高さを持つオブジェクトについて、各位置を表す 3 つの変数を効果的に作成する必要がありますが、使用するのは 1 つだけですソリューション。

一般に、スタンドアロンの MIP 定式化 (または分岐限定) は 2 次元または 3 次元の問題ではうまく機能しませんが、制約プログラミングは 2 次元の問題の正確な解を生成することに成功しています。このアブストラクトをご覧ください。紙を見なくても、同じサイズのビンの数を最小限に抑えようとしている問題の分解アプローチが気に入っています。3D 問題の結果はそれほど多くはありませんが、実装可能な結果が見つかったらお知らせください。

幸運を ！

于 2010-02-03T16:05:11.993 に答える
4

3 つのさまざまなアルゴリズムをテストするプログラムを作成しました。また、これは良い情報源です: A Thousand Ways to Pack the Bin - A Practical Approach to Two-Dimensional Rectangle Bin Packing。2次元の長方形ビン用ですが、いつでも3Dに変換できます。

于 2013-06-03T07:38:08.940 に答える
2

ウィキペディアから：

多くの場合、これらの単純な戦略で十分ですが、十分に大きな入力に対して、最適解の固定パーセンテージ内でビン パッキング問題を解決できる効率的な近似アルゴリズムが実証されています。

これについて彼らが提供する2つのソースは次のとおりです。

于 2010-02-03T14:35:22.283 に答える
1

最適な正確なソルバー:動的計画法を使用します。

状態変数:

  1. あなたが梱包して廃棄したアイテム。
  2. コンテナに満たされたスペース。

コンテナーが平行六面体グリッドで、項目がグリッドの正確なセルに「収まる」場合、3 次元配列を使用して状態変数 2 を表すことができます。それ以外の場合は、より複雑なデータ構造を使用する必要があります。

最高のヒューリスティック ソルバー

知らない。おそらく変数近傍検索。あなたの問題と時刻表作成の問題 (私が取り組んでいます) にはいくつかの類似点があるため、同じヒューリスティックが両方に適している可能性があります。

実験を行うための既製のソリューション

すみません、手がかりさえありません。

于 2010-04-19T15:17:56.643 に答える
0

あなたの質問は似ています： 3Dビンパッキングアルゴリズム

ただし、回転を許可しないため、かなり良い結果を得ることができます。FIRST-FIT-DECREASINGソリューションにもっと目を向けることをお勧めします。

于 2010-04-19T15:09:41.270 に答える