スタッキングアルゴリズム - 可能な限り小さな領域に3Dオブジェクトを積み重ねます

Question

私は、郵便物のための最も便利なサイズにオブジェクトを積み重ねる問題を解決しようとしています。オブジェクトのサイズと形状は変更されます。すべてのオブジェクトの長さ、幅および高さは既知である。

たとえば、顧客は、2つの50x50x50cmのオブジェクト（立方体）と一緒に（長さx幅x高さ）200x100x10cmオブジェクト（幅広、長さおよび幅）を注文することができます。もし私がこれを梱包したら、平らなワイドオブジェクトを下に、2つのキューブを横に並べて並べます。

誰にでも、これに対する合理的に効率的なアルゴリズムソリューションがありますか？あるいは、私がこれを解決することを考えなければならない方法へのアプローチさえ。私は一週間中にコーディングしています、それは遅く、私の脳は揚げられています。私はまだ必死ではないが、明日は休みを取っていたい。

3次元空間を表す配列を作成することです。各配列要素は、その空間で1平方センチメートル/ cmを表します。 3D空間の長さと幅は、最も長いオブジェクトと最も広いオブジェクトに基づいています。次に、最大のオブジェクトから最小のオブジェクトまで作業し、十分な「穴」を見つけて、あなたが行くようにそれらを埋めるだけです。

私は確信していますが、これはもっと効率的にこれを行う数学的な式です。

アイデア？

Answer 1

これは簡単な問題ではないし、NP-hardでもあると思う。あなたは良いアイデアを持っているようですね！私はKnapsack problemについて読んで、より多くの理論と新しいアイデアを得ることをお勧めします。

Answer 2

これは些細なことではありません。私はこれが適切な名前はbin packingだと信じています。Google検索では多くの学術論文が公開されていますが、単純なアルゴリズムはありません（特に3-Dの場合）。

実際に何個のオブジェクトを処理しようとしていますか？比較的少数の場合（TEU輸送コンテナに数百もなく、おそらくFedexing用の段ボール箱に少数の場合）、おそらくローカルマキシマソリューションに対する単純なブルートフォースアプローチが最良のアプローチかもしれません。

Answer 3

最初のアドバイス - キーボードから離れて、コーディングをやめ、思考を開始してください！

2番目のアドバイス - 提案されているアプローチ（最大のものから次に大きいものまで）は、この問題のヒューリスティックです。また、膨大な数のパッケージや膨大な数のパッキングがなければ、実行効率にあまり関心を持たないでください。開発効率が最優先事項になるはずです。

第3のアドバイス - ビンパッキング用のGoogleが警告されていますが、これに関する膨大な文献があります。

最後に、私は専門家ではないが、私はそれがブルートフォースを使用せずに、最適な結果を見つけることが現在可能ではないと思う。この:-)

Answer 4

ための数式があるように、特定のことはありませんしかし、私はいくつかのことを提案することができます：

1）最初のコンテナのボリュームが最大のオブジェクトと2番目のコンテナの2番目に大きいオブジェクトをパックするのは、最初のコンテナの無限結果は最大14％（またはそれは34％ですか？正確に覚えていません！）は、最適な結果よりも最悪です。私はPaul Hoffmanの著書「The Numbers Loved Only Numbers」の本のどこかでこれを読んだ。

2）遺伝的アルゴリズムを使用すると、パフォーマンスが低下しても比較的良い結果が得られます。

Logen SolutionsとMaxLoadのように、生活のためにこれを行う企業もあります。お支払いをご希望の場合は、ウェブサービスもご利用いただけます。