カオス最適化を用いた職場レイアウト技法 A Chaos-based Optimization for Solving

(1)

カオス最適化を用いた職場レイアウト技法 A Chaos-based Optimization for Solving

Facility Layout Problem

2013 年 2 月大森峻一

Shunichi Ohmori

(2)

カオス最適化を用いた職場レイアウト技法 A Chaos-based Optimization for Solving

Facility Layout Problem

2013 年 2 月

早稲田大学大学院創造理工学研究科経営システム工学専攻

ロジスティクスエンジニアリング研究

大森峻一

Shunichi Ohmori

(3)

序論

(7)

1.1 ^研究目的

施設計画において職場レイアウト設計は限られた空間の中に所与の目的を効率的に実現しうるようにすべての配置対象の位置関係を決定する事を目的としており，生産効率に大きく影響を及ぼす重要な段階である．不十分な職場レイアウトは運搬工の増加，必要スペースの増加を生じさせ，ひいては製造原価の上昇を招きかねず，また一度設置された設備の移設には多大な費用がかかる事より，施設計画者にとって適切な職場レイアウト案を作成し理解する事は非常に重要である．

一般的なレイアウト設計の過程では，複数の代替案が作成され，その中から設計条件に最も合致していると思われるものが実行案として選択される．ところがこの代替案が作成される過程では，多様な設計要件がある事，更には短納期の要求や膨大な配置の組合せ等といった難しさがあるため設計者に多大な負担がかかっている．この問題点を解決するため，あらかじめ設計条件を十分満足している多くの良好解を選択候補として列挙する事で設計者の意思決定を十分支援に有効である．この様な設計支援を行うために，

数理的技法を用いた設計の自動化，職場レイアウト技法が広く研究されている．

これまで数多くのレイアウト技法が提案されているが，レイアウトの表現方法によって離散表現 (Discrete Representation)^{と連続表現}(Continuous Representation)^の2つに大別する事ができる.^離散表現ではグリッド状の配置領域に職場を配置する表現方法であり,コンピュータはレイアウトをマトリクスとして認識する事ができる．代表的の技法としてはHillerの入替法,CRAFT(Computerized-Relative Allocation of Facilities Technique),MULTIPLE,SABLE等が挙げられる．この様に解表現を離散的に行う事により問題はシンプルになるが,代わりに表現できないレイアウトが存在するため,^{解表現の柔軟} 性が失われてしまうという問題点がある．これに対し，連続表現では,レイアウト（職場の座標・形状）

を連続変数ベクトルにより表すため非常に柔軟な解表現が可能となり,離散表現では表現できなかったレイアウトが表現可能となる．この様な柔軟性から,近年の研究では連続表現が主流となってきている [1, 32, 45]^{．しかしながら},解表現を連続的に行う事で,求解は非常に難しくなる．

これまでに連続表現を用いたレイアウト技法としてMIP(Mixed-Integer Programming),NLP(Non- Linear Programming),MH(Meta-Heuristics)を用いた解法が提案されているが,^{連続表現を用いた難} しさゆえ, それぞれの解法に何らかの”^妥協”が含まれる事が知られている．NLP^{を用いた解法では}, 準ニュートン法等の非線形連続最適化技法を用いて求解を行うが,局所解法であるため得られる解の質が初期解に依存してしまうという問題がある (解の質に対する妥協)．MH を用いた技法では, レイアウトを文字列に変換（エンコード）する事で組合せ最適化問題として定式化し SA(Simulated Annealing),GA(Genetic Algorithm)^等のMHを適用し求解する方法である．しかしながら,^{文字列とし} て表現できないレイアウトが存在するという問題点があり,解表現が限定的になってしまう(^{解表現の自} 由度に対する妥協)．MIPを用いた解法では,職場同士の相対位置をバイナリ変数,職場の座標・形状を連続変数として定式化を行い分子限定法等を用いて求解する．しかしながら,厳密解法であるため扱える問題規模が非常に少ない(^{問題規模に対する妥協})．これまでに様々な改良が提案されてきたが,^{それらの改} 良をもってしても12職場の問題まで扱えておらず,適用範囲が非常に限定的である．

近年ではSEQUENCE(Liu and Meller[32])^やGRAPH-PAIR(Bozer Wang[33])^等，MH^とMIP^をハイブリッドで用いる方法が提案され，35職場等，大規模な問題でも十分な精度の近似解を導出する技法が提案されている．これらの技法では,相対位置関係の探索にMHを適用している．しかしながら，その探索過程においてはランダムな近傍解を生成しそれを取捨選択するという構造になっているが,職場レイアウト問題では「物流量が多い職場同士はなるべく近くに」という自明の良解条件が存在するため，ラ

(8)

第1^{章序論} 3 ンダムに探索する方法では探索過程において多くの無駄な探索を行っていると考えられ，多大な探索時間を必要とする．また,MDS(Multi Dimensional Scaling),力学的モデル,凸緩和等を応用して物流量が多い職場同士が近くに配置される様な好適な相対位置関係を探索する試みもいくつか提案されているが,^職場レイアウト問題が多峰性の構造(^非凸性)^{を有している事から},^これらはNLP^{を用いた解法同様},^局所解法となり初期解に依存してしまうという問題点がある．

本研究では，以上の問題点を解決するため，連続表現により定式化された職場レイアウト問題に対する効率的な数理的技法の開発を対象とする．本研究では,SEQUENCEやGRAPH-PAIRと同様,MIPと MHのハイブリット戦略を基本とした技法の提案を行う．本研究では,相対位置関係の探索過程において連続MHを適用する事で「物流量が多い職場同士はなるべく近くに」という良解条件を活用した好適な相対位関係を効率的に求める新たなヒューリスティクスを提案した．連続MHは最適化の分野において非凸連続最適化問題に対する解法として目覚ましい成果を挙げており,大域的な探索能力に優れるため初期解に依存する事なく,質の良い解に辿り着ける事が種々の実験から明らかにされている．従って,連続表現された職場レイアウト問題においても,この多峰性を克服する能力により質の良い解を効率的に探索できる事が期待できる．これまでに様々な連続MH^{が提案されているが},その中でも問題構造によって有効な技法が異なる事から,^{予備調査として}7^{種類の連続}MH^{を適用する事で},職場レイアウト問題に最も相性の良い技法を調べた．その結果「カオス最適化」が最も相性が良い事を明らかにした．更に相対位置決定下における職場位置・形状の最適化を高速化するため,主双対内点法を適用し問題の構造を利用したカスタマイズを加えた．数値実験では,小規模問題における最適解との比較,及び,大規模問題における他の技法により算出された近似解との比較を行い,提案技法の有効性を示した．

1.2 職場レイアウト技法について

1.2.1 職場レイアウト設計の位置づけ

レイアウト計画を広くとらえると,下記の５レベルがある．（図1も参照．）

(1) ^{物流を含む企業構想} (2) ^{敷地内建屋レイアウト} (3) ^{職場レイアウト} (4) ^{設備レイアウト} (5) 作業域のレイアウト

これらの段階は相互に影響し合っており,^{本研究の対象とする}(3)^{職場レイアウトも},^{前段階の「}(2)^敷地内建屋レイアウト」及び後段階の「(4)設備レイアウト」からの制約を受けながら意思決定がなされる必要がある．各段階のオーバーラップは図1.1^{に示されている．}

(9)

図1.1 職場レイアウト設計の位置づけ

1.2.2 職場レイアウトの設計プロセス

職場レイアウトは,施設のライフサイクルの中で常に変化する目的と同調させるために終始再計画する必要がある．この様な継続的改善を行う設計プロセスとして,^{伝統的に次の}9ステップからなるエンジニアリング・デザイン・アプローチが適用されている[1]^．

1.施設の目的の定義(再定義)．新規施設計画,既存の施設の改良計画のいずれであれ,あらかじめ量的に指定された製品あるいはサービスを産出することが基本である．そして,^{可能ならばアクティビ} ティの数（大きさ）とレベルを確認する．

2.目的を達成するために必要な基本的あるいは補助的なアクティビティの規定．目的を達成するために形成され,また要求される基本的的,副次的なアクティビティは製造,^設備,^人的資源,^物の流れという観点で規定されなければならない．副次的アクティビティの機能は,基本的なアクティビティの障害や遅れを除去する．この例として,メンテナンス機能が製造のアクティビティをサポートする事が挙げられる．

3.アクティビティ間の相互関係の決定．施設の枠の中でアクティビティがどのような相互の影響を与え，サポートするかを確定する．ここでは,定量的なもの，定性的なもの両方の相互関係を定義する必要がある．

4.アクティビティの要求スペースの確定．各々のアクティビティの必要スペースの算出には，全ての設備，材料，人的要求を考慮する必要がある．

5.^{代替案の作成．} ^ステップ1^から4までに与えられた入力情報を基に,複数の代替案を作成する．

6.^{代替案の評価．} 既に与えられた基準をもとにして代替案のランクを検討する．

7.^{代替案の選択．} ^{複数の案がある場合},組織体のゴールと目的に最も合致した計画を選択することが必要となる．この際,ステップ6でまとめられた評価の情報を活用する．

8.施設計画の実施．ひとたび代替案が選択されたならば,施設の実際の工事・建設,レイアウトを遂行

(10)

第1^{章序論} 5

図1.2 職場レイアウトの設計プロセス

しんければならない．レイアウトの監督,^{スタートアップの準備},^{実際のスタート},^運用,^問題の除去は施設計画の実施段階の一部である．

9.施設計画の保全と適応．施設に新たな要求が発生したならば,全体的な施設計画をそれにしたがって修正する必要がある．省エネルギー,運搬設備やモノの流れのパターンの変更を促し,^{新たな施設} 計画を要求する．

本研究で扱う数理的技法の位置づけは,「５．施設計画の代替案の作成」の部分に該当する．この段階では,通常複数の代替案を作成するが,あらかじめ設計条件を比較的満足していると思われる多くの良好解を選択候補として列挙する事で，設計者の意思決定を支援する事が数理的技法の目的である．

ここで,この数理的技法を適用する際に必要となる入力情報が「３．アクティビティ間の相互関係」及び「４．アクティビティの要求スペース」である．これらについては,1.2.3節にて詳述する．また,得られたアウトプットに対する「代替案の評価」「代替案の選択」の段階で重要な役割を果たすレイアウトの評価関数については,1.2.4^{節にて詳述する．}

(11)

1.2.3 職場レイアウトの入力情報

アクティビティ間の関係性

アクティビティの相互関係には,from-to chartとして表現された（量的な）物流量,^そして表1.1^に示す様な（質的な）相互関係のレイティングを用いた近接性評定値の2種類がある．それぞれに例を表1.2 に示す(これらは次節で示す通り,^{互いに変換可能である})．質的な相互関係のレイティングに関しては, 表1.1^の様に5段階評価で表されるのが一般的である．これらの評価については,^{次の様なものを考慮に} いれて判断される必要がある．

1. ^物の流れ 2. ^{情報の流れ} 3. ^{管理の容易性} 4. ^清潔性 5. 騒音の影響

表1.1 相互関係のレイティング（近接性評定値）

Value Clossness

A Absolutely Necessary E Especially Important

I Important

O Ordinary Important

U Unimportant

X Closeness Not Desirable

表1.2 From-To chartとRelationship chart

(a)From-to chart (b)Relationship chart

A B C D E F G H A B C D E F G H

A 0 45 15 25 10 5 0 0 A - I U O U U U U

B 0 0 0 30 25 15 0 0 B - U I O O U U

C 0 0 0 0 5 10 0 0 C - U U U U U

D 0 20 0 0 35 0 0 0 D - O U U U

E 0 0 0 0 0 65 35 0 E - A O U

F 0 0 0 0 0 0 0 0 F - E U

G 0 5 0 0 25 0 65 0 G - U

H 0 0 0 0 0 0 0 0 H -

(12)

第1^{章序論} 7

アクティビティの要求スペース

アクティビティの要求スペースを決定する際には,^{保管倉庫の働き},^{在庫のレベル},^保管単位,^保管方法と戦略,^{必要な設備},^{建物の構造},人的要求を考えなければならない．製造と事務の環境において,^必要なスペースはまず個々の作業場（ワークステーション）のために決定されるべきであり,^{次に部門の必要ス} ペースをワークステーションの集合として決定すべきである．

製造に必要なスペースの決定では,設備・材料・人のためのスペースを確保する必要がある．設備スペースに関しては,設備そのものの大きさに加えて,^{人の作業スペース},^{材料の投入スペース},^{廃棄物の仮} 置きスペース,治工具の保管スペース等を考慮して,必要スペースを決めなければならない．

1.2.4 レイアウトの評価関数について

多くのレイアウト技法で用いられている評価関数は(1.1)^{式で表される} ^{物流量×距離} ^{の最小化で} ある．

∑N i=1

∑N j=i+1

fijdij (1.1)

• N:職場数

• fij：職場ij 間の物流量

• dij：職場ij^間の距離

ここで,fij に関しては,from-to chartとして表現された（量的な）フローマトリクスを入力情報として用いるが, ^表1.1に示す様な（量的な）相互関係のレイティング（近接性評定値）を用いたい場合には, 強度に対応する適切な数値（例えば,A=10,E=5,I=2,O=1,U=0,X=-10）を仮定する事で変換する事が出来る．

また反対に,from-toチャートの情報を相互関係のレイティング,^即ち,5段階評価に変換する事も可能である．例えば,^表1.2^の例では,from-toチャートの物流量の最大値は90ユニットである．これをAEIOU の5^で割れば18^{になるので},^（A)90-73,(E)72-55,(I)54-37,(O)36-19,(U)18-0,^{の様に変換できる．}

これらの定量的な評価により,産出された代替案に対して,多くの修正条件や実際上の制限を考慮し,より現実的なレイアウト案を作成する事で最終的な代替案を得る．修正条件は,個々の事例ごとに異なるが, 一般的なものとしては,^{ハンドリングシステム},^貯蔵設備,^{立地や位置決め},^人的要求,^{建物の特性},^動力その他等が挙げられる．

1.2.5 数理的技法の役割

運搬をできるだけ小さく設計するという要求は，配置計画において「物流量の多いもの同士をなるべく近くに配置する」という要求に置き換えられる事ができる．しかしながら，モノの流れが多いもの同士を近くに配置する作業は，職場数が数個から十数個程度であれば試行錯誤により人手で行う事ができるが，

これが30職場あるいはそれ以上となると，とても人間が手に負える規模ではなくなってしまう．これに対しコンピュータを用いる事により設計者が到底及ばない膨大な組合せをわずかな時間で探索する事ができる．この様にして得た代替案に対して，設計者の意図を適切に反映し修正する事により設計者の生産性を著しく高める事が出来るだけでなく，最終的な解の質を著しく高める事ができる．このような理由から，1960年代以降，設計の自動化は職場レイアウト問題と呼ばれ広く研究がなされている．

(13)

1.2.6 基本レイアウトと詳細レイアウト

施設計画には建築的・構造的条件から来る多くの制約条件（例えば，柱，防火壁，階段，補強材）があり，その特殊性から第三者，即ちゼネコンにゆだねられるケースが多い．ゼネコンにおける一般的な職場レイアウト設計の過程では「基本レイアウト（Block Layout）」と「詳細レイアウト(Detailed Layout)^」という2つのレベルに分けて設計をする場合が多い．図1.3に基本レイアウトと詳細レイアウトの例を示す．基本レイアウトは職場の大まかな位置・形状を決定する段階であり,詳細レイアウトは内部の設備配置までを含んだ厳密な位置・形状，通路の構造，搬入搬出口（I/O point）を決定する段階である．前者がマクロなフローの設計を行うのに対し，後者がミクロなフローの設計を表しており，効率的な職場レイアウトを設計するためには両者を適切に行わなければならない．

本研究で対象とするのは，詳細レイアウトの目的関数値に対してきわめて大きな影響を及ぼし，数理的技法の研究も盛んな基本レイアウトの作成に焦点を当てて論じる事とする．

図1.3 基本レイアウト（左図）と詳細レイアウト（右図）

1.3 本論文の構成

本論文の構成は以下の通りである．第1章では研究目的,及び,本論文が研究の対象とする場を明らかにする．第2章ではレイアウト技法に具備すべき条件,従来の研究を纏めると同時に,^{本研究提案の連続} MH適用の必要性を述べる．第3^章では,本論で提案する技法の基本概念を示し,^{その予備調査として},^職場レイアウト問題と相性の良い連続MH^{の調査を行う．第}4^章では,本論文で提案するアルゴリズムの詳細を示す．第5^章では,提案技法の適用事例を示す事により,本研究の有効性を示す．最後に,^第6^章にて結論を述べる．

(14)

第 2 ^章

連続メタヒューリスティクスの必要性

(15)

2.1 レイアウト技法に具備すべき要件

一般的に施設計画は完全個別受注生産である事から，全ての施設に共通的な要件を見出す事は不可能である．従って職場レイアウト計画にコンピュータを援用するためには，計算機処理のためのレイアウト表現の単純化と制約条件の満足度を数値化して評価するための設計目標のモデル化が必要である．数理的技法により考慮される条件は明確な数値基準によって判断可能なものに限定されるため，設計者がここで獲得した代替案を利用するには，単に評価値が高い候補案が最終案として採用されるのではなく，設計者の意図が十分に反映された候補案が選択され修正される事を前提に考える必要がある．

この様な観点に基づき，基本レイアウトの段階において職場レイアウト技法が具備すべき要件を，文献

調査[1]-[9]，またゼネコンエンジニアリング本部へのヒアリングにより下記の様にまとめた．

1. 異面積の考慮 2. ^{配置領域の限定} 3. ^{職場矩形性の維持} 4. ^{職場形状の柔軟性}

「異面積の考慮」は,各職場の面積が異なる条件で適用可能である事を意味する(図2.1にそれぞれの職場面積が異なる20職場の職場レイアウトの例を示した)．これは自明の条件であるが,大小様々な面積の職場を扱う事で数理的技法の適用が困難になる為,^{この条件を明記した．}^（事実,初期の技法は等面積の職場のみしか扱う事が出来なかった．）

「配置領域の限定」は,特定の職場の配置をある領域内に指定できる事を意味する．（例えば,^図2.1^では,職場# 3のプレス機は,騒音のため,なるべく中央に配置する方が望まれやすい）．また,この条件の特殊なケースとして,「固定職場を扱う場合」「方角を指定する場合」も含まれる．「固定職場を扱う場合」

は,既存のレイアウトを改良する際に,ある特定の職場内の設備が非常に重い重量を持っている場合,^あるいは,技術的な理由で動かすのが非常に困難な場合に,既存の位置を全く変えない様にするための要件である．また,「方角を指定する場合」は,施設を取り巻く外部環境との整合性の理由から,^{特定の方角に面} した形で指定した職場を配置したい場合を意味する要件である（例えば,^図2.1^では,^職場# 19^の受入は, 道路側の方角に面して配置された方が望まれやすい）．

「職場形状の矩形性の維持」は,得られる最終レイアウト案の職場が矩形，あるいは，それに近い形になっている事が望ましい事を意味する．一般的に多くの施設では,職場形状は矩形であるためこの条件を加えた．稀なケースとして,^{矩形以外の形状（}L^型,^凹型,凸型等）が必要となる事もあるが,^{それらは基本} レイアウト段階で矩形として得られた案を，詳細レイアウトの段階で修正する事で対応できると考えられている．

「職場形状の柔軟性」は,職場のアスペクト比（縦横比）を指定した範囲内に収める事が出来る事を意味する．一般的に,職場内に含まれる設備形状等の制約により職場は様々な形状を取り得るため,^限りなく正方形に近い方が望ましいもの,^{長方形が望ましいもの},また特に形状に指定がないもの,^{といった職場} 特有の条件を扱える事が望ましい．

以上の様に数値的に判断可能な条件を満たした候補案を多数生成し，設計者の意図が十分に反映されたものを選択し修正する事により設計者の生産性を著しく高める事が出来るだけでなく，最終的な解の質を著しく高める事ができる．

(16)

第2章連続メタヒューリスティクスの必要性 11

図2.1 20職場のレイアウト案の例

2.2 本研究に関連する従来研究

職場レイアウトの最適化は広く研究されており,サーベイ論文も多く出されている．代表的なものとしてはLevary and Kalchik(1985)[15], Kusiak and Heragu (1987)[14], Meller and Gau (1996)[13], Drira et al.(2007)[11], Arikaran et al.(2010)[10]が挙げられる．本節では,本研究に関連する従来研究をまとめ,具備すべき要件の観点から考察を行う．

2.2.1 連続表現と離散表現

これまで数多くのレイアウト技法が提案されているが，レイアウトの表現方法によって離散表現 (Discrete Representation)^{と連続表現}(Continuous Representation)^の2つに大別する事ができる.

離散的表現では,職場はグリッド状に隔てらえれた候補点に配置され,これによりコンピュータはレイアウトをマトリックスとして扱う事ができる．そのような表現で,各々の職場の面積はもっとも近い整数値のグリッド数とされる．もしグリッドのサイズが大きすぎると小さな職場はとても少ないグリッドを持つ事になる．また,グリッドの大きさはレイアウトの全体的な解を決定する．つまり,^{小さめのグリッ} ドサイズは職場形状に柔軟性を与え,よりよい解をもたらす．しかしながら,全体の面積は決まっているので,小さ目のグリッドサイズは多数のグリッド数を結果としてもたらしてしまい,^{適切なグリッドサイ} ズの選択を計画のプロセスの初期段階で行うべきである．

代表的の技法としてはHillerの入替法,CRAFT(Computerized-Relative Allocation of Facilities Tech-

nique),MULTIPLE,SABLE等が挙げられる．この様に解表現を離散的に行う事により問題はシンプル

になるが,代わりに表現できないレイアウトが存在するため,解表現の柔軟性が失われてしまうという問題点がある．

(17)

,

に柔軟な解表現が可能となり,離散表現では表現できなかったレイアウトが表現可能となる．この様な柔軟性から,近年の研究では連続表現が主流となってきている[1, 32, 45]．これまでに連続表現を用いたレイアウト技法としてMIP,NLP,MHを用いた解法が提案されている．しかしながら,^{連続的な表現を用い} てコンピュータで処理するのはより困難となり,求解が非常に難しくなるという問題点がある．

2.2.2 具備すべき要件の観点からの従来技法のまとめ

ここでは,本研究で対象とする連続表現を用いたレイアウトにいたるまでの代表的な従来技法を具備すべき要件の観点からまとめ表2.1^に示す．

離散表現を用いた従来技法では,前述の通り解の表現が限定的になってしまうため,考慮できない要件が存在する(詳細は2.3節参照)．また,連続表現されたものの中でもMHを用いた解法では,組合せ最適化問題として扱うため連続表現されたレイアウト案を数字・文字列として変換(^離散化)^{しているため},^考慮できない要件が存在する．これに対して連続表現を直接扱うNLP,MIPによる解法では理論的にはどの様なレイアウトも表す事が可能であり,2.1節で述べた全ての要件を扱う事が可能となる(2.4.1^項参照)^．

以上より,2.1節で述べた全ての要件を考慮するためには,連続表現を用いる事が不可欠であり,^本研究においても連続表現を用いたレイアウト技法の開発を対象とする．以降より各技法の概略を2.3節および 2.4節に示す．

図2.2 離散表現（左図）と連続表現（右図）.

表2.1 具備すべき要件の観点からの従来技法のまとめ

要件

離散表現連続表現

QAP CRAFT MULTIPLE

MH MIP

Hiller MCRAFT SABLE NLP

異面積の取扱い可能 × ○ ○ ○ ○

固定職場の取扱い可能 ○ ○ ○ × ○

矩形性の維持 ○ × × ○ ○

職場形状の柔軟性 × × × × ○

(18)

2.3 ^{離散表現を用いた解法}

本節では,離散表現を用いた解法としてQAP,Hiller^の入替法,CRAFT,MCRAFT,MULTIPLE,SABLE の概要を示す．これらの技法は解表現を離散的に行う事によりコンピュータでの取扱いは容易になるが, 代わりに表現できないレイアウトが存在するため,解表現の柔軟性が失われてしまうという問題点がある．

以降に,各技法の概略と具備すべき要件の観点からの詳細な問題点について述べる．

2.3.1 QAP,Hiller の入替法

QAP(Quadratic Assginment Problem)^は,Koopmans and Beckmann (1957)[17]^{により定式化され} た問題であり,数理的技法を最初に用いた研究として知られる．この問題では全ての職場が1^×1^の等面積正方形である事を前提とし，マテリアルハンドリングコストが最小化となる職場の割当を求める問題として定式化された．この問題に対しては様々な解法が提案されているが,初期の解法として知られる

Hillerの入替法では,隣接職場の上下左右のみを入れ替える配置変更方法を用いる．この技法の特徴は入

替の有効度という概念を用いて職場の上下左右の入替で最も有効なペアーを見つけて実行する事にある．

しかしながら異面積の職場を扱う事が出来ないため適用範囲が非常に限定される．

図2.3 QAPのレイアウト表現(職場1と職場2の入替の様子)

(19)

2.3.2 CRAFT,MCRAFT

異面積の職場を扱える離散表現の技法としては，Armour and Buﬀa により提案された CRAFT(Computerized-Relative Allocation of Facilities Technique) が挙げられる．CRAFT ^では,与えられた初期レイアウトに対して,2職場の交換を行う事でより良いレイアウトを得る事を指向する技法である．交換される2^職場は,交換後の評価値の改善度合いが最も大きい職場ペアが選択され,^これらの交換を改善が見られなくなるまで行う．CRAFTは初期レイアウトを正確に反映できる点,^職場形状に柔軟性がある点といったメリットがある一方,職場の矩形性の維持が難しい点がデメリットとしてあげられる．また最適化の観点から見ても,初期解に依存する点,交換の際に職場の分断が発生しやすく探索できる実行可能解が限定されるといった弱点が報告されている．

任意の2職場間の交換を可能にできる様な改良としてMCRAFT^がある．MCRAFT^{では職場を}3^つ

の帯(band)^に分割し,上部の帯から順に．この場合も職場の矩形性の維持が困難である事,^{また形状のコ}

ントロールが非常に難しい事という同様の問題点を有している．

図2.4 CRAFTのレイアウト表現(職場5と職場6の入替の様子)

(20)

2.3.3 MULTIPLE,SABLE

MCRAFTと同様に,任意の2職場間を交換可能にする方法として，Bozer,Meller,Elbacherにより提案されたMULTIPLE,^及びSABLE^{が挙げられる．}MULTIPLE,SABLE^では,^{空間充填曲線}(SFC:Space

Filling Curve)を建屋のグリッド状に引き,^{その通った順番に},予め定められた職場順序に従って職場配置

を行う．職場配置の柔軟性を保ちつつ任意の2職場間の入れ替えを可能にする技法を提案した．しかしながら,^{職場の形状が}SFCに依存するため職場の矩形性の維持が困難であるという問題点を有している．

図2.5 MULTIPLEの入力情報(SFCと職場面積)

図2.6 MULTIPLEの配置変更（左図：職場順序1-2-3-4-5-6,右図：職場順序5-2-3-4-1-6）

(21)

2.4 ^{連続表現を用いた解法}

本節では,連続表現を用いた解法としてMIP,NLP,MHを用いた解法の概略を示す．連続表現では,^レイアウトを連続変数ベクトルにより表すため非常に柔軟な解表現が可能となり,離散表現では表現できなかったレイアウトが表現可能となる．この様な柔軟性から,近年の研究では連続表現が主流となってきて

いる[1, 32, 45]．しかしながら,連続的な表現を用いてコンピュータで処理するのはより困難となり,求解

が非常に難しくなるという問題点がある．以降に,各技法の概略と問題点について述べる．

2.4.1 連続表現を用いた定式化

N ^個の職場1,· · · , N ^{を考える．職場}i= 1, ..., N ^に対して,^{それぞれの中心座標を}(xi, yi)∈R²,^横幅と縦幅の半分の長さを(wi, hi)∈R²^とする. ^{これらの職場は},^{左下のコーナーを原点}(0, 0)^とし,^横幅と縦幅をW, Hとする建屋領域内に配置されなければならない (^図2.7^参照).尚，以降に紹介するモデルによっては，(wi, hi)を職場の縦幅・横幅の全部の長さとして扱うものもあるため注意されたい．

目的関数

目的関数は1.2.4^{節でも述べた通り},^物流量fij と距離dij の積の総和で表される総物流コストの最小化である．

minimize

∑N i=1

∑N j=i+1

fijdij (2.1)

距離dijの測り方は技法により異なるが,通常は下記のうちのいずれかが用いられる．

• ^{ユークリッド距離：}dij =√

(xi−xj)²+ (yi−yj)²

• ^{ユークリッド距離の}2^乗：dij = (xi−xj)²+ (yi−yj)²

• ^{マンハッタン距離：}dij =|xi−xj|+|yi−yj|

2番目のユークリッド距離の2^乗は,微分の際に便利な形であるため用いられる事がある．また,^上記の距離のどれを用いた場合も,得られる最終レイアウトは似通ったものになる事が実験的に報告されている．

図2.7 連続表現された職場レイアウト.

(22)

建屋内制約

建屋内制約は,すべての職場が建屋領域内に配置されなければならない事を要求する制約であり,^下記の式で表される．

wi≤xi≤W −wi, i= 1· · ·N. (2.2) hi≤yi≤H−hi, i= 1· · ·N. (2.3)

アスペクト比制約

アスペクト比制約は,各職場のアスペクト比が指定された上下内に収まっていなければならない事を示している．

li≤hi/wi≤ui, i= 1· · ·N, (2.4) 但し,^{アスペクト比は}hi/wi^で示され,その上限値と下限値はそれぞれui, liで示される．両辺にwiを乗じる事により,この式は線形式として表現できる:

liwi≤hi≤uiwi, i= 1· · ·N, (2.5) 職場形状が固定の場合は,li=uiとして設定すれ事で線形等式制約として扱う事が出来る.^{この様な問} 題は設備レイアウト問題(MLP:Machine Layout Problem)^{と呼ばれる事もある．}

面積制約

職場i= 1, ..., N に対して,siを職場iの必要スペースとすると, 各職場は以下の関係を満たしていなければならない:

4wihi≥si, i= 1· · ·N. (2.6)

非重複制約

非重複制約は,相異なる職場i, jに対して,職場同士に重複部分が発生しない事を要求している．ここで,非重複制約は技法毎に定式化の方法が異なるため,ここでは職場iの占める領域をDiとし,下記の様な形で示す．

Di∩Dj =∅, i, j= 1· · ·N. (2.7)

(23)

基本となる定式化

以上の目的関数,及び制約条件を纏めると下記の様に定式化する事ができる．

minimize

∑N i=1

∑N j=i+1

fij(d^x_ij+d^y_ij) (2.8) subject to wi≤xi≤W −wi (2.9)

hi≤yi≤H−hi (2.10)

liwi≤hi≤uiwi (2.11)

4wihi≥si (2.12)

Di∩Dj =∅ (2.13)

• N : 職場数;

• i, j : ^職場番号(i, j = 1· · ·N);

• fij : ^職場 ij ^{間の物流量};

• W, H : ^{建屋の横幅・縦幅};

• li, ui : 職場iのアスペクト比の上下限;

• si : 職場iの面積;

• xi, yi : ^職場i^のx, y^座標;

• wi, hi : ^職場iの横幅・縦幅の半分の長さ;

決定変数は(xi, yi, wi, hi)^であり,これらは全て連続変数で記述されているため,^{理論的には全てのレイ} アウトを表現する事が可能である．これらの表現を用いて,前述したレイアウト技法に具備すべき要件の記述がどの様に行われるかを次節に示す．また,これらの解法に関しては2.4.2-2.4.5節に詳述する．

具備すべき要件の記述

連続表現を用いた場合に,前述のレイアウト技法に具備すべき要件がどの様に表現されるかを以下に示す．

• 異面積の考慮：入力情報として職場面積siに任意の値を規定する事ができるため対応可能である．

• 配置領域の指定：ある職場iの配置領域を[W_i^min, W_i^max]の範囲に指定したい場合には,建屋制約同様,下記の制約を課す事で対応可能である．

W_i^min+wi≤xi≤W_i^max−wi, i= 1· · ·N. (2.14) H_i^min+hi≤yi≤H_i^max−hi, i= 1· · ·N. (2.15) また,職場位置・形状を(x⁰_i, y⁰_i)に固定する場合は,ある職場iの座標を(xi, yi) = (x⁰_i, y⁰_i)の様に直接指定する事が可能である．これは,上記の制約でW_i^max =x⁰_i +wi, W_i^min =x⁰_i −wiとした場合と等価な条件である(y^{方向についても同様})^．さらに,一部の方角に面した職場を指定したい場合は,^{例えば東側を考えると}x⁰_i +wi=W という制約条件を不可すればよい．これは,^上記の制約でW_i^max =W, W_i^min =W −2wiとした場合と等価な条件である(他の方角についても同様)^．

• 職場の矩形性の維持：全ての職場形状を矩形に限定しているため,対応可能である．

• 職場形状の柔軟性：アスペクト比制約で対応可能．職場形状が完全に固定の場合はアスペクト比の上下限をli=uiと設定する事で,線形等式制約として表現可能である．

(24)

2.4.2 NLP を用いた解法

NLPを用いた解法では,準ニュートン法等の非線形連続最適化技法を用いて求解を行うが,局所解法であるため得られる解の質が初期解に依存してしまうという問題がある(^{解の質に対する妥協})^．そこで,^可能な限り“^{良い初期解}”を得る事で解の質を改善する事を狙ったものが主流となっている．

NLT(Non-Linear Techinique) [46]

NLPを用いて初めて定式化を行ったのが,van campのNLTである．NLTでは3-Stagesのモデルとなっている．1-Stageでは,職場を円状に等間隔に分布させる．2-Stageでは,職場を円で近似した緩和問題を解いて概ねの位置を決める．3-Stage^では,職場を矩形として扱った厳密なモデルを解く．ここで,1-Stage^の結果は2-Stage^の初期解,2-Stage^の結果は3-Stageの初期解となっている．2-Stage^及び

3-Stage^{の問題に関しては},制約式をペナルティ関数を用いて目的関数にキャストし,^{それを準ニュートン}

法で求解している．

NLTの定式化は下記に示す通りである．

minimize

∑N i=1

∑N j=i+1

fij(d^x_ij+d^y_ij) (2.16)

subject to wi≤xi≤W −wi (2.17)

4wihi≥si (2.20)

|xi−xj| −(wi+wj)≥0, if |yi−yj| −(hi+hj)<0 (2.21)

|yi−yj| −(hi+hj)≥0, if |xi−xj| −(wi+wj)<0 (2.22)

制約式(2.21)(2.22)^は,非重複制約を表している．これは水平方向,あるいは垂直方向のいずれかの方向

に対し,職場同士の距離が職場の幅の合計の半分よりも大きい事を要求している制約である．この様な選言的な制約式により,職場の重複を防ぐ事が出来る．

NLTでは,制約違反に対するペナルティ関数を定義する事で,制約式の考慮を行っている．しかしなが

ら,制約式(2.21)(2.22)をペナルティ関数として目的関数に加えた場合,得られる関数が非連続かつ微分

不可能な形となる．そこで,NLTでは下記の様なペナルティ関数値を設定する事で,^{この問題を解消して} いる．

Pij =

{ µkφ[|xi−xj| −(wi+wj)]², if |yi−yj| −(hi+hj)<0

µkφ[|yi−yj| −(hi+hj)]², if |xi−xj| −(wi+wj)<0 (2.23) 但し,µkはk個目の制約式に対する重みづけパラメータ,φはペナルティ関数（制約違反の時のみ正）である．しかしながら,目的関数とペナルティ関数の合成関数が非凸関数となるため,関数形が多峰性を持つため得られる解の質が初期解に依存する事がわかっている．

(25)

AR-BPL model [23]

NLT の改良として提案されたのが,Anjos^の AR-BPL model ^{である．このモデルは} 2-stages^のモデルとなっており,1-Stage ^の AR(Attractor-Repeller) model^{では緩和問題を解き} “^{良い初期解}”^を求め,2-Stage^のBPL(Bilinear Penalty Layout) model^では,厳密なモデルを解いて最終レイアウトを得る．

1-StageのARモデルでは,非重複制約の代わりに“ターゲット距離”と呼ばれる考え方を用いて問題を

緩和している．これは,相異なる職場i, jに対して,ターゲットとなる距離Tijを設定し,職場間の距離がターゲット距離よりも大きい場合(Tij < dij)^には,^{小さすぎたり}(Tij < dij)した場合にはペナルティを課すという方法である．ARモデルの定式化は下記の通りである．

minimize

∑N i=1

∑N j=i+1

[

fijdij+ (Tij

dij −1) ]

(2.24) subject to wi≤xi≤W −wi (2.25)

4wihi≥si (2.28)

目的関数の第2項はターゲット距離からの乖離に対するペナルティを表しており,Tij =dij の時にペナルティが0となる.この様な項を加える事により,職場同士をターゲット距離まで“ある程度”離す事ができ, 非重複制約を間接的に考慮する事ができる．厳密な制約条件の考慮は2-StageのBPL modelで行う．

2-Sgate^のBPL^{モデルでは},厳密な非重複制約を扱っており,下記の様な形で定式化されている．

minimize

∑N i=1

∑N j=i+1

fij[(xi−xj)²+ (yi−yj)²] (2.29)

subject to wi≤xi≤W −wi (2.30)

4wihi≥si (2.33)

XijYij = 0 (2.34)

Xij ≥(wi+wj)− |xi−xj|, Xij ≥0 (2.35) Yij ≥(hi+hj)− |yi−yj|, Yij ≥0 (2.36) 非重複制約は式(2.34)(2.35)(2.36)の様に定式化されている．ここで,制約(2.35)(2.36)は下記の式を線形化したものである．

Xij =max((wi+wj)− |xi−xj|,0) (2.37) Yij =max((hi+hj)− |yi−yj|,0) (2.38) 即ち,Xij, Yij はそれぞれx, y方向への職場の重なりを表している．これらの式を用いる事により,(2.34) より,Xij, Yijのいずれかが0^となれば(^即ち,x, yのいずれかの方向に職場同士が離れていれば),^重複が起きない事を表していると解釈できる．

ARモデルでは,NLTに比べて物流量が多い職場同士が近づきやすくなるが,扱っている解法が局所解法であるため,初期解への依存性は克服されたとは言い難い．この方法の改良として,[24, 25]等が提案されているが,全て同様の問題点を有している．

(26)

2.4.3 MH を用いた解法

MHを用いた技法では,レイアウトを文字列に変換（エンコード）する事で組合せ最適化問題として定式化しSA(Simulated Annealing),GA(Genetic Algorithm)^等のMHを適用し求解する方法である．しかしながら,文字列として表現できないレイアウトが存在するという問題点があり,^{解表現が限定的になっ} てしまう(解表現の自由度に対する妥協)^．

LOGIC(Layout Optimization with Gulitine Cut)

LOGICでは,建屋を分割する事でレイアウトを得る技法である．職場を表すオペランド,及び分割操作

を表すオペレータの2種類の文字列により表される．この表現方法はSlicing Tree^{と呼ばれる．分割操} 作は水平の分割R(Right)及び垂直方向の分割操作U(Upper)の２つがある．この分割操作を再帰的に行う事で最終レイアウトを得る．職場の配置変更は,Slicing Treeの一部を変化させる事で行う．通常,^この配置変更と解の取捨選択はMHを用いて行われる．

図2.8に8職場の例を示す．ツリーの最上部にあるが最初のカットであり,ここではRとなっている事から水平方向のカットであり,^職場1,2,3,5,8^{が建屋の西側},^職場4,6,7が東側に配置される事を示す．

LOGICは次に建屋のカットした部分をそれ自体“^部分建屋 ^{として扱い},^{上記の手順を各}“^部分建屋 ^が

1つの職場を含むだけになるまで繰り返す．

LOGIC^では,職場の形状を矩形に限定する事ができる．しかしながら,各職場の形状はそれぞれの面積

と配置された場所によって決まるために,入力情報として職場の形状を規定する事はできない．つまり,配置結果としては横長になったり逆に正方形に近くなってしまったりする．また,職場の総面積が建屋の面積と一致していなければならず,配置領域内に拡張のために空き領域が必要とされる場合等には向かない．

図2.8 Layout Coding via Guilotine-Induced Cut (ﬁgure taken from [1]

(27)

FBS(Flexible Bay Structre)

FBS^はTate and Smith[27]が開発したレイアウト表現技法である．改良FBS^は総面積∑N

i siが配置領域W ×Hよりも小さい場合にも適用できる様に改良したものである．

FBS,^{あるいは改良}FBS^では,建屋を縦方向に分割し（Bay^{と呼ばれる）},^{さらにその}Bay^{を横方向に} 分割する事で職場配置が行われる．改良FBSでは,これらの分割をBay BreakBk と職場順序Oik と呼ばれる2つのバイナリ順列により表現する．

X= [Bk

Oik

]

(2.39) Bk =

{ 1 k^{番目の職場で}Bay^変更

0 ^それ以外 (2.40)

Oik =

{ 1 ^職場i^がk^{番目に配置}

0 ^それ以外 (2.41)

図2.9^に5職場の例を示す．この例では,Bay Break=(1,0,1,0,1),^職場順序=(4,3,5,1,2)^{の例を示してお} り,^{職場順序は式}(2.41)に示すバイナリ変数の行列の形により表現されている．Bay Break^がある1,3,5 番目の職場配置後にBay^{変更となるため},^各Bay^に対して(4),(3,5),(1,2)^{が割り付けられる．各}Bay^内では,左図に示す通り,職場順序に従いBayを横方向に分割する事でレイアウト案を得る．各職場の縦幅, 横幅は分割の際に職場面積に応じて決定されるが,各職場のアスペクト比の上下限を超える場合は,上下限を超えない最大・最小の値に設定される．

FBS^{においても},LOGIC^と同様,下記に示すメリット・デメリットが存在する．

• 異面積の職場を扱う事ができる．

• 職場の形状を矩形に限定する事ができる．

• 職場のアスペクト比を規定が難しい．

• 配置領域の指定を指定が難しい．

図2.9 改良FBS(5職場の例)

(28)

2.4.4 MIP を用いた解法

MIPを用いた解法では,職場同士の相対位置をバイナリ変数,職場の座標・形状を連続変数として定式化を行い分子限定法等を用いて求解する．

相対位置制約は,^{相異なる職場}i, j^に対して,^職場i^職場jの左右上下のどの方向に配置されるかを指定する制約である. これらの関係性はバイナリ変数H (meaning ’horizontal’)^及び,V (meaning ’vertical’) により下記の様に示される．

Hij =

{ 1 (if iis left ofj) 0 (otherwise) Vij =

{ 1 (ifiis below j) 0 (otherwise) これらの変数を用いて,下記の様に職場同士の重複を排除する．

xi+wi≤xj−wj ifHij = 1 (2.42)

yi+hj ≤yj −hj ifVij = 1 (2.43) 全ての職場間に対して重複を排除するためには,下記の条件を満たしている必要がある．

Hij +Hji+Vij+Vji= 1 (2.44)

MIPでは,Hij,Vij の全ての組合せを探索すれば大域的な最適解を求める事が出来る.しかしながら,厳密解法であるため扱える問題規模が非常に少ない．これまでに様々な改良が提案されてきたが,^それらの改良をもってしても12職場の問題まで扱えておらず,適用範囲が非常に限定的であるという問題がある．

代表的なモデルとしてFLP0,FLP1,FLP2が挙げられる．次項以降に概略を示す．

図2.10 相対位置グラフ（左図）と職場レイアウト（右図）[35]. 左図はH,V ^{により規定された相対} 位置関係をグラフ形式で表している.右図は相対位置制約を満たしたレイアウトの例である. (Figures taken from S.Boyd[35])

(29)

FLP0

職場レイアウト問題をMIPとして最初に定式化したのが,Montreuil^のFLP0^{である．このモデルは}, 職場の中心座標だけでなく,上下左右の端の座標を用いて定式化しているところに特色がある．下記に FLP0^{の定式化を示す．}

minimize

∑N i=1

∑N j=i+1

fij(|xi−xj|+|yi−yj|) (2.45) subject to 0≤x⁰_i≤x⁰⁰_i ≤W (2.46)

0≤y_i⁰≤y⁰⁰_i ≤H (2.47)

w^min_i ≤(x⁰⁰_i −x⁰_i)≤w_i^max (2.48) h^min_i ≤(y⁰⁰_i −y⁰_i)≤h^max_i (2.49) (x⁰⁰_i −x⁰_i)(y_i⁰⁰−y⁰_i)≤si (2.50)

xi= 0.5x⁰⁰_i + 0.5x⁰_i (2.51)

yi= 0.5y_i⁰⁰+ 0.5y_i⁰ (2.52)

x⁰⁰_i ≤x⁰_j+M(1− Hij)≥1 (2.53) y_i⁰⁰≤y⁰_j+M(1− Vij)≥1 (2.54) Hij+Hji+Vij+Vji≥1 (2.55)

• N : 職場数;

• i, j : 職場番号(i, j = 1· · ·N);

• fij : ^職場 ij ^{間の物流量};

• W, H : ^{建屋の横幅・縦幅};

• Hij,Vij : 水平方向，垂直方向への職場 ij 間の相対位置関係を示すバイナリ変数.i^がj^の左(^下) にある場合Hij(Vij) = 1^{，そうでなければ}0;

• w^min_i , w^max_i : 職場iの横幅の上下限;

• h^min_i , h^max_i : 職場iの縦幅の上下限;

• si : ^職場i^の面積;

• M : ^{非常に大きい数};

• xi, x⁰_i, x⁰⁰_i : ^職場i^の中心,^左端,^右端のx^座標;

• yi, y_i⁰, y⁰⁰_i : 職場iの中心,下端,上端のy座標;

FLP0^{の問題点は以下の}2つが挙げられている．まずは,問題を線形化するために面積制約を外周長制約に置き換えているが,これにより得られる解の精度が非常に悪くなるという点である．もう一つは,^バイナリ変数の組合せが膨大であるため,^{扱える規模が}6職場程度までと限定されているという点である．

カオス最適化を用いた職場レイアウト技法 A Chaos-based Optimization for Solving

カオス最適化を用いた職場レイアウト技法 A Chaos-based Optimization for Solving

Facility Layout Problem

2013 年 2 月大森峻一

Shunichi Ohmori

カオス最適化を用いた職場レイアウト技法 A Chaos-based Optimization for Solving

Facility Layout Problem

2013 年 2 月

早稲田大学大学院創造理工学研究科経営システム工学専攻

ロジスティクスエンジニアリング研究

大森峻一

Shunichi Ohmori

目次

第 1 ^章

序論

1.1 ^研究目的

1.2 職場レイアウト技法について

1.2.1 職場レイアウト設計の位置づけ

1.2.2 職場レイアウトの設計プロセス

1.2.3 職場レイアウトの入力情報

1.2.4 レイアウトの評価関数について

1.2.5 数理的技法の役割

1.2.6 基本レイアウトと詳細レイアウト

1.3 本論文の構成

第 2 ^章

連続メタヒューリスティクスの必要性

2.1 レイアウト技法に具備すべき要件

2.2 本研究に関連する従来研究

2.2.1 連続表現と離散表現

2.2.2 具備すべき要件の観点からの従来技法のまとめ

2.3 ^{離散表現を用いた解法}

2.3.1 QAP,Hiller の入替法

2.3.2 CRAFT,MCRAFT

2.3.3 MULTIPLE,SABLE

2.4 ^{連続表現を用いた解法}

2.4.1 連続表現を用いた定式化

2.4.2 NLP を用いた解法

2.4.3 MH を用いた解法

2.4.4 MIP を用いた解法

カオス最適化を用いた職場レイアウト技法 A Chaos-based Optimization for Solving

カオス最適化を用いた職場レイアウト技法 A Chaos-based Optimization for Solving

Facility Layout Problem

2013 年 2 月 大森 峻一

Shunichi Ohmori

カオス最適化を用いた職場レイアウト技法 A Chaos-based Optimization for Solving

Facility Layout Problem

2013 年 2 月

早稲田大学大学院 創造理工学研究科 経営システム工学専攻

ロジスティクスエンジニアリング研究

大森 峻一

Shunichi Ohmori

目次

第 1 章

序論

1.1 研究目的

1.2 職場レイアウト技法について

1.2.1 職場レイアウト設計の位置づけ

1.2.2 職場レイアウトの設計プロセス

1.2.3 職場レイアウトの入力情報

1.2.4 レイアウトの評価関数について

1.2.5 数理的技法の役割

1.2.6 基本レイアウトと詳細レイアウト

1.3 本論文の構成

第 2 章

連続メタヒューリスティクスの必要性

2.1 レイアウト技法に具備すべき要件

2.2 本研究に関連する従来研究

2.2.1 連続表現と離散表現

2.2.2 具備すべき要件の観点からの従来技法のまとめ

2.3 離散表現を用いた解法

2.3.1 QAP,Hiller の入替法

2.3.2 CRAFT,MCRAFT

2.3.3 MULTIPLE,SABLE

2.4 連続表現を用いた解法

2.4.1 連続表現を用いた定式化

2.4.2 NLP を用いた解法

2.4.3 MH を用いた解法

2.4.4 MIP を用いた解法

2013 年 2 月大森峻一

早稲田大学大学院創造理工学研究科経営システム工学専攻

大森峻一

第 1 ^章

1.1 ^研究目的

第 2 ^章

2.3 ^{離散表現を用いた解法}

2.4 ^{連続表現を用いた解法}