私は1日500以上のオーダーを持っているとしましょう。各注文は、異なる空間次元および重量を有する平均30個の製品からなる。私は、最小限の数の箱を使って製品を梱包したいと思っています。箱の拘束は重量と体積です。両方の制約は固定であり、すべてのボックスで同じです。ビンパッキング/ナップザック2d/4d
これは4dのビンパック/ナップザックの問題のように見えますが、この問題を解決できるいくつかのアルゴリズムについては読んだことがあります。この問題を解決するのに役立つpythonパッケージがありますか？また
、私は2Dで、私は体積と重量を意味し、私は2Dビンパッキングアルゴリズムによって満たされることになる3次元空間、およそあまりにも心配していないので、（とない長方形のボックスを！）。
多くの場合、事前に評価されています。
これを4Dから2Dに縮小していただきありがとうございます。 は、それが質量と体積が自然密度を経由して関連しているとしてあなたの2D問題は、1Dよりもはるか困難であるように私には明らかではない、ということで行わました。 これは、ディメンションが（マシン、時間）であるジョブショップのスケジューリングとはまったく異なります。あなたの品物の密度は異なりますが、質量は&ですが、正の相関が見られます。
ターゲット密度のヒューリスティックは、単純にbin_weight_limit/bin_volumeです。より良い見積もりは、入力セットが質量または体積によって制限されるかどうかを検討し、アイテムの混合が毎日大幅に変化しない場合は、昨日出荷した密度を使用することさえあります。私は、標準の1D欲張りのアプローチを使用することをお勧めします。これまでにパックされたアイテムがターゲットの密度を上回っている場合、「欲張り」はより密度の低いアイテムを選択することを意味し、逆も同様です。
あなたが重量順にソートされたアイテムのリストと、ボリューム順にソートされたそれらのアイテムの別のリストを格納することで、これを実装することができます。リストへのポインタを維持し、ターゲット密度の上または下にあるかどうかに従って、1つのリストまたは他のリストから選択します。例えば、いくつかの候補項目をスキップして強く不均衡な密度が「大きな」量だけ変化することを保証するなど、選択プロセスがほぼ満ちているとき、または不均衡がより大きいときに、選択プロセスをより複雑にする関数を定義する。それぞれの項目が追加されると、目標密度の上下の間でビン密度を交互に変化させようとするかもしれません。
はお返事J_Hいただきありがとうございます。私はこのソリューションが厳しいとは思えません。問題は、ターゲットの密度bin_weight_limit/bin_volumeを使用すると、密度がターゲット密度を下回っていても、ボックスの容量に制約がないため、ボックスをいっぱいにする可能性があるということです。 –
私は1Dビンパッキングアルゴリズムを使用して、最大音量を制限しました。重量に制約はありません。その後、注文ごとのビンの重量を計算し、各設定が許可されているかどうかを確認します。構成が許可されていない場合は、ビンごとの最大重量を制限する1Dビンパッキングアルゴリズムを適用します。 –