よくある話なのでアルゴリズムがありそうですが、見つけられずにいます。
なにかフリーソフトなどあれば教えてください。
充填する側の形状が球体か立方体であれば、最密充填は計算できます。
直方体でも計算可能ですが、自由度が高くなると計算困難になる可能性が高くなります。
まずは、最密充填を調べよう。
http://www.logi-solu.co.jp/article/14413386.html
才数(さいすう)について[基礎]
フリーソフトは見つけられなかったのですが、30日間無償でお試しができるソフトを見つけましたのでお伝えしますね。
http://www.epox-c.co.jp/qsol/vms/page_pkg_vms.html
VMS Solverお試し版
箱詰め方法のような問題は組み合わせ最適化問題と総称され、たいていはNP困難、つまり総当たりで試すしかないという性質があります。
難しい問題ですので、フリーソフトが見つからないのも仕方がないことかと。
(コンテナの登場が物流界で画期的だったのは、統一サイズの直方体なら船上で箱詰め問題を解く必要がなく機械的に並べていけるからという面もありました)
実際の解決には焼きなまし法や遺伝的アルゴリズムで近似解を求めることが多いようです。
○ダンボール箱の体積(V):入れるものの体積を(v)とすると、V/vが最大個数(=X)。箱の(縦横高さ)寸法をA,B,C 入れるものの寸法をa,b,cとすると A/a{切捨て}×B/b{切捨て}×C/c{切捨て}が最小個数(=Y) で XとYの間になる。
○実際には、箱に対象となる物を入れて、揺すった値が、一番正解に近くなる。
○箱や、入れるものの形状に因るので、万能の計算法はない。
○問題解法の定義がはっきりしないので。NP問題でもない!
段ボールの各辺の長さをaaa,bbb,ccc、体積をV、荷物の各辺の長さをaa,bb,cc、体積をVとすると、入る最大個数は高々V/V=vになります。
ここでv=s*t*uなる整数s,t,uの組を求め(つまりs,t,uはvの約数)、s*aa<aaa,t*bb<bbb,u*cc<cccを満たすのであれば、v個入ることになります。
ならないのであれば、v-1(>1)について同様に試す。これを繰り返すのが一番早いと思います。
コメント(0件)