【論文紹介】3次元パッキングに対する 効率的な bottom-left 法

【論文紹介】 3次元パッキングに対する 効率的な bottom-left 法 2025-01-28 阿部晃典

論文紹介 本日は以下の論文を紹介する。以前紹介した Find2D-BL を利用して 3 次元パッキング 問題を解く方法について解説している。 川島大貴, 田中勇真, 今堀慎治, 柳浦睦憲. 3 次元パッキングに対する効率的な bottom-left 法. 数理解析研究所講究録, 第 1726 巻, 2011 年, pp. 50–61. PDF ※ 純粋な論文紹介ではなく、提案手法の冗長な部分を簡略化するなど、細かい点では改変がある。

• https://www.docswell.com/s/akabe/KNRED2-Find2D-BL
• https://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1726-05.pdf

パッキング問題 (Packing problem) 商品・箱の3辺サイズが与えられ、商品を箱に効率的に詰め込む方法を計算する問題を 総称してパッキング問題 と呼ぶ。 最適解の計算は一般に NP 困難だが、色々な近似解法がある。 今回は近似解法の1つである BL 法を 3 次元に拡張した DBL 法の解法について取り扱う。

Depth Bottom Left 法

2 次元パッキング問題で考える 3つの既に配置された長方形が3つあり、赤い図形を追加で配置することを考える y 箱 新規図形 (0, 0) 既配置の図形（商品） x

BL (Bottom Left) 法と BL 点 新規図形を配置可能な点のうち、(y, x) が辞書順で最小の位置を BL 点と呼ぶ。 新規図形を BL 点に配置する方法を BL 法と呼ぶ（貪欲法）。 y 箱 新規図形 (0, 0) x BL点

DBL (Depth Bottom Left) 法と DBL 点 BL 点と同様の概念を 3 次元で定義したものが DBL法／DBL 点である。 配置可能な点のうち、(z, y, x) が辞書順で最小の位置を DBL 点と呼び、 新規図形を DBL 点に配置する方法を DBL 法と呼ぶ（貪欲法）。 z DBL 点 y x 新規図形

余談 パッキング問題では、 ● ● z 方向を奥行き (depth) y 方向を高さ (height) と設定することが多い。 ただし、この資料では z を高さ、y を奥行き と定義する。

提案手法の概要

Tips: 箱の壁6面を直方体に変換する 箱を構成する壁 6 面を薄い直方体に変換する。 箱を特別扱いせず、既配置図形と同様に考慮する。 z z 箱 x y x y

2 次元の NFP (No Fit Polygon) 既配置図形 Q に対し、新規図形 P の (x,y) が最小の点（＝左下の端点）を配置すると 重なってしまう領域を NFP (No Fit Polygon) と言う。 NFP(P, Q) の外側であれば、P を配置して良い。 (x2, y2) hQ hQ+hP 既配置図形 Q 新規図形 P wP (x1, y1) hP NFP の内側は P を配置できない wQ wQ+wP NFP(P, S) x1 = xQ - wP y1 = yQ - hP x2 = xQ + wQ y2 = yQ + hQ NFP の外側は P を配置できる

3 次元の NFP (No Fit Polygon) 既配置図形 Q に対し、新規図形 P の (x,y,z) が最小の点 を配置すると重なってしまう 領域を 3 次元の NFP とする。 NFP(P, Q) の外側であれば、P を配置して良い。 NFP(P, S) x1 = xQ - wP y1 = yQ - dP z1 = zQ - hP x2 = xQ + wQ y2 = yQ + dQ z2 = zQ + hQ wQ+wP dQ+dP hQ+hP 既配置図形 Q 新規図形 P

既配置図形の NFP が重複しない領域を探す NFP の重なりがない部分 が新規図形を配置できる領域となる。 この領域内で (z, y, x) が最小の点が DBL 点になる。 この白い領域なら 新規図形を配置可能 新規図形 DBL 点 ※ 実際は 3 次元だがわかりやすさのために2 次元で表現している。

提案手法の概要 z DBL 点 提案手法では、以下の手順で DBL 点を探す。 1. 2. 3. 4. 走査面 全ての既配置図形と新規図形の NFP を計算する。 xy 平面と平行な走査面 (sweep face) を定義する。 z=0 から走査面を徐々に上に移動する。 走査面と交差する NFP を集めて、走査面上で Find2D-BL を実行する。 Find2D-BL は O(n log n) で BL 点を見つけるので、DBL 点の探索コストは O(n2 log n) となる。n 個の図形を配置するためには O(n3 log n) の時間がかかる。

走査面に関する高速化

走査面に関する高速化 提案手法では、走査面に関連した高速化を実装している。 ● ● ● ● ① 走査する z 座標を絞る。 ② 走査面と交差する NFP の集合を逐次的に計算する。 ③ 上面・下面のソートを高速化する。 ④ Find2D-BL の対象 NFP を絞る。

① 走査する z 座標を絞る 新規図形は（箱底面を含む）既配置図形の上面にしか配置できない。 → NFP の上面で Find2D-BL を実行すれば良い。走査面も NFP 上下面を考える。 z 配置できない 配置可能 (0, 0) x, y

② 走査面と交差する NFP の集合を逐次的に計算する 以下の手順で計算すると走査面の移動 と同時に交差する NFP 集合を得られる。 1. 2. 3. NFP の集合 E を定義する（初期値は空集合）。 NFP の上面・下面を z 座標でソートして面リスト F を作る。 foreach f ∈ F 3.1. 3.2. f が下面なら、f に対応する NFP を E に追加する。 f が上面なら、f に対応する NFP を E から除去する。さらに、走査面 f 上で NFP 集合 E に対して Find2D-BL を実行する。

③ 上面・下面のソートを高速化する（着眼点） 以下の手順で計算すると走査面の移動 と同時に交差する NFP 集合を得られる。 1. 2. 3. NFP の集合 E を定義する（初期値は空集合）。 NFP の上面・下面を z 座標でソートして面リスト F を作る。 foreach f ∈ F 3.1. 3.2. f が下面なら、f に対応する NFP を E面のソートに に追加する。O(n log n) かかる。 f が上面なら、f に対応する NFP を Eこのコストは工夫すると削減できる。 から除去する。さらに、走査面 f 上で NFP 集合 E に対して Find2D-BL を実行する。 2 ※ 後続のループが O(n log n) なので、ソートを 高速化しても計算量的には変わらないが、処理速 度は若干早くなる。

③ 上面・下面のソートを高速化する（アイディア） NFP の下面の座標は新規図形 P の 3 辺サイズにより変化する。 しかし、NFP の面の上下関係は元の既配置図形に依存 する（P は無関係 ）。 Q S NFP(P, S) 既配置図形 Q, S について z 座標の Q 上面 > S 上面 > S 下面 > Q 下面 という関係性が成り立つ。 NFP についても同様の関係が成り立っている。 NFP(P, Q) P

③ 上面・下面のソートを高速化する（概要） 2 つの工夫により、DBL 点探索時におけるソートのコストを O(n) にする。 ● 既配置図形の上下面のソート済みリストを逐次的に構築する。 ○ ○ ● DBL 探索のたびにソートしない。 DBL 点が見つかったら、新規図形の上下面をリストに 挿入ソート (O(n)) することで、逐次的にソート済みリストに面を追加していく。 この面のリストはあくまで上下関係を把握するためのもの。 走査時に既配置図形の上下面の座標を NFP の上下面の座標に変換する。

③ 上面・下面のソートを高速化する（疑似コード） DBL 点の探索 探索後の処理 ※ Ft, Fb は既配置図形のソート済み上下面リスト P ← 新規図形 i, j ← 0 (x, y, z) ← DBL 点の座標（左の方法で探索） while (i, j < 既配置図形の数) Nt ← Ft[i] に対応する NFP NFP の z 座標で 上下関係を判定 Nb ← Fb[j] に対応する NFP if (Nt の上面 z 座標 < Nb の下面 z 座標) (x, y, z) と P から上下面の座標計算する。 ft ← P の上面 (z = x + hP) fb ← P の下面 (z = x) 1要素の挿入 なので O(n) E ← E \ {Nt}, i ← i + 1 E に対して Find2D-BL を実行する。 面 ft をリスト Ft に挿入ソートする。 else E ← E ∪ {Nb}, j ← j + 1 面 bt をリスト Fb に挿入ソートする。

④ Find2D-BL の対象 NFP を絞る（着眼点） DBL 点の探索 ※ Ft, Fb は既配置図形のソート済み上下面リスト 次はここを工夫する。 i, j ← 0 右図のような状態の時に... while (i, j 【Before】 < 既配置図形の数) 走査面と重複する全 NFP を考慮する。 {NFP(B), NFP(C), Nt E←=Ft[i] に対応する NFPNFP(D)} 【After】 NbA← Fb[j] に対応する の NFP の上面にある図形 NFP だけ考慮する。 E’ = {NFP(B)} if (Nt の上面 z 座標 < Nb の下面 z 座標) A の上面の 図形だけ考慮 z 今までは全範囲の 図形を考慮 B 走査面（A上面） A C D E ← E \ {Nt}, i ← i + 1 E に対して Find2D-BL を実行する。 else E ← E ∪ {Nb}, j ← j + 1 (0, 0) x, y

④ Find2D-BL の対象 NFP を絞る（疑似コード） DBL 点の探索 while (i, j < 既配置図形の数) Nt, Nb ← Ft[i], Fb[j] に対応する NFP if (Nt の上面 z 座標 < Nb の下面 z 座標) このアルゴリズムの中で Find2D-BL が一番コストが高いの で、Find2D-BL の呼び出し回数の 削減は高速化に寄与する。 E ← E \ {Nt}, i ← i + 1 E’ ← E の中で Nt 上面と重なりを持つ NFP を抽出 E’ に対して Nt 上面で Find2D-BL を実行する。 else E ← E ∪ {Nb}, j ← j + 1 ただし、オーダー表記としての計算 量は変わらない。

④ Find2D-BL の対象 NFP を絞る（注意） 上面と重複する NFP に絞ると、オーバーハングする配置ができなくなる。 DBL 法をさらに近似したような手法になることに注意が必要となる。 z このような配置はできない (0, 0) x, y

まとめ

まとめ ● DBL 法 ○ ○ ● 3 次元パッキング問題の近似解法 配置可能な点のうち (z, y, x) の辞書順で最小の点（ DBL 点）に greedy に配置する 提案手法 ○ ○ ○ Find2D-BL を使って DBL 点を効率的に発見するアルゴリズム ポイント ■ 3 次元 NFP (No Fit Polygon) の重なりで図形を配置可能な領域を考える。 ■ NFP の上下面を走査面として、走査面上で Find2D-BL を実行する。 ■ Find2D-BL の対象となる NFP を上手に絞ることで高速化を図っている。 制限：オーバーハングする配置に対応できない（少し改造すれば対応可能） 実装例：kawashima_11.py

• https://www.docswell.com/s/akabe/KNRED2-Find2D-BL
• https://gist.github.com/akabe/3cffc028e219262bfd2708a1fd92d832#file-kawashima_11-py

疑似コード

全体の処理 function solve_DBL(箱 B, 配置対象図形のリスト Ps): 既配置図形のリスト Rs ← [] 既配置図形のソート済み上面リスト Ft ← [] 既配置図形のソート済み下面リスト Fb ← [] foreach P ∈ Ps: DBL点 = find_DBL_point(P, Rs, Ft, Fb) if DBL点が見つかった: Rs.append( (DBL点, P) ) ft, fb ← DBL点と P から上下面を作成する Ft ← insert_sort(Ft, ft) Fb ← insert_sort(Fb, fb)

DBL 点の探索 function find_DBL_point(新規図形 P, 既配置図形リスト Rs, 上面リスト Ft, 下面リスト Fb): NFPs ← P と Rs から NFP を計算する i, j ← 0 while (i < 既配置図形の数 and j < 既配置図形の数): Nt ← Ft[i] に対応する NFP Nb ← Fb[j] に対応する NFP if (Nt の上面 z 座標 > Nb の下面 z 座標): E ← E ∪ {Nb}, j ← j + 1 else: E ← E \ {Nt}, i ← i + 1 BL点 ← find2D_BL_on_top_face(E, Nt) BL点が見つかった場合は (x,y,z)=(BL 点 x 座標, BL 点 y 座標, Nt 上面 z 座標) をDBL点として返す

NFP 上面での BL 点の探索 function find2d_BL_on_top_face(NFP 集合 E, 探索対象 NFP Nt): E’ ← Nt の上面と重なりのある NFP を E から抽出する Ef ← Nt の上面を 2 次元上の箱とみなして、箱の枠を直方体で表現し、そのNFP を計算する return find2d_bl(E’ ∪ Ef) # Find2D-BL を実行