最も適切な箱の寸法の求め方を教えてください。

質問

最も適切な箱の寸法の求め方を教えてください。

２つの大きさの異なる直方体（又は立方体）を入れる事が可能な
もっとも小さな箱の大きさの求め方を教えてください。
また、２つではなく３つ、４つの場合はどうでしょうか？

この答えに関連する考え方やヒントだけでもOKですし、
組み合わせの数の算出方法、関連する本やHP、検索するキーワード、
ロジックを考えてくれる企業、教育機関などなど、何でも結構ですのでご教授頂きたいと思います。

宜しくお願いします。

回答No.1

kamiyasiro · ベストアンサー

専門家ではありませんが，興味を引く質問だったので回答させて下さい．

これの2次元のものは，最適倉庫問題とかいいます．
ググれば出てくると思います．

1次元の問題は，配送問題とか郵便配達人問題とか言って，
時間や距離を最小化するような問題で
LP最適化を使用します．LPとは線形計画法です．
これも配送トラックが1台2台のときは簡単に解けますが，
数十台の最適化問題になると，完全に解くにはとんでもなく時間がかかります．
そのため，内点法などのアルゴリズムが生まれています．
（有名なカーマーカー特許問題など，面白い話は一杯あります）

さて，ご質問の内容は，最適倉庫問題の3次元版ですね．
2次元を拡張すれば解けるような気がします．
ただし，やはり3個4個と増えていった時の計算時間爆発が問題ですね．

なお，解き方ですが，
条件を定式化すれば1次関数がいくつもできて，その最小値の探索問題となります．
ただ，実用化レベルのソフト（工場レイアウト・ソフトなど）では，
パターンマッチングの繰り返しの力技で解いているみたいです．

教育機関は聞いたことがありませんが，「半導体パターンレイアウト」などで
教科書があるのではないでしょうか

お礼

解答頂いた内容を元に調べた結果、
色々と分かりました。

やはり、単純なロジックはなく論文のテーマにもなる様な内容だったんですね。

大変助かりました。
有難うございました!