数理解析研究所講究録
第 1981 巻 2016 年 5-26

5ラスタ表現された図形の詰込み問題に対する局所探索法
大阪大学大学院情報科学研究科情報数理学専攻村上祥平
Department of Information and Physical Sciences,
Graduate School of Information Science and Technology, Osaka University
大阪大学大学院情報科学研究科情報数理学専攻梅谷俊治
Department of Information and Physical Sciences,
Graduate School of Information Science and Technology, Osaka University
NTT データ数理システム中野雄介
NTT DATA Mathematical Systems Inc.
大阪大学大学院情報科学研究科情報数理学専攻森田浩

Department of Information and Physical Sciences,

Graduate School of Information Science and Technology, Osaka University

1

はじめに

詰込み問題とは，いくつかの図形を互いに重ならないように与えられた領域内に配置する問題である．この問題は，図形の次元や形状により様々なバリエーションを持ち，製造業や物流業などの多くの分野に応用を持つ問題である．

近年，工業上の応用事例において，様々な曲線で描かれた図形を詰込み問題で取扱う必要が生じている．図形の表現方法は，大きく分けてベクタ形式とラスタ形式の 2 種類が知られている．ベク
タ形式とは点と線分で図形を表現する方法である．この形式では図形対の重なり判定を各線分が交点を持つか否かで判定するが，曲線など複雑な形状の図形の重なり判定では，直線と曲線や曲線同士の交点の有無を判定するため，重なりを高速に判定することは容易ではない．一方で，ラスタ形式とは画像を色のついたドットと呼ばれる点集合で図形を表現する方法である．重なり判定はドット同士の重なりの有無で判定するため，曲線など複雑な形状の図形の重なり判定においても，ドット同士の重なりの有無で判定できる．

ラスタ表現された図形の詰込み問題を解くデータ構造とアルゴリズムは提案されているが，実用的な規模の例題に対して現実的な計算時間で十分な精度の解を得られていない [3, 14, 15]. 本研究

では，ラスタ表現された図形の詰込み問題に対して効率的な局所探索法を提案する．
2 節では，先行研究の手法について述べ，先行研究の課題と本研究の目的を示す．3 節では，図形の表現方法について述べる．4 節では，本研究で扱うストリップパッキング問題と部分問題の重なり度最小化問題の定式化を行う．5 節では，図形対の重なり判定に用いるミンコフスキー差について述べる．6 節では，アルゴリズムの概要について述べ，7 節では，初期解の構築方法について述べる．8 節では，重なり度最小化問題を解くために用いる局所探索法について述べ，9 節では，数値実験の結果と考察について述べる．最後に，10 節では，結論について述べる．

6
2

研究背景と目的

ストリップパッキング問題とは，布地や金属版など母材が十分な幅を持ち，必要となる母材の幅を最小化する，詰込み問題の一種である．この問題は，図形の集合と幅が固定され，長さが可変である長方形領域が与えられる．全ての図形が重ならないように長方形領域内に配置するという制約の下で，長方形領域の長さを最小化することが目的である．この問題は図形の回転に依存して 3 つのバリエーションを持つ．(1) 任意の回転角を許す，(2) 有限個の回転角を許す，(3) 回転を許さない場合が存在し，本研究では (2) の場合を扱う．この問題は繊維産業において布の使用量を最小化する事例などに応用されており，コンピュータの性能向上とアルゴリズムの高速化により，実用的な規模の例題に対して良い解が得られるようになっている．

図形の表現方法は，大きく分けてベクタ形式とラスタ形式の 2 種類が知られている．ベクタ形式とは点と線分で図形を表現する方法である．従来の研究では，図形の表現方法としてベクタ形式が用いられる場合が多く，ベンチマーク問題例に対する数値実験結果では No-Fit Polygon と呼ばれるデータ構造を使用した方法が良い結果を出している．一方で，No-Fit Polygon にはいくつかの問題点が存在する．No-Fit Polygon は穴，凹面を含む図形，ジグソー型の図形を扱う場合，縮退を引き起こすため実装の際には多くの例外処理が必要となる [5]. また，No-Fit Polygon は直線で表現された多角形を扱う場合には効率良く計算できるが，一般的な曲線で表現された図形の No-Fit
Polygon を高速で作成することは難しい．そのため，曲線で表現された図形を扱う場合には直線に近似して円弧を含む図形を扱う．曲線を多数の直線で近似すると図形が実際の形状に近づく．一方で，近似に用いる直線の数を増やせば計算時間は増加し，図形を実際の形状に近づけることと計算時間はトレードオフの関係である．そのため，ベクタ形式では曲線など複雑な形状の図形の重なりを高速に判定することは容易ではない．

ベクタ形式を用いた多角形詰込み問題に対するアルゴリズムについて紹介する．ヒューリスティックを使用した手法として，図形を領域内に 1 つずつ配置する際に，配置座標の決定を効率化するアプローチが知られている．Albano ら [1] は，すでに配置済みの図形の右端に接する配置の中で，可能な限り左側に配置する手法を提案している．また，No-Fit Polygon を利用して図形対が接する
配置を発見することで，手続きの効率化を行っている．No-Fit Polygon I は 2 つの図形対が重なりなく接するような配置の集合と定義される [2]. Blazewicz ら [6] は Albano ら [1] の手法を詰込まれた図形により形成された穴に配置できるように拡張した Bottom-Left-Fill Algorithm を提案している．Gomes ら [10] は No-Fit Polygon を用いて領域内の図形が重ならない配置の中で，可能な限り左側に配置する手法を提案している．また，局所探索法を適用することで図形の配置順を効率良く探索している．Burke ら [7] は円弧や穴を含む図形を扱えるように拡張した Bottom-Left-Fill

Algorithm を用いて，円弧や穴を含む図形を扱う手法を提案している．
他のヒューリスティックを使用した手法として，部分問題を解く手法が知られている．部分問題
として (1) 重なり度最小化問題 (2) コンパクション問題，(3) セパーション問題が知られている．重なり度最小化問題とは，与えられた幅，長さの長方形領域の中に配置するという制約の下で，図形対の重なりを最小化する問題である．コンパクシ
問題は与えられた実行可能解において，長方$\exists\sqrt[\backslash ]{}$形領域の長さが最小になるように図形を再配置する問題である．セパレーション問題は与えられた実行不可能解において，重なりを解消するのに必要な最小移動距離だけ移動させることで実行可能解を得る問題である．Bennell ら [4] はコンパクシ ンアルゴリズムとセパ $t/-$ ションアルゴリ
ズムを組み込んだタブー探索を提案している．Gomes ら [11] はコンパクションアルゴリズムとセ
パレーションアルゴリズムを組み込んだ焼きなまし法を提案している．Egebald ら [9] は重なり度$\exists$

最小化問題を解くことで多角形ストリップパッキング問題を解くヒューリスティックアルゴリズムを提案している．図形対が重なっている面積を重なり度としており，局所探索法の近傍は探索を行

7う図形の配置に対して水平方向，垂直方向に移動させて得られる配置としている．Imamichi ら [12]は，図形対の重なりを解消するのに必要な最小移動距離を重なり度として，非線形計画法の考えを組み込んだ局所探索法を繰り返すことで，重なり度最小化問題を解くアルゴリズムを提案している．Umetani ら [16] は Egeblad ら [9], Imamichi ら [12] の手法をベースとして，図形対の重なりを解消するのに必要な最小移動距離を重なり度としている．

一方，ラスタ形式とは画像を色のついたドットと呼ばれる点集合で図形を表現する方法である．
重なり判定はドット同士の重なりの有無で判定するため，曲線など複雑な形状の図形の重なり判定においても，ドット同士の重なりの有無で判定できる．これまで，ラスタ表現された図形の詰込み問題を解くデータ構造はいくつか提案されている．Olveira ら [14] は図形が配置されているピクセ
ルを 1, 配置されていないピクセルを と表現する手法を提案している．行列によりレイアウトを$0$

表現し，行列の要素値が 1 より大きければ図形が重なっていることが分かる．Segenreich ら [15] は，図形の重なりだけではなく，図形対が接触している点を発見できる手法を提案している．図形の境界上を 1, 図形の境界に囲まれた内部を 3, 図形が重なっていることを 4 以上で表現する．Babu ら[3] は，図形が配置されているピクセルを 1 以上，配置されていないピクセルを として表現する手$0$

法とは異なる手法を提案した．図形を配置する領域の境界上または境界の外側は 1 以上の値，境界
の内側は

$0$

と表現しており，最も右のピクセルを 1 として，右から左に 1 ピクセル移動することに値を 1 加えている．図形の表現方法も類似している．図形の境界の外側を 1 以上の値，境界上またと表現しており，同様に最も右のピクセルを 1 として，右から左に 1 ピクセル移
動することに値を 1 加えている．図形を配置した際には，図形の領域と図形のピクセル値が であるときのみ 1 以上の値となり，それ以外の場合は と表現することで，配置を表現している．
ラスタ形式を用いた詰込み問題に対するアルゴリズムについて紹介する．Olveira ら [14] はラス
は境界の内側を

$0$

$0$

$0$

タ表現された図形に対する焼きなまし法を提案している．Segenreich ら [15] は重なりを持つ図形に対して，水平方向に各配置の重なりの有無を確認し，重なりが無い配置を探索する方法を提案している．水平方向に探索して，重なりが無い配置が見つからなければ，現在の図形の配置から決められた長さだけ上に位置する配置に対して，水平方向に各配置の重なりの有無の確認を繰り返して，重なりが無い配置を探索する．Babu ら [3] は遺伝的アルゴリズムにより図形の配置順を探索
し，Bottom-Left Algorithm により図形の配置座標の決定を効率化した手法を提案している．
このようにラスタ形式を用いた手法は提案されているが，実用的な規模の例題に対して現実的な計算時間で十分な精度の解を得られていない．本研究では，ラスタ表現された図形の詰込み問題に対して効率的な局所探索法を提案する．本研究では，Umetani ら [16] が提案した局所探索法をベースとして，ラスタ表現された図形の詰込み問題に対して局所探索法を提案する．

3

図形の表現方法

コンピュータ上において，2 次元の図形はベクタ形式もしくはラスタ形式で表現される．ベクタ
形式は図形を点と線分で表現しており，ラスタ形式は図形をドットと呼ばれる点集合で表現する．
ベクタ形式やラスタ形式で表現された図形の呼び名は様々であるが，本研究ではベクタ形式で表現された図形をベクタ図形 (図 1), ラスタ形式で表現された図形をラスタ図形 (図 2) と呼ぶ．

従来，詰込み問題ではベクタ図形が多く用いられてきた．ベクタ図形は点と線分で表現されており，図形対の重なり判定は基本的に各線分が交点を持つか否かで判定する．そのため，曲線など複雑な形状の図形の重なり判定は，直線と曲線や曲線同士の交点の有無を判定することになるため判定が困難である．直線の重なり判定においても有限精度で線分が記述されているため，数値誤差により重なり判定を誤る場合がある．

8

図 1: ベクタ図形

図 2: ラスタ図形

一方，ラスタ図形は点集合で表現されており，図形対の重なり判定はドット同士の重なりの有無で判定する．ベクタ図形では図形の形状が複雑であるほど重なり判定が困難になるが，ラスタ図形

ではどのような図形であってもドット同士の重なりの有無で判定を行うため，曲線など複雑な形状の図形の重なり判定においても，ドット同士の重なりの有無で判定できる．また，連続値で表現された線分同士の交点を計算する必要が無く，数値誤差や縮退を回避するための例外処理を施す必要が無いという利点を持つ．しかしながら，ラスタ図形は点集合で表現されており，重なり判定にかかる計算量がドットの解像度に依存するという欠点を持つ．また，ドットの数に計算量が依存しているため，図形対の重なりの有無，重なりを解消するのに必要な移動距離を容易に得ることはできない．本研究では 4 節で述べる重なり度の計算において，図形対の重なりを解消するのに必要な移動距離を重なり度として用いる．

ラスタ図形は各ドットの色データを保持しているが，本研究では，図形を走査して有色のドットの区間の始点と終点の座標のみを保持するデータ構造を使用する [13]. 本研究ではこのデータ構造
をスキャンライン形式と呼ぶ (図 3). また，重なりを解消するのに必要な移動距離の計算を効率化するために，水平方向だけでなく垂直方向にも走査し，2 つのスキャンライン形式で表現された集合 (以下，スキャンラインの集合と呼ぶ) を作成する．

一一

ドットの集合–スキャンライン集合

図 3: 水平方向，垂直方向のスキャンラインの集合

4

定式化

4.1

ストリップパッキング問題

個の図形集合 $P=\{P_{1}, P_{2}, . . . , P_{n}\}$ が与えられるものとする．図形は許可された回転角の集合$O=\{O_{1}, O_{2}, . . . , O_{n}\}$ が与えられる． $O_{i}(1\leq i\leq n)$ は図形月が回転可能である角度の集合であ$n$る．また，幅 $W$ , 長さ の長方形領域 $C=C(W, L)$ が与えられる．ここで，$W>0$ の定数であり，が $0\in O_{i}$ 度回転していることを表す．図形は図形$L>0$ の変数である．簡略化のために，$r_{i}=(x_{i},y_{i})$
為の適当な点を参照点として，参照点の座標により図形月の配置を表現する．本研
究では，参照点を図形疏を囲む Bounding Box の中心とする．図 4 に参照点の例を示す．ただし，
図 4 の黒い点が参照点である．本研究ではラスタ図形を扱うため，各図形 の幅，長さを$L$$P_{i}(0)$$P_{i}$$P_{i}$

9$w_{i}(0)|$–$l_{i}(0)$図 4: Bounding Box による参照点の決定$w_{i}(0)= \max\{y|(x, y)\in P_{i}(0)\}-\min\{y|(x, y)\in P_{i}(0)\}$(1)$l_{i}(0)= \max\{x|(x, y)\in P_{i}(0)\}-\min\{x|(x, y)\in P_{i}(0)\}$(2)で表し，全ての回転角 $0\in O_{i}$ で $w_{i}(0)\leq W,$ $l_{i}(0)\leq L$ を満たす．また，$r_{i}=(x_{i}, y_{i})$ に配置された
図形鳥はミンコフスキー和により表される．ミンコフスキー和を式 (3) に示す．
乃 $\oplus r_{i}=\{p+r_{i}|p\in P_{i}\}$ .

(3)

このとき，ストリップパッキング問題は式 (4) のように表される．
minimize$L$subject to$(P_{i}(0_{i})\oplus r_{i})\cap(P_{j}(0_{j})\oplus r_{j})=\emptyset,$$1\leq i<j\leq n,$$(P_{i}(0_{i})\oplus r_{i})\subseteq C(W, L) , 1\leq i\leq n$(4),$o_{i}\in O_{i}, 1\leq i\leq n,$$r_{i}\in \mathbb{R}^{2}, 1\leq i\leq n$(5),$L\geq 0.$

本問題の解は $r=(r_{1}, r_{2}, \ldots, r_{n})$ と $0=(0_{1},0_{2}, \ldots, 0_{n})$ により表される．実行可能解 $(r, 0)$ が与えられた際の長方形領域 $C$ の幅 $L(r, 0)$ は，式 (6) のように表される．
$L(r, 0)= \max\{x|(x, y)\in(P_{i}(0_{i})\oplus r_{i}), 1\leq i\leq n\}$$- \min\{x|(x, y)\in(P_{i}(0_{i})\oplus r_{i}), 1\leq i\leq n\}$

図 5 にストリップパッキング問題の実行可能解の例を示す．

図 5: ストリップパッキング問題の実行可能解の例

.

(6)

10
4.2

重なり度最小化問題

重なり度最小化問題はストリップパッキング問題の部分問題として扱い，与えられた長さ の長方形領域
は点において実行可能解を発見する問題である．関数ん$\overline{L}$$C(W, \overline{L})$$(r_{i}, rj, O_{i}, Oj)$に配置された図形対$r_{i},$$rj$, $P_{j(oj)}$ の重なり度である．重なり度最小化問題の目的は全ての図$W$$(1\leq
i\leq
n)$
が幅
形乃
の長方形領域, 長さ
内に配置され，重なり度 $F(r, 0)=$$\sum_{i=1}^{n-1}\sum_{j=i1}^{n}f_{i}(rr$を最小化する解を求めることである．
,$P_{i}(0_{i})$$\overline{L}$$C(W, \overline{L})$minimize$F(r, 0)= \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}f_{ij}(r_{i}, r_{j}, 0_{i}, 0_{j})$subject to$(P_{i}(0_{i})\oplus r_{i})\subseteq C(W, \overline{L})$, $1\leq i\leq n$ ,(7)$o_{i}\in O_{i}, 1\leq i\leq n,$$r_{i}\in \mathbb{R}^{2}, 1\leq i\leq n.$

Egebald ら [9] は，図形対乃，乃が重なっている面積を重なり度んとしている．Imamichi ら $[12$ 」，
Umetani ら [16] は，重なり度んの定義に侵入度を用いている．点$rj$ に配置された重なりを持$P_{j}(oj)$$\delta(P_{i}(0_{i})\oplus
r_{i,jj}P(0)\oplus
rj)$
の侵入度
,
つ図形丑
は図形ろの重なりを解消するための最小移動距離である．侵入度は式 (8) のように表される．
$r_{i},$$(0_{i})$,$\delta(P_{i}(0_{i})\oplus r_{i}, P_{j}(0_{j})\oplus r_{j})=\min\{\Vert u\Vert|(P_{i}(0_{i})\oplus r_{i})\cap(P_{j}(0_{j})\oplus(r_{j}+u))=\emptyset, u\in \mathbb{R}^{2}\}$

ここで，$\Vert\cdot\Vert$(8)はユークリッド距離である．

本研究では，図形対乃，弓の重なりを解消するのに必要な水平方向，垂直方向の最小移動距離をにおける重なりを解消するための最小重なり度んとする．任意のある一方向$d=(d_{x}, d_{y})\in \mathbb{R}^{2}$

移動距離は式 (9) のように表される．
$\rho(P_{i}(0_{i})\oplus r_{i}, P_{j}(0_{j})\oplus r_{j}, d)=\min\{|t||(P_{i}(0_{i})\oplus r_{i})\cap(P_{j}(0_{j})\oplus(r_{j}+td))=\emptyset, t\in \mathbb{R}\}$,(9)

また，重なり度んは式 (10) のように表される．
(10)$f_{ij}(r_{i}, r_{j}, 0_{i}, 0_{j})= \min\{\rho(P_{i}(0_{i})\oplus r_{i}, P_{j}(0_{j})\oplus r_{j}, d)|d\in\{e_{x}, e_{y}\}\}$

ここで，$e_{x}=(1,0)$ , $e_{y}=(0,1)$ である．

ミンコフスキー差

5

重なり度最小化問題において重なり度んを効率良く計算するためにミンコフスキー差を用いる．ミンコフスキー差はしばしば No-Fit Polygon と呼ばれる．No-Fit Polygon は Art ら [2] によって導入された図形対の重なりを効率良く判定するためデータ構造である． に対するのミンコ
フスキー差丑 ろを定義する．図形を原点に固定し，図形ろは移動可能とする．このとき，
ろは図形対が重なりを持つような図形ろの配置全体からなる集合であり，式 (11) のように
$P_{i}$$\ominus$$P_{j}$$P_{i}$$P_{i}\ominus$

表される．

NFP $(P_{i}, P_{j})=P_{i}\ominus P_{j}=\{u-w|u\in P_{i}, w\in P_{j}\}$ .

(11)

図 6 にミンコフスキー差の例を示す．ただし，図 6 における灰色の図形がミンコフスキー差である．

11$arrow 7$$\subset\mathring{i}^{r_{i}}J^{1_{P_{i}}}$$\circ P_{i}$$\bullet$の参照点

P, の参照点
図 6: 図形$P_{i}$, ろに対するミンコフスキー差

本研究では，図形 $P_{i}(1\leq i\leq n)$ をスキャンラインの集合で表現するため，ミンコフスキー差もス
キャンラインの集合で表現される．図形 $P_{i}(1\leq i\leq n)$ は$S_{i}^{h}=\{S_{i1}^{h}, S_{i2}^{h}, .

1, 長さ

.

.

, S_{ia_{i}^{h}}^{h}\}$個の水平方向のスキャンラインの集合$a_{i}^{h}$により表現される．各水平方向のスキャンライン

$S_{ik}^{h}(1\leq k\leq a_{i}^{h})$は幅である．水平方向のスキャンラインの集合で表現されたミンコフスキー差 NF
は $a_{i}^{h}+a_{j}^{h}-1$ 個のスキャンラインの集合により表現される．同$l_{ik}^{h}$$P^{}$$S_{ij}^{h}=\{S_{ij1}^{h}, S_{ij2}^{h}, .

様に，図形 $P_{i}(1\leq i\leq n)$ は.

.

$(P_{i}, P_{j})$, S_{ij_{a_{?}^{h}+a_{j}^{h}-1}}^{h}\}$に個の垂直方向のスキャンラインの集合
より表現される．各垂直方向のスキャンライン
は幅長さ1である．垂直方向,
は $a_{i}^{v}+a_{j}^{v}-1$ 個のスキャのスキャンラインの集合で表現されたミンコフスキー差 NF
ンラインの集合
により表現される．
$a_{i}^{v}$$S_{i}^{v}=\{S_{i1}^{v}, S_{i2}^{v}, .

$S_{ik}^{v}(1\leq k\leq a_{i}^{v})$$P^{}$$S_{i_{J}’}^{v}=\{S_{ij1}^{v}, S_{ij2}^{v}, .

図形$P_{i}$

.

.

.

.

, S_{ia_{i}^{v}}^{v}\}$$w_{ik}^{v}$$(P_{i}, P_{j})$, S_{ij_{a_{i}^{v}+a_{j}^{v}-1}}^{v}\}$の参照点に対する図形弓の参照点の相対座標は $(Xj-x_{i}, yj-y_{i})$ であり，この参照点を含むミンコフスキー差 NF$P^{}$$(P_{i}, P_{j})$のスキャンライン$S_{ijk}^{h}$の始点と終点の標を$x$$b_{ijk}^{l},$$b_{ijk}^{r}$とする．このとき，水平方向の重なりを解消するための最小移動距離, または終点わ irjk までの距離の最は弓の参照点から，この参照点を含むスキャンラインの始点小値となる．水平方向の重なりを解消するための最小移動距離は式 (12) のように表される．
$\rho(P_{i}(0_{i})\oplus r_{i,jjj}P(0)\oplus r, e_{x})$$b_{ijk}^{l}$, 蘇 $-(x_{j}-x_{i}$$\rho(P_{i}(0_{i})\oplus r_{i}, P_{j}(0_{j})\oplus r_{j}, e_{x})=\min\{((x_{j}-x_{i})-b_{ijk}^{l})$

(12)

$(b$

同様に，図形乃の参照点に対する図形鳥の参照点の相対座標は $(x-x_{i},-y_{i})$ であり，この参照点を含むミンコフスキー差 NF$P^{}$$(P_{i}, P_{j})$のスキャンライン$S_{ijk}^{v}$の始点と終点のとする．このとき，垂直方向の重なりを解消するための最小移動距離

はろの参照点から，この参照点を含むスキャンラインの始点

$y$

座標を

$b_{ijk}^{u},$$b_{jik}^{d}$$\rho(P_{i}(0_{i})\oplus r_{i}, P_{j}(oj)\oplus rj, e_{y})$までの距離の最, または終点
小値となる．垂直方向の重なりを解消するための最小移動距離は式 (13) のように表される．
$b_{ijk}^{u}$$b_{\iota’jk}^{d}$$\rho(P_{i}(0_{i})\oplus r_{i}, P_{j}(0_{j})\oplus r_{j}, e_{y})=\min\{((y_{j}-y_{i})-b_{ijk}^{u}) , (b_{ijk}^{d}-(y_{j}-y_{i}$(13)

式 (12), (13) より，水平方向，垂直方向の重なりを解消するための最小移動距離を得ることができるため，式 (10) より重なり度ん $(r_{i}, roo)$ を求めることができる．図 7 にミンコフスキー差による重なり度の計算の例を示す．図 7 において，水平方向の重なりを解消するための最小移動距離は弓の参照点からこの参照点を含むスキャンラインの左端までの距離であり，垂直方向の重なりを解消するための最小移動距離は乃の参照点からこの参照点を含むスキャンラインの下端までの距離であることが分かる．

12$\circ P_{i}$$\bullet$

図 7:

6$P_{j}$の参照点$arrow$の参照点$\circ$P の参照点に対するろの参照点 rj-r, の相対座標$,$

ミンコフスキー差による図形疏，乃の重なり度$f_{ij}(r_{i}, rj , O_{i}, Oj)$の計算

アルゴリズムの概要

本研究で用いるストリップパッキング問題に対するアルゴリズムの概要について述べる．初めに初期解を 7 節で述べる方法で作成する．そして与えられた計算時間 に達するまで，下記の手順を繰り返すことで最良解を得る．
初めに，長方形領域 $C$ の長さ を縮小または拡張する．長さ の縮小または拡張はパラメータ
$T$

$L$

$L$

により決定される．現在の配置が実行可能解であれば，長方形領域 の長さを から$(1-\triangle^{dec})L$に縮小し，長方形領域 からはみ出した図形疏を領域内にランダムに再配置する．一に拡張する．
方で，現在の配置が実行可能解でなければ，長方形領域 の長さを から
ここで，図形対に重なりが存在する場合，長方形領域 の長さを に固定して，誘導局所探索法を用いて重なり度最小化問題を解き，重なりを解消する．誘導局所探索法については 8 節で述べる．
図 8 にアルゴリズムの実行例を示す．ここで，図 8 における黒色の図形は重なりを持つ図形，灰色$\triangle^{dec},$$\triangle^{inc}$

$C$

$C$

$C$

$C$

の図形は重なりを持たない図形を示す．

図 8: アルゴリズムの実行例$L$$L\vee$$(1+\triangle^{inc})L$

$L$

13
アルゴリズムの概要
入力: 図形 $P=\{P_{1}, P_{2}, . . . , P_{n}\}$ , 各図形の回転可能な回転角の集合 $O=\{O_{1}, O_{2}, . . . , O_{n}\}$ と幅$W$ の長方形領域 $C.$
出力: 図形疏 $(1\leq i\leq n)$ の配置 $r=\{r_{1}, r_{2}, . . . , r_{n}\}$ , 回転角 $0=$ ol, , . . . ,と長方形領域 $C$$\{$$0_{2}$$0_{n}\}$の長さ $L(r, 0)$ .

Stepl: 初期解 $(r, 0)$ を生成し，$L^{*}arrow L,$ $(r^{*}, 0^{*})arrow(r, 0)$ とする．
Step2: 現在の解 $(r, 0)$ が実行可能解であれば，各図形の配置を微調整する． $L<L^{*}$ を満たす場
合，$L^{*}arrow L,$ $(r^{*}, 0^{*})arrow(r_{\}}o)$ として，$Larrow(1-\triangle^{dec})L$ を行う．一方，現在の解 $(r, 0)$ が実行可能
解でなければ，$Larrow(1+\triangle^{inc})L$ とする．もし，計算時間が に達した場合，長方形領域 $C$ の長さを出力して終了する．
,解$Step3$ : 図形疏が長方形領域 $C$ の外にはみ出している場合，領域 $C$ 内にランダムに再配置する．
Step4: 現在の解 $(r, 0)$ が実行可能解でなければ，誘導局所探索法により重なり度を最小化する．
そして Step2 に戻る．
$T$

$L^{*}$$(r^{*}, 0^{*})$

初期解の構築法

7

本研究は，Next-Fit Algorithm を用いて各図形を配置し，得られた各図形の配置の微調整をする
ことで初期解を構築する．Next-Fit Algorithm は長方形詰込み問題に対する近似解法の 1 つである．長方形領域をレベルと呼ばれる $m$ 個の長方形 $y=\{V_{1} , V_{2}, . . . , V_{m}\}$ に分割し，各レベルに図形を上詰めに配置する．レベルに図形を配置する．本に図形が配置できない場合，レベル研究で Bbounding box を用いて，各図形を長方形として考えることで，Next-Fit Algorithm により各図形を配置する．初めに，図形 $P_{i}(1\leq i\leq n)$ の回転角をに固定し，各図形の長さ を降順に整列する．各図形 $P_{i}(1\leq i\leq n)$ を 1 つずつ，図形同士が接するように左上に配置する．図 9 に
Next-Fit Algorithm の実行結果の例を示す．
$V_{k}$$V_{k+1}$$0^{O}$$l_{i}$

Next-Fit Algorithm
入力: 回転角を$o\circ$に固定された図形 $P=\{P_{1}, P_{2}, . . . , P_{n}\}$ , 各図形の長さ $l_{i}(1\leq i\leq n)$ と幅 $W$ の長方形領域 $C.$
出力: 図形 $P_{i}(1\leq i\leq n)$ の初期配置 $r=\{r_{1}, r_{2}, . . . , r_{n}\}$ と長方形領域 $C$ の初期の長さ $L(r, 0)$ .

Stepl: $iarrow 1,$ $Larrow 0,$ $l^{*}arrow 0,$ $w^{sum}arrow 0$ とする．また，各図形の長さ
順列$\sigma=(\sigma_{1}, \sigma_{2}, \ldots, \sigma_{n})$$l_{i}$

を降順に整列した添字のを得る．

Step2: $w^{sum}+w_{\sigma_{i}}>W$ を満たす場合，$w^{sum}arrow 0,$ $Larrow L+l^{*},$とする．
$w^{sum}+w_{\sigma_{i}}\leq
W$を
Step3:
を満たす場合，図形$w^{sum}arroww^{sum}+w_{\sigma}i$$iarrowi+1,$に配置して，とする．もし，$i=n$ ならば終了し，$i\leq n$ ならば Step2 に戻る．
$l^{*}arrow 0$$P_{\sigma_{i}}(1\leq i\leq n)$$(x_{i}, y_{i})=(L+ \lfloor\frac{l_{\sigma_{i}}}{2}\rfloor, w^{sum}+\lfloor\frac{w_{\sigma}}{2}\rfloor)$$l^{*} arrow\max\{l^{*}, l_{\sigma_{i}}\},$

次に，Next-Fit Algorithm で得られた配置に対して，各図形の配置を微調整する．配置されている図形疏 $(1\leq i\leq n)$ をの昇順に整列して，図形 $P_{i}(1\leq i\leq n)$ を 1 つずつ整列された順に選ぶ．
$x_{i}$

選択した図形丑の左側の各配置に対して，重なり度んを計算し，重なり度ん $=0$ を満たす配置の中で，最も左側の配置に移動させる．次に，選択した図形$f_{ij}$の上側の各配置に対して，重なり度を計算し，重なり度ん $=0$ を満たす配置の中で，最も上側の配置に移動させる．この操作を図$P_{i}$

形疏 $(1\leq i\leq n)$ が移動しなくなるまで繰り返し，重なりが増加しない範囲で長方形領域 $C$ の長さを最小化する．図 10 に各図形の配置の微調整の実行結果の例を示す．

$L$

14
$V_{1} V_{2} V_{3} V_{4} V_{5} V_{\’{o}} V_{7} V_{R}$

:
:

:

:

図 9: Next-Fit Algorithm の実行結果の例

各図形の配置の微調整
入力: 回転角をに固定された図形 $P=\{P_{1}, P_{2}, . . . , P_{n}\}$ , 各図形の配置 $r=\{r_{1}, r_{2}, . . . , r_{n}\}$ と$0^{o}$

幅 $W$ , 長さ $L$ の長方形領域 $C.$

出力:図形月 $(1\leq i\leq n)$ の微調整された配置の昇順に整列した添字の順列
Stepl: 図形疏 $(1\leq i\leq n)$ を$r^{*}=\{r_{1}^{*}, r_{2}^{*}, .

$x_{i}$$iarrow 1$.

.

, r_{n}^{*}\}$と長方形領域 $C$ の長さ $L.$$\sigma=(\sigma_{1}, \sigma_{2}, .

.

.

, \sigma_{n})$を得る．また，とする．

とする．
Step2:
Step3: 図形
が，$C(W, L)$ を満たす場合，$r_{\sigma_{i}}^{*}arrow r_{\sigma_{i}}$$P_{\sigma_{i}}$$(P_{\sigma}i\oplus(r_{\sigma}i-e_{x}))\cap(P_{j}\oplus rj)=\emptyset(1\leq i\leq n, \sigma_{i}\neq j)$$r_{\sigma_{i}}arrow r_{\sigma}i-e_{x}$かつ$P_{\sigma_{i}}\oplus(r_{\sigma_{i}}-e_{x})\subseteq$とする．もし，$P_{\sigma_{i}}\oplus(r_{\sigma_{i}}-e_{x})\subseteq C(W, L)$

ならば，Step3に戻る．

Step4: 図形
が，$C(W, L)$ を満たす場合，r i$P_{\sigma_{i}}$$(P_{\sigma_{i}}\oplus(r_{\sigma_{i}}-e_{y}))\cap(P_{j}\oplus rj)=\emptyset(1\leq i\leq n, \sigma_{i}\neq j)$$\sigma$$arrow$r i–ey とする．もし，かつ$P_{\sigma_{i}}\oplus(r_{\sigma_{i}}-e_{y})\subseteq$$P_{\sigma_{i}}\oplus(r_{\sigma_{i}}-e_{y})\subseteq C(W, L)$$\sigma$

ならば，Step4 に戻る．

Step5:
を満たす場合，$iarrow i+1$ として Step2 に戻る．もし，$i>n$ ならば，$r^{*}=r$ を満たす場合は終了し，満たさない場合は Stepl に戻る．
$r_{\sigma}^{*}i=r_{\sigma}i$

図 10: 各図形の配置の微調整の実行結果の例

158

重なり度最小化問題に対する局所探索法

8.1

局所探索法の概要

局所探索法とは近傍内に改善解が存在する限り，その解に移動する操作を繰り返して，解を探索する手法である．本研究で用いる近傍と解の良否の判定条件について説明する．近傍 NB $(r, 0)$ は近傍解 $(r’, 0’)$ の集合であり，近傍解 $(r’, 0’)$ は図形 $P_{k}(0_{k})(1\leq k\leq n)$ に対して近傍探索して得られる解である．本研究では，水平方向，垂直方向を交互に探索し，図形なるまで近傍探索を繰り返す．図形$P_{k}(0_{k}’)$$P_{k}(0_{k}’)$の解が改善されなくの探索方向は $d\in\{e_{x}, e_{y}\}$ であり，式 (14) のように表

される．

(14)

$N_{0}=\{r_{k}+td|r_{k}+td\subseteq C(W, L)\}$

そのため，近傍探索では現在の配置$r_{k}$

よりも $F(r_{k}’, 0_{k}’)$ の値が小さくなる新たな配置 $r_{k}’=r_{k}+td$を探索する．

本研究では，本来の評価関数 $F(r, 0)$ の代わりに，ペナルティ重みを導入した式 (15) を用いて解$(r, 0)$を評価する．

(15)$\overline{F}(r, 0)=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}w_{ij}f_{ij}(r_{i}, r_{j}, 0_{i}, 0_{j})$ただし，$w_{ij}>0$ のペナルティ重みである．ペナルティ重みの説明および更新については 8.3 節で説の新たな配置明する．また，図形を探索するときは，式 (16) が最小化される配置を新た$P_{k}(0_{k}’)$$r_{k}’$な配置とする．

(16)$\overline{F}(r_{k}’, 0_{k}’)=\sum_{1\leq j\leq nj\neq k}w_{kj}f_{kj}(r_{k}’, r_{j}, 0_{k}’, 0_{j})$図 11 に近傍探索の例を示す．

近傍探索
入力: 図形 $P=\{P_{1}, P_{2}, . . . , P_{n}\}$ , 幅 $W$ , 長さ
出力: 図形の新たな配置
Stepl:とする．図形$te_{x}(t\in N_{0})$ を探索する．
$P_{k}(0_{k}’)$$r_{k}’arrow r_{k}$$L$の長方形領域 $C$ , 図形

$P_{k}$の新たな回転角$0_{k}’.$$r_{k}’.$$P_{k}(0_{k}’)$に対して$\overline{F}_{k}(r_{k}’+te_{x}, 0_{k}’)$$\overline{F}_{k}(r_{k}", 0_{k}’)<\overline{F}_{k}(r_{k}’, 0_{k}’)$を満たす場合，を最小化するような $r_{k}"=r_{k}’+$$r_{k}’arrow r_{k}"$とする． $darrow e_{y}$ とする．

に対してStep2: 図形
を最小化するような $r_{k}"=r_{k}’+td(t\in N_{0})$ を探索す
とする．
る．もし，
を満た
を満たす場合，す解が存在しなければ， を出力して終了する．
$Step3:d=e_{x}$ ならば，$darrow e_{y}$ として，$d=e_{y}$ ならば，$darrow e_{x}$ として，Step2 に戻る．
$\overline{F}_{k}(r_{k}’+td, 0_{k}’)$$P_{k}(0_{k}’)$$\overline{F}_{k}(r_{k}", 0_{k}’)<\overline{F}_{k}(r_{k}’, 0_{k}’)$$r_{k}’arrow r_{k}"$$\overline{F}_{k}(r_{k}", 0_{k}’)<\overline{F}_{k}(r_{k}’, 0_{k}’)$$r_{k}’$

次に局所探索法について説明する．局所探索法はいくつかの重なりを持つ図形が存在する解 $(r, 0)$に対して，近傍 NB $(r, 0)$ 内の改善解 $(r’, 0’)$ に移動させることを繰り返すことで解を改善する．近
傍 $NB(r, 0)$ 内の改善解 $(r’, 0’)$ を探索する順番はランダムに選択する．$\overline{F}(r’, 0’)<\overline{F}(r, 0)$ を満たす改善解 $(r’, 0’)\in NB(r, 0)$ を探索し，改善解が存在すれば移動する．もし，重なりが存在しないか，
近傍 NB $(r, 0)$ に改善解が存在しなければ，解 $(r, 0)$ と評価関数 $F$ が最も最小化された解 $(r^{*}, 0^{*})$
を出力する．

16

図 11: 近傍探索の例

探索する各図形 $P_{k}(0_{k}’)(0_{k}’\in O_{k})$ に対して，部分近傍 $NB_{k}(r, 0)(1\leq k\leq n)$ を定義する．近
傍 NB $(r, 0)$ は図形 $P_{k}(1\leq k\leq n)$ の部分近傍 $NB_{k}(r, 0)(1\leq k\leq n)$ の集合である．初めに，重なりを持つ全ての図形の部分近傍 NBk $(r, 0)(1\leq k\leq n)$ を作成する．ランダムな順番で部分近を
傍 $NB_{k}(r, 0)(1\leq k\leq n)$ を探索する．部分近傍 NBk $(r, 0)(1\leq k\leq n)$ に満たすような解が存在しない場合，探索を終了する．もし，部分近傍 $NB_{k}(r, 0)(1\leq k\leq n)$ 内で$\overline{F}(r’, 0’)<\overline{F}(r, 0)$$\overline{F}(r’, 0’)<\overline{F}(r, 0)$を満たすような近傍解 $(r, 0)$ が存在するならば，移動前か移動後の図形環と重なる図形 $P_{j}(j\neq k)$ の部分近傍 NBj $(r, 0)$ を探索する部分近傍に加える．アルゴリズムを以下に示す．ただし，$Q$ は探索する部分近傍 NBk $(r, 0)$ の添字 $k(1\leq k\leq n)$ の集合である．また，$(\overline{r}, \={o})$は評価関数万によって評価された局所最適解である．
局所探索法
入力: 図形 $P=\{P_{1}, P_{2}, . . . , P_{n}\}$ , 各図形の回転可能な回転角の集合 $O=\{O_{1}, O_{2}, . . . , O_{n}\}$ , 幅 $W,$の長方形領域 $C$ と解 $(r, 0)$ .
長さ.
, 評価関数 が最も最小化された解
出力: 評価関数 $F$ が最も最小化された解$L$$(r^{*}, 0^{*})$$\overline{F}$$(\overline{r}, \={o})$, $(r^{*}, 0^{*})arrow(r, 0)$ として，$Qarrow\{1, 2, . . . , n\}$ とするを出力して終了する．
を満たす場合，ランダム,を満たす場合，$Oarrow
O_{k}$に $k\in Q$ を選択し，
とする．
ランダムに
$0_{k}’\inO$に対して近傍探索を適用して，近傍解 $(r’, 0’)$
Step3:
を選択して，図形息を得る． $F(r’, 0’)<F(r^{*}, 0^{*})$ を満たす場合，$(r^{*}, 0^{*})arrow(r’, 0’)$ とする．もし，とすとして Step4 へ進む．
でないなら，
ならば，ならば，Step3 に戻る．
として，Step2 に戻る．
ならば，
る．もし，
$F(r^{*},
0^{*})=0$,を出力して，終了する． $F(r^{*}, 0^{*})\geq 0$ を満
Step4:
を満たす場合，Stepl:
Step2:$(\overline{r}, \overline{o})arrow(r, 0)$$(r^{*}, 0^{*})$$Q=\emptyset$$Q\neq\emptyset$$(\overline{r}, \={o})$$(0_{k}’)$$\overline{F}(r’, 0’)<\overline{F}(\overline{r}, \overline{o})$$(\overline{r}, \overline{o})arrow(r’, 0’)$$O=\emptyset$$\overline{F}(r’, 0’)<\overline{F}(\overline{r}, \overline{o})$$Oarrow O\backslash \{0_{k}’\}$$O\neq\emptyset$$Qarrow Q\backslash \{k\}$$(r^{*}, 0^{*})$$(\overline{r},\overline{o})$たす場合，近傍探索を行う前，近傍探索を適用した後の図形烈と重なる全ての図形ろに対して，$Qarrow Q\cup\{j\}$8.2

として，Step2 に戻る．

近傍探索の高速化

本研究では，近傍内の任意の配置で重なる可能性がない図形との重なり度の計算を省略すること
で近傍探索を高速化する．
$I_{kj}=\{t|r_{k}+td-r_{j}\in NFP(P_{j}(0_{j}), P_{k}(0_{k})\}$

(17)

17
を満たす場合，2 つの図形 $P_{j}(oj)$ ,は重なる可能性がない．ここで，図形乃のの左端と右端， 座標の上端と下端を式 (18), (19), (20), (21) に示す．

$I_{kj}=\emptyset$$P_{k}(0_{k})$

$x$

座標

$y$

$x_{i}^{\min}= \min\{x|(x, y)\in P_{i}(0_{i})\oplus r_{i}\}$(18)$x_{i}^{\max}= \max\{x|(x, y)\in P_{i}(0_{i})\oplus r_{i}\}$(19)$y_{i}^{\min}= \min\{y|(x, y)\in P_{i}(0_{i})\oplus r_{i}\}$(20)$y_{i}^{\max}= \max\{y|(x, y)\in P_{i}(0_{i})\oplus r_{i}\}$(21)

水平方向の近傍探索の場合，様に，垂直方向の近傍探索の場合，$(y_{k}^{\min}, y_{k}^{\max})\cap(y_{j}^{\min}, y_{j}^{\max})=\emptyset$を満たす．同を満たすならば，を満たを満たすならば，$I_{kj}=\emptyset$$(x_{k}^{\min}, x_{k}^{\max})\cap(x_{j}^{\min}, x_{j}^{\max})=\emptyset$$I_{kj}=\emptyset$

す．このため，重なる可能性がない図形の集合を得ることができ，重なり度の計算を省略することができる．図 12 に近傍探索の高速化の例を示す．ただし，図 12 における黒色の図形は探索する図
形，灰色の図形は重なる可能性がある図形，白色の図形は重なる可能性がない図形を示す．

図 12: 近傍探索の高速化の例

8.3

誘導局所探索法

単純な局所探索法では，しばしば精度の低い局所最適解に陥る．そのため，ペナルティ重みの適応的な調整を用いた誘導局所探索法を用いる．初めにペナルティ重みを 1.0 に初期化する．局
所最適解に陥ったとき，以下の式 (22) に従ってペナルティ重みを更新することで，局所最適解に陥った際にも，探索を再開することができる．点$rj$ に配置された図形疏とろ $(oj)$ が重なりを持つ場合，ペナルティ重みの更新は式 (22) に従う．
$w_{i_{J}}$$w_{ij}$$(0_{i})$$r_{i},$$w_{ij} arrow w_{ij}+\frac{f_{ij}(r_{i},r_{j},0_{i},0_{j})}{1\leq k<t\leq n\max f_{kl}(r_{k},r_{l},0_{k},0_{l})}$

.

(22)

18
誘導局所探索法
入力: 図形 $P=\{P_{1}, P_{2}, . . . , P_{n}\}$ , 各図形の回転可能な回転角の集合 $O=\{O_{1}, O_{2}, . . . , O_{n}\}$ , 幅 $W,$
長さ $L$ の長方形領域 $C$ と解 $(r, 0)$ .
出力: 長方形領域 $C$ の長さ $L(r^{*}, 0^{*})$ と図形 $P_{i}(1\leq i\leq n)$ の配置 $r^{*}=$$\circ^{*}=\{0_{1}^{*}, 0_{2}^{*}, .

.

.

$\{$

君

$, r_{2}^{*}, .

.

.

, r_{n}^{*}\}$, 回転角, 0_{n}^{*}\}.$

Stepl: $\max_{-}iterarrow 0,$ $w_{ij}arrow 1(1\leq i,j\leq n)$ , $(r^{*}, 0^{*})arrow(r, 0)$ とする．
Step2: 重なりを持つ図形に対して局所探索法を適用して，重なりが最小となる配置に図形を$(r,0)$
を更新する．
移動させることで，解$Step3:F(r, 0)<F(r^{*}, 0^{*})$ を満たす場合，$(r^{*}, 0^{*})arrow(r, 0)$ として，$iterarrow 0$ とする．もし，を出力して終了する．
$F(r, 0)=0$ ならば，解$Step4$ : $iterarrow iter+1$ とする．もし，$iter \geq\max$ -iter ならば，式 (22) を用いて $w_{ij}(1\leq i, j\leq n)$を更新して，Step2 に戻る．
$P_{i}$$(r^{*}, 0^{*})$

9

数値実験

本研究では，円弧や穴を含むベンチマーク問題例 [8] と多角形のベンチマーク問題例 [8, 16] を用いた．これらのベンチマーク問題例の概要を表 1, 2 に示す．ベンチマーク問題例のデータ形式はベクタ図形であるため，長方形領域 の幅 $W=512$ ピクセルとして，各図形をラスタ形式に変換
$C$

した．

表 1: 円弧や穴を含むベンチマーク問題例
問題名

Progfilesl
Progfiles2
Progfiles3
Progfiles4
Progfiles5
Progfiles6
Progfiles7
Progfiles8
Progfiles9
Progfiles10

図形の種類

図形数

回転角の増分

8
7
6
7
5
9
9
9
16
13

32
50
46
54
50
69
9
18
57

90
90
45
90
15
90
90
90
90

91

$0$

$(^{\circ}$)

本研究では提案手法の実験結果を Burke ら [8], Umetani ら [16] の結果と比較する．Burke ら [8]はベクタ図形を用いて，円弧や穴を含むベンチマーク問題例，多角形のベンチマーク問題例を扱っている．Umetani ら $[16|$ はベクタ図形を用いて，多角形のベンチマーク問題例を扱っている．また，

Umetani ら [16] の手法は従来の多角形のベンチマーク問題例の最良解をいくつか更新している．
本研究では，ペナルティ重みの更新回数 max-iter $=200$ , 領域の幅を調整するパラメータ $l^{dec}=$$0.02,$ $l^{inc}=0.005$ とする．各ベンチマーク問題例に対して提案手法を 10 回適用し，得られた解の中で最も充填率が高い結果を解とした．ただし，充填率は in 1(疏の面積)/WL としており，各実$\Sigma$$=$

行で乱数の種を変更している．また，現在の提案手法の計算効率を改善した場合に，どの程度向上
できるか確かめるために，多角形のベンチマーク問題例に対して 24 時間の実験を 1 回行った．
表 1, 2 のベンチマーク問題例に対して得られた結果と Bukre ら [8] の手法 BLF, Umetani ら [16]の手法 FITS の結果を表 3, 4 に示す．ただし，各結果は表 5, 6 に示した計算機環境，計算時間で得19
表 2: 円弧や穴を含むベンチマーク問題例
問題名

図形の種類

図形数

AlbanoDagli
DighelDighe2
Fu
Jakobsl
Jakobs2
Mao

8
10
16
10

24
30
16
10
12
25
25
20
24
43
43
99
48
64

12
25
25
9
8
4

Marques
ShapesO
Shapesl

481017

ShirtsSwim
Trousers

回転角の増分$(^{\circ}$

)

180
180
$0$

$0$

90
90
90
90
90
$0$

180
180
180
180

られた結果である．提案手法と Umetani ら [16] は 1200 秒の制限時間を設けている．Burke ら [8]は制限時間を設けていないが，他の基準を終了条件として用いており，表 5, 6 は表 3, 4 の計算結果を得るまでにかかった時間を示している．
表 3: 円弧や穴を含むベンチマーク問題例に対する実験結果

問題名

BLF
Best %$($

Progfilesl
Progfiles2
Progfiles3

Progfiles4
Progfiles5
Progfiles6
Progfiles7
Progfiles8
Progfiles9
Profiles10

提案手法
$)$

82.5
73.8
70.8
86.8

75.9
72.1
73.3
78.7
52.9
73.2

Best %
$($

$)$

842
762
72.3

84.0
81.2
78.8
95.8
829
57.5
78.0

Avg. %
$($

$)$

82.3
75.0
70.8
82.7
80.0
77.5
95.5
81.9
56.4
66.1

20
表 4: 多角形のベンチマーク問題例に対する実験結果
問題名

BLF
Best %$($

AlbanoDagli
DighelDighe2
Fu
Jakobsl
Jakobs2
Mao
Marques
ShapesO
Shapesl
Shirts

Swim
Rousers$)$

FITS 提案手法 (1200 秒)
Avg. %
Avg. %
Best %
Best %
$($

$)$

86.0
82.2
82.1

90.0
86.9
99.9

84.3
89.2
82.6
75.1
78.7

100.
91.2
89.1
80.4
85.0
89.8
66.8
73.7
87.2
74.9

86.5
65.6
71.5
82.8
67.2
86.
$9$

$0$

$\underline{89.5}$

$($

$)$

$($

$)$

$($

87.5
85.2
96.9
97.
89.5
84.5
78.2
83.9
89.0
64.9
71.6
84.2
72.6
86.

87.3
85.7
99.8

86.5
84.4
86.1
97.
87.7
83.1
77.1
82.8
88.4
64.1
69.7
83.3
71.1
85.
$2$

$3$

$\underline{100.0}$

90.3
88.7
80.3
82.8
88.8
66.2

72.6
86.1
73.0

$8$

$\underline{88.8}$

$)$

$6$

提案手法 (24 時間)

Best %
$($

87.7
86.0
97.6
97.3
90.7
86.8
79.1
84.6
89.7
65.3
71.8
85.2
73.4
87.5

表 5: 円弧や穴を含むベンチマーク問題例に対する計算機環境と計算時間 (秒)

問題名

BLF
Pentium4
2. $0GHz$

runs
Best
$10$

Progfilesl
Progfiles2
Progfiles3
Progfiles4
Progfiles5
Progfiles6
Progfiles7
Progfiles8
Progfiles9
Profiles10

15
295
283
256
300
171
211
279
98
247

提案手法

Core i7
3.1GHz$10$ runs
Time Limit

1200
1200
1200
1200
1200

1200
1200
1200
1200
1200

$)$

21
表 6: 多角形のベンチマーク問題例に対する計算機環境と計算時間 (秒)問題名BLF
Pentium4
2. $0GHz$
$10$

runs

Best

299
252

AlbanoDagli
DighelDighe2
Fu
Jakobsl
Jakobs2
Mao
Marques
ShapesO
Shapesl
Shirts

3
148
139
29
51
152
21
274
239
194
141
253

Swim
Trousers

提案手法

FITS
Core i7
3.1GHz$10$ runs

Core i7
3.1GHz$10$ runs

Time Limit

Time Limit

1200
1200
1200
1200
1200
1200
1200
1200
1200
1200
1200
1200
1200
1200

1200
1200
1200
1200
1200
1200
1200
1200
1200
1200
1200
1200
1200
1200

提案手法は Burke ら [8] の結果を数多くのベンチマーク問題例で上回った．この結果から，提案

手法は円弧や穴を含むベンチマーク問題例においては十分な性能を示すことが分かった．一方で，Umetani ら [16] の結果を全てのベンチマーク問題例で下回った．この理由について考察する．局所探索法の呼び出し回数と長方形領域 の幅 $W$ の関係について図 13 に示す．図 13 より，長方形領$C$

域 $C$ の幅 $W$ が大きくなる程，局所探索法の呼び出し回数が減少していることが分かる．これは長方形領域 $C$ の幅 $W$ が大きくなるにつれて近傍探索で重なり度を評価する配置の数が増加するためだと考えられる．

次に，局所探索法の呼び出し回数が十分か確かめるために，Umetani ら [16] の局所探索の呼び出
し回数の比較を表 7 に示す．7 より，提案手法の局所探索法の呼び出し回数が Umetani ら $[16|$ の手法と比較すると非常に少ないことが分かり，そのため充填率が低い可能性があることが考えられる．
次に，現在の局所探索法の計算効率を改善した場合に，充填率がどの程度向上できるか確かめる．
表 4 より 24 時間の実行をした場合，充填率は向上したが，Umetani ら [16] の結果には及ばないことが分かった．この結果から，現在の提案手法の高速化のみでは不十分であることが分かった．最後に，提案手法で得られた各ベンチマーク問題例に対する解を図 14, 15 に示す．

10

結論

本研究では，ラスタ図形の詰込み問題に対する局所探索法を提案した．ラスタ図形は図形対の重なり判定をドット同士の重なりの有無で判定するため，曲線など複雑な形状の図形の重なり判定においても，ドット同士の重なりの有無で判定できる．また，重なりを解消するのに必要な移動距離を効率良く計算するためにスキャンライン形式を使用した．本研究はストリップパツキング問題の22
表 7: 多角形のベンチマーク問題例に対する局所探索法の呼び出し回数

問題名

FITS 提案手法

Core i7
3.1GHzTime Limit

Core i7
3.1GHz$10$ runs
Time Limit

5930564012651035355

39754
31696
96501

19462491172243
33661328998922496181895$10$AlbanoDagli
DighelDighe2

Fu
Jakobsl
Jakobs2
Mao
Marques
ShapesO
Shapesl
ShirtsSwim
Trousers

runs

82496724823129820646301894094
76822
233491

33541
29396
76821
59821
39173
41578
9413
19022
28613

部分問題である重なり度最小化問題を繰り返し解くことでストリップパッキング問題の解を求めた．重なり度最小化問題では，長方形領域の幅と長さを固定することで，図形対の重なり度の総和を最小化した．重なり度は重なりを解消するのに必要な水平方向，垂直方向の最小移動距離としている．また，ミンコフスキー差を用いることで効率的に重なり度を計算することができた．重なり度最小化問題の解法は局所探索法を使用した．任意の図形を選択し，水平方向，垂直方向に交互に移動させることで，重なり度を最小化した．単純な局所探索法では，しばしば精度の低い局所最適解に陥るため，ペナルティ重みの適応的な更新を用いた誘導局所探索法を使用した．数値実験の結果より，円弧や穴を含むベンチマーク問題例に対して十分な性能を示すことができた．

参考文献[1] A. Albano and G. Sapuppo, Optimal allocation of two-dimensional irregular shapes using
heuristic search methods, IEEE Transactions on Systems, Man and Cybernetics, 10 (1980),

242-248.
[2] R. C Art, An approach to the two dimensional irregular cutting stock problem, Technical
Report 36. $Y08,$ $IBM$ Data Processing Division, 171 (1966).
[3] A.R. Babu and N. R. Babu, A generic approach for nesting of 2-D parts in 2-D sheets using
genetic and heuristic algorithms, Computer-Aided Design, 33 (2001), 879-891.

23

図 13: 局所探索法の呼び出し回数と長方形領域 $C$ の幅 $W$ の関係[4] J. A. Bennell and K. A. Dowsland, Hybridising tabu search with optimisation techniques for
irregular stock cutting, management Science, 47 (2001), 1160-1172.
[5] J. A. Bennell and J. F. Oliveira, The geometry of nesting problems: A tutorial, European
Journal of 0perational Research, 184 (2008), 397-415.
[6] J. Blazewicz, P. Hawryluk and R. Walkowiak, Using a tabu search approach for solving
the two-dimensional irregular cutting problem, Annals of Operations Research, 41 (1993),

313-325.
[7] E. K. Burke, R. S. R. Hellier, G. Kendall and G. Whitwell, A New bottom-left-fill heuristic algorithm for the two-dimensional irregular packing problem, Operations Research, 54(2006), 587-601.

[8] E. K. Burke, R. S. R. Hellier, G. Kendall and G. Whitwell, Irregular packing using the line
and arc no-fit polygon, 0perations Research, 171 (2010), 948-970.
[9] J. Egebald, B. K. Nielsen, and A. Odgaard, Fast neighborhood search for two-and threedimensional nesting problems, European Journal of 0perational Research, 183 (2007), 1249-

1266.
[10] A. M. Gomes and J. F. Oliveira, A2-exchange heuristic for nesting problmes, European
Journal of Operational Research, 141 (2002), 359-370.
[11] A. M. Gomes and J. F. Oliveira, Solving irregular strip packing problems by hybridisingsimulated annealing and linear programming, European Journal of 0perational Research,
171 (2006), 811-829.
[12] T. Imasmichi, M. Yagiura and H. Nagamochi An iterated local search algorithm based on
nonlinear programming for the irregular strip packing problem, Discreate 0ptimization, 6(2009), 345-361.

24[13] H. Okano, A scanline-based algorithm for the $2D$ free-form bin packing problem, Journalof 0perations Research Society of Japan, 45 (2002), 145-161.
[14] J. F. Oliveira and J. S. Ferreira, Algorithms for nesting problems, Lecture Notes in Economics and Mathematical Systems, 396 (1993), 256-273.
[15] S. A. Segenreich and L. M. Braga Optimal nesting of general plane figures: A monte carlo
heuristical approach, Computers & Graphics, 10 (1986), 229-237.

[16] S. Umetani, M. Yagiura, S. Imahori, T. Imamichi, K. Nonobe and T. Ibaraki, Solving the irregular strip packing problem via guided local search for overlap minimization, international
Transactions in Operational Research, 16 (2009), 661-683.

25

Marques

Mao

ShirtsSwim

図 14: 提案手法により得られた多角形のベンチマーク問題例に対する解26

Profiles4
図 15: 提案手法により得られた円弧や穴を含むベンチマーク問題例に対する解