0

私は次の番号を持っています6、8、9、4、3、2、10、7、14、12、6、2、3、1、10、11、13、5

これらに最適な1Dビンパッキングアルゴリズムを実装する正しい方法を知りたいです。このビデオhttp://www.youtube.com/watch?v=B2P1TzKKWOI&feature=relatedでは、彼らは私の考えとは異なる方法でそれを解決しているので、正しい答えがわかりません。

私の解決策、先着順なので、次のようになります。

  • ビン＃1：6,8,2
  • ビン＃2：9,4,3
  • ビン＃3：3,10,1
  • ビン＃4：7,6
  • ビン＃5：14,2
  • ビン＃6：12
  • ビン＃7：10
  • ビン＃8：11,5
  • ビン＃9：13

彼らの解決策、私は彼らが適切な数を一緒に「ペアリング」していると思うので、それは次のようになります：

  • ビン＃1：6,10
  • ビン＃2：9,7
  • ビン＃3：14,2
  • ビン＃4：12.4
  • ビン＃5：14,2
  • ビン＃6：13,3
  • ビン＃7：8,6,2
  • ビン＃8：10,5,1
  • ビン＃9：11,3

どちらが正しいですか？

4

1 に答える 1

3

コメントの最後にアルゴリズムを添付しました。

@AngelicCore、あなたのソリューションとビデオのソリューションの根本的な違いは、あなたのソリューションが「オンライン」ソリューションであり、ビデオのソリューションが「オフライン」ソリューションであることだと思います。

オフラインビンパッキングは、パッカーが各アイテムについて完全な情報を持っており、パッカーが望む順序でそれらを配置する時間があることを前提としています. 出荷用のステージング エリアがある倉庫を考えてみましょう。すべてのケースは、出荷の準備が整うまで、必要に応じて積み重ね、パレットに積み、再注文できます。

オンライン ビン パッキングは、多くの場合、先入れ先出し方式 (FIFO) で「オンザフライ」で行われます。入ってくるトラックからベルトコンベアにケースを受け取っていると想像してください。マテリアル ハンドリング機器は、すべてのケースを迅速に出発トラックに転送します。

その他の注意事項

ビン容量は 16 で与えられます。 (14+13+12+11+10+10+9+8+7+6+6+5+4+3+3+2+2+1)/16 = 126/ 16 ~ 7.87 => ceiling(7.87) = 8 つの最小ビンが下限です。

アルゴリズム

最適なヒューリスティック

このヒューリスティックは、アイテムが割り当てられるたびに可能な限り最大のビンを作成しようとします。ここでも、満杯でないビンはすべて開いたままになります。次の項目 j を、現在の内容が最大であるビンに配置しますが、Q − qj を超えない (したがって、項目が収まります)。どのビンにも収まらない場合は、新しいビンが開かれます。

初期化:

アイテムの重みのリスト L = {q1, q2, ..., qn} が与えられます。

item1 を bin1 に配置し、L から削除します。j=2,m=1 とします。

反復:

  1. 残りの容量が最小で qj より大きいビン i を見つけ (Si がビン i の項目である場合、Q − qk はビン i の残りの容量)、j を k∈Sii に配置します。j がどのビンにも収まらない場合は、新しいビンを開き、m + 1 の番号を付け、j をビン m + 1 に配置し、m = m + 1 とします。

  2. L からアイテム j を削除します。j = j + 1 とします。

  3. 項目が L​​ にある間、手順 1 から繰り返します。

于 2012-09-06T11:22:34.793 に答える