3

郵便料金に最も便利なサイズにオブジェクトを積み重ねるという問題を解決しようとしています。オブジェクトのサイズと形状はさまざまです。すべてのオブジェクトの長さ、幅、高さがわかっています。

たとえば、顧客は (長さ x 幅 x 高さ) 200x100x10cm のオブジェクト (幅、長さ、フラット) を 2 つの 50x50x50cm のオブジェクト (立方体) と共に注文する場合があります。これを梱包する場合、フラットな幅の広いオブジェクトを下に置き、2 つのキューブを上に並べて配置します。

これに対する合理的に効率的なアルゴリズムソリューションを持っている、または知っている人はいますか? または、これを解決することを考えるべき方法へのアプローチでさえあります。私は一週間ずっとコーディングをしてきましたが、遅くて頭がおかしくなりました。私はまだ絶望的ではありませんが、明日は休みたいだけです.

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

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

何か案は？

4

4 に答える 4

5

最初のアドバイス - キーボードから離れ、コーディングをやめ、考え始めましょう!

2 番目のアドバイス - 提案されたアプローチ (最初に最大、次に最大) は、この問題に対して十分に評価され、よく使用されるヒューリスティックです。また、膨大な数のパックを行う必要がある場合や大量のパックを実行する場合を除いて、実行効率をあまり気にしなくても、開発効率がおそらく最優先事項となるはずです。

3 番目のアドバイス -- ビンパッキングについては Google ですが、注意してください。これについては膨大な量の文献があります。

最後に、これには数式があると確信しないでください :-)

于 2009-07-30T13:22:31.400 に答える
2

これは簡単な問題ではなく、NP 困難でさえあると思います。しかし、あなたはいくつかの素晴らしいアイデアを持っているようです！ナップザック問題について読んで、さらに理論と新しいアイデアを得ることをお勧めします。

于 2009-07-30T13:21:42.960 に答える
2

これは些細なことではないと思います。これの適切な名前は binpacking だと思います.Google検索は多くの学術論文を明らかにしますが、単純なアルゴリズムはありません（特に3Dで、これはあなたが望むものです）。

実際に処理しようとしているオブジェクトはいくつありますか? それが比較的少ない場合 (つまり、TEU 輸送用コンテナに数百ではなく、フェデックスの段ボール箱に数個)、ローカル マキシマ ソリューションに対する単純な力ずくのアプローチが最適なアプローチである可能性があります。

于 2009-07-30T13:22:19.123 に答える
1

私は専門家ではありませんが、ブルート フォース アプローチを使用せずに最適な結果を見つけることは現時点では不可能だと思いますが、いくつか提案することはできます。

1) 最初のコンテナに最大の容積を持つ物体を詰め始め、2 番目のコンテナに 2 番目に大きい物体を詰め始め、最初のコンテナに無限に 3 番目に大きい物体を詰めると、結果はせいぜい 14% になります (または 34% ですか?正確には思い出せません!) 最適な結果よりも最悪です。これは、ポール・ホフマンの「数字だけを愛した男」という本のどこかで読んだことがあります。

2) 遺伝的アルゴリズムは、ある程度のパフォーマンスを犠牲にして、比較的優れた結果を提供する必要があります。

Logen SolutionsやMaxLoadのように、これを生業にしている会社もあります。支払う意思がある場合は、それらの Web サービスを使用することもできます。

于 2009-07-30T13:43:10.350 に答える