2次元パッキング問題の効率的解法 Find2D-BL の紹介

2次元パッキング問題の効率的解法 Find2D-BL の紹介 阿部晃典

箱の予測 出荷時に使用する段ボール箱の種類を事前に予測するタスク。 予測できると、 ● ● 段ボールの発注数量が事前にわかる 出庫作業時に色々な箱を試さなくて良い（作業速度UP） といったメリットがある。

箱の予測方法は2通り ● 組合せ最適化 ○ ○ ○ ● 商品の3辺、箱の3辺を与えて商品を箱に詰めるシミュレーションを実行する。 今日の話はこちら。 メリット ■ 商品の配置結果が得られる。 ■ 過去の梱包実績が不要で、商品・箱の大きさが正確にわかれば良い。 ■ 予測結果に疑義が生じた時の調査が比較的楽。 機械学習 ○ ○ 商品の組み合わせと過去の梱包実績から、傾向を学習し、箱を予測する。 メリット ■ 組合せ最適化よりは高速化しやすい（精度とのトレードオフはある） ■ 商品の柔らかさなどを考慮することもできる。

パッキング問題 (Packing problem) 商品・箱の3辺サイズが与えられ、商品を箱に効率的に詰め込むための、詰め方を計算 する問題の総称。 最適解の計算は一般に NP 困難だが、色々な近似解法がある。 今日は 3 次元パッキング問題の基礎となる、 2 次元パッキング問題の効率的な解法について紹介する。

BL 法

具体例で考える 3つの既に配置された長方形が3つあり、赤い図形を追加で配置することを考える y 箱 新規図形 (0, 0) 既配置の図形（商品） x

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

Find2D-BL Find2D-BL は BL 点を高速に探索するアルゴリズム。 BL 法は愚直な実装だと O(n4) [Imahori+ ‘18] だが、Find2D-BL なら O(n2 log n) 。 論文：Shinji Imahori, Yuyao Chien, Yuma Tanaka, and Mutsunori Yagiura. Enumerating bottom-left stable positions for rectangle placements with overlap. Journal of the Operations Research Society of Japan. Vol.57, No.1, March 2014, pp.45–61.

• https://orsj.org/wp-content/corsj/or63-12/or63_12_762.pdf
• https://www.jstage.jst.go.jp/article/jorsj/57/1/57_KJ00009350944/_article/-char/ja/

Find2D-BL

Tips: 箱の四辺を取り囲む図形に変換する 箱と既配置図形を区別するのが面倒なので、箱を取り囲むような図形に変換すること で、箱を特別扱いしないようにする。 箱を取り囲む長方形に変換 y 新規図形 (0, 0) x

NFP (No Fit Polygon) 既配置図形 Q に対し、新規図形 P を配置すると重なってしまう領域のこと。 NFP(P, Q) の外側であれば、P を配置して良い。 NFP の内側は P を配置できない NFP(P, Q) h’ h + h’ 既配置図形 Q 新規図形 P w’ w h w + w’ NFP の外側は P を配置できる

既配置図形の NFP が重複しない領域を探す NFP の重なりがない部分 が新規図形を配置できる領域となる。 この領域内で (y, x) が最小の点が BL 点になる。 この白い領域なら 新規図形を配置可能 新規図形 BL 点

走査線で BL 点を探す 走査線を徐々に y 方向に移動しながら NFP の重複がない部分を探したい。 でも、画像化してピクセル単位で探すのは時間がかかり過ぎるので、 3 つの工夫で高速化する。 ● ● ● 走査する y 座標を絞る 走査する x 座標を絞る 完全二分木で NFP の重複数を計算する BL 点 走査線 (sweep line)

高速化：走査する y 座標を絞る NFP の重複数は NFP の上下の辺でしか変化しない。 → NFP の上下辺の y 座標のみ、走査線による BL 点探索を行う。 BL 点

高速化：走査する x 座標を絞る NFP の重複数は NFP の左右の辺の位置でしか変化しない。 → NFP の左右の辺で x 方向を分割して区間 (interval) を作り、 区間ごとの NFP 重複数を計算すればよい。 1 3 2 2 3 4 3 1 区間ごとの NFP 重複数

高速化：完全二分木で NFP の重複数を計算する 完全二分木の操作は大きく分けて 2 つ。両方とも O(log n) で実行可能。 更新 走査線を y 方向に移動した時に、 各区間の NFP の重複数を更新す る。 1 3 2 1 2 23 43 1 探索 走査線上で NFP の重複数がゼロ になる区間を探す。 1 2 1 0 1 22 1 1 1 2 32 1

完全二分木の概要 ● ● 葉の数は区間の数と同じ。 ノードは p_self, p_min という 2 つの値を持つ。 ○ ○ p_self ■ 根から葉までの p_self の合計は区間の NFP 重複数に一致する。 ■ 木の更新に使う中間データで、探索には p_min だけ使う。 p_min ■ p_min = p_self + min(左の子の p_min, 右の子の p_min) で計算する。 ■ あるノードで p_min = 0 なら ● p_self = 0 かつ ● 左右のどちらかの子で p_min = 0 ■ つまり、根から p_min=0 のノードを辿っていくと、重複ゼロの区間を発見できる。

完全二分木の更新

更新の概要 走査線 A が B に移動したことを考える。走査線は常に NFP の上下辺の位置であり、こ の NFP を R とする。 走査線が R の上辺なら R の区間の重複数を -1、下辺なら +1 したい。 R 走査線 B 走査線 A 1 2 1 1 2 3 2 1 B に対応する NFP 重複数 1 3 2 2 3 4 3 1 A に対応する NFP 重複数 上辺なので -1

更新 ① 最初に、NFP R の左右辺の区間に対応する葉の p_self, p_min を -1 する。 0/1 0/1 0/1 0/1 1/1 2/2 3/3 ↓ 2/2 0/0 NFP 左辺 木のノードは p_self / p_min で表記 1/3 0/0 2/2 0/1 3/3 3/3 ↓ 2/2 NFP 右辺 1/1

更新 ② 親ノードに移動しながら、各ノードの p_min を更新していく。 p_min = p_self + min(左の子の p_min, 右の子の p_min) 0/1 0/1 0/1 0/1 1/1 2/2 3/3 ↓ 2/2 0/0 木のノードは p_self / p_min で表記 1/3 0/0 2/2 0/1 3/3 3/3 ↓ 2/2 1/1

更新 ③ NFP の左右辺に囲まれた、内側の区間の p_self, p_min も -1 する。 同様に、各ノードの p_min を更新する。 0/1 左辺側から辿ったノードに右 の子があれば、右の子の p_self を -1 する。 0/1 0/1 1/1 3/3 ↓ 2/2 右辺側から辿ったノードに左 の子があれば、左の子の 木のノードは p_self を -1 する。 p_self / p_min で表記 0/1 2/2→1/1 1/3→0/2 0/0 2/2 0/0 3/3 0/1 3/3 ↓ 2/2 1/1

更新 ④ 左右から親を辿り、同一のノードに行き着いたら、 根まで辿りながら p_min を更新していく。 0/1 0/1 0/1 1/1 3/3 ↓ 2/2 0/1 2/2→1/1 1/3→0/2 0/0 2/2 0/0 3/3 木のノードは p_self / p_min で表記 0/1 3/3 ↓ 2/2 1/1

更新の結果 p_self を足し合わせると、NFP の重複数が正しく変化していることがわかる。 木のノードは p_self / p_min で表記 0/1 0/1 走査線 B 0/1 0/1 2/2→1/1 1/3→0/2 0/1 3/3 ↓ 2/2 0/0 0/0 2/2 3/3 3/3 ↓ 2/2 3 ↓ 2 2 ↓ 1 2 ↓ 1 3 ↓ 2 4 ↓ 3 3 ↓ 2 走査線 A 1 2 1 1 2 3 2 1 B 1 3 2 2 3 4 3 1 A 1/1 1/1

完全二分木の探索

探索 探索では p_min のみを使う。 p_min = 0 なら「p_self = 0 かつ左右の子のいずれかが p_min = 0」である。 p_min = 0 のノードを辿っていけば、NFP の重複がない区間を発見できる。 0/0 0/0 0/1 0/1 1 2 1 0 1 2 2 1 1/1 0/0 2/2 1/1 0/1 0/0 1/1 0/1 2/2 2/2 1/1

まとめ

まとめ ● BL 法 ○ ○ ● 2 次元パッキング問題の近似解法 図形を BL 点に greedy に配置していく Find2D-BL ○ ○ BL 点を効率的に発見するアルゴリズム ポイント ■ NFP (No Fit Polygon) の重なりにより、図形を配置可能な領域を考える。 ■ NFP の上下左右の辺でのみ、 NFP の重複数が変わることを利用し、探索を省略する。 ■ 完全二分木により、 NFP の重複数の更新・探索を効率化する。 実装例：find2d_bl.py

• https://gist.github.com/akabe/5732e98680705c2c0782abbab49f1f8f

アルゴリズムの疑似コード

Find2D-BL アルゴリズム function Find2D_BL(既配置図形の集合, 新規図形, 箱) 1. 2. 3. 4. 5. 箱を、四辺を取り囲む図形に変換して、既配置図形に追加 既配置図形を NFP に変換 NFP を上下辺のリストと左右辺のリストに分解し、各リストをソート 左右辺のリストを区間として、完全二分木を初期化 foreach 走査線 ∈ 上下辺のリスト 5.1. 5.2. 5.3. 6. 走査線に対応する NFP に含まれる区間の NFP 重複数を更新する（完全二分木の更新） 走査線が NFP の上辺ならば、 NFP 重複数がゼロの区間を探索する（完全二分木の探索） もし、重複ゼロの区間が見つかったら、 BL 点として返す 上記で BL 点が見つからないなら「BL 点はなし」とする

完全二分木の初期化 function CreateTree(インターバルの数 N): 1. 2. 3. depth := ceil(log2 N) 深さ depth の完全二分木 T を作る T の各ノードを初期化する 3.1. 3.2. 4. 5. 左から N 番目以降の葉は p_self, p_min = 1（この領域には実際には区間が存在しないので、常 に図形配置できない区間としてマークしておく） それ以外の葉・中間ノードは p_self, p_min = 0 T の中間ノードの p_min を更新する return T

完全二分木の更新 function UpdateTree(完全二分木 T, 左辺側の葉 L, 右辺側の葉 R, 走査線) 1. 2. 3. λ := if 走査線がNFPの上辺 then -1 else +1 ノード L, R の p_self, p_min に λ を加算する L の親と R の親が同一ノードになるまで以下を繰り返す 3.1. 3.2. 3.3. 3.4. 4. L != L の親の右の子 ならば、L の親の右の子 の p_self, p_min に λ を加算する R != R の親の左の子 ならば、R の親の左の子 の p_self, p_min に λ を加算する L, R の親の p_min を更新する L := L の親, R := R の親 L の親 == R の親になったら、そのノードから根までの p_min を更新する

完全二分木の探索 function FindNoOverwrap(ノード V, 左辺側の葉 L) 1. 2. 3. 4. V の下に存在する最右の葉が L より左であれば「BL 点なし」を返す V の p_min が 0 以上なら「BL 点なし」を返す V が葉であれば、V を BL 点として返す V が中間ノードであれば、左の子→右の子の順で FindNoOverwrap を適用 ※ L には走査線に対応する NFP の左辺に対応する葉を与える。BL 点は NFP の左 辺〜右辺の範囲にしか出現しないので、それ以外を探索する必要はない。