職場形状非固定の問題

提案技法の有効性を検証するため，FLP^{ベンチマーク問題}[32, 46, 47, 48, 49]^{を用いて数値実験を} 行った．表4.3に，各ベンチマーク問題の出典，フロー密度(FD:Flow Density)^{，面積利用率}(AU:Area Utilization)^，最良値(Best Known Solution)^{，最良値の出典}(Best Known Solution)^{を纏めた．ここで，}

フロー密度は物流が存在する(i.e.,fij >0となる)職場ペアの割合で，全ての職場間に物流が存在する 時，フロー密度は100%となる．また職場利用率は職場の総面積を建屋面積で割った値で，建屋内のデッ ドスペースが全くない時に面積利用率は100%^となる．

比較対象は，各問題に対しベスト解を出している従来技法である Liu and Meller[32], Bozer and Wang[33], Konak and Konak [44]を用いてた．提案技法は異なる初期解から10^{回の試行を行った．実} 験環境,^{パラメータ設定は表}3.2^{にまとめた．}

実験結果として，表4.4に目的関数値，表4.5に計算時間を示す．また，SC35に対する，得られた相 対位置関係，得られたレイアウト図面をそれぞれ図4.9,図4.10に示す．以下にそれぞれの図表に対する コメントを行う．

表4.1の設定を基に，カオス力学的モデルによる職場移動を繰返し最も目的関数値が少なくなった時の 様子を示したのが，図4.9である．図中の線は職場間の物流量を表しており，線が太い程，物流量が大き い値となっている．結果を見てわかる通り，物流量が大きい職場同士は近づいて配置されている事が確認 できる．

この結果から，相対位置関係を抽出しLPにより最適化を行ったものが図4.10^{である．図}4.9^で求め られた職場位置，相対位置関係が維持されながら面積条件を加えた形になっており，図4.9^{と同様，物流} 量が大きい職場同士は近づいて配置されている事が確認できる．尚, 右上隅の職場が孤立しているが,^こ れは他の職場と全く物流量を持たない職場である事が理由である．

同様の実験を表4.3の各問題に対して行った結果が表4.4である．表4.4を見ると，提案技法を用いる 事により，Ba10, SC30, SC35の3問題に対し，ベスト解の更新を行う事ができた．また，その他の問題 に関しても，従来技法と同程度の質の解を算出できている事が確認できる．ベスト解との誤差が大きい問

題はM15a,M15sであるが，これらの問題に共通している事項としては「FD^{が小さく」「}AU^{が大きい」}

表4.4 目的関数値の比較(-はデータなし．*はベスト解)

問題 Best Konak & Konak [44] Liu & Meller [32] Bozer & Wang [33] ^提案技法

O7 131.6 - 131.6* - 211.2

O8 240.0 - 240.0* 240.0* 397.4

O9 235.2 - 235.2* 235.2* 356.3

VC10 18823.7 18823.7* 19997 - 19507.0

Ba10 8129 8129 8702 - 7970.3*

M15a 27545.3 27545.3* - - 36612.9

M15s 23197.8 23197.8* - - 37654.9

AB20 4833.4 5336.4 5668 4833.4* 5135.6

Tam30 19462.4 19462.4* - - 23791.2

SC30 3340.3 3443.3 3707 3340.3 2993.5*

SC35 3379.5 3700.8 3604 3379.5 3044.8*

という事である．この特徴を考えると物流コストの最小化よりも，面積条件をいかにうまく扱うかがポイ ントであるため，カオス力学的モデルにおいて引力が働きにくく，結果として提案技法のメリットがう まく発揮されなかったと考えられる．またO7,O8,O9は小規模問題であるため最適解がわかっているが，

提案技法では最適解を求める事ができなかった．これらの点は今後の課題として考えられる．

計算時間(^表4.5^参照)を見ると，本研究と同じFLP2の定式化を用いて解いている[32, 33]^に比べて 提案技法が約0.04-5% の探索時間で求解できている事がわかる．（[44]^はFBS:Flexible Bay Structure を用いておりMIPよりも解空間が狭くなっているが，それと比べても約1-21%の探索時間で求解ができ ている．）これは，力学的モデルの引力の作用により，物流量が大きい職場同士が高速に引き合う作用を 持っている事が主因であると考えられる．実際に本研究提案の職場レイアウト技法を用いる際には，設計 者がコンピュータを利用し，次々と入力条件（職場の面積/形状・建屋面積・職場間の近接性）を変えて，

結果を検討しながら実行することを想定しているため，速やかな応答が実現できる方が望ましい．従っ て，計算時間の短縮はこの応答性が良くなる点でメリットがあると考えられる．

最後のコメントとして，図4.9と図4.10の関係は，SLP(Systematic Layout Planning)における「ア クティビティ相互関係ダイアグラム」と「面積相互関係ダイアグラム」の関係と同様の関係であり，実務 的には図4.9の段階でレイアウト案の検討を行うといった様な使い方も興味深い．本研究提案のカオス力 学的モデルを用いる事により，図4.9の様な「アクティビティ相互関係ダイアグラム」の代替案が高速に 求められるので，この段階でも十分に設計者の意思決定を支援できると考えられる．これは，特に面積要 件などが定まっていない段階でのディスカッションに有効であると考えられる．

第4章 カオス最適化と線形計画法を用いたヒューリスティクスの提案 97

表4.5 計算時間の比較(-はデータなし．*はベスト解)

問題 Konak & Konak [44] Liu & Meller [32] Bozer & Wang [33] 提案技法

O7 - 562 - 2*

O8 - 3,056 18 3*

O9 - 3,879 21 4*

VC10 3 - 0.6*

Ba10 10 2,988 - 1.2*

M15a 17 - - 1.5*

M15s 18 - - 1.8*

AB20 85 12,456 116 2.7*

Tam30 924 - - 5.0*

SC30 873 14,652 1,102 52.0*

SC35 1,842 5,774 1,915 87.8*

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

x 10⁻³ 0.4

0.6 0.8 1 1.2 1.4 1.6 1.8 2 2.2x 10⁴

図4.8 SC35に対する力学的モデルの分岐図

−2 0 2 4 6 8 10 12 14 16 18

−2 0 2 4 6 8 10 12 14 16 18

図4.9 SC35に対するカオス力学的モデル適用後のアウトプット

−2 0 2 4 6 8 10 12 14 16 18

−2 0 2 4 6 8 10 12 14 16 18

図4.10 SC35に対するLP適用後のアウトプット

第 5 ^章

結論

の3点である．

1. 連続メタヒューリスティクスの必要性（第2^章）

2. 職場レイアウト問題と連続メタヒューリスティクスの相性調査（第3^章）

⇒CA(Chaos-Annealing)が最も優れた結果となった．

3. カオス最適化を用いたヒューリスティクスの提案（第4章）

⇒大域探索と局所探索のフェーズを分離し,各フェーズに工夫を加える事でCAを改良した．

一点目として,レイアウト技法に具備すべき条件,従来の研究とその限界を纏めると同時に,^{本研究提案} の連続メタヒューリスティクス適用の必要性を述べた．レイアウト技法に具備すべき条件として1)^異面 積の考慮，2)^{配置領域の限定，}3)^{職場矩形性の維持，}4)職場形状の柔軟性，という4^{つの条件を文献調} 査及びゼネコンエンジニアリング本部へのヒアリングを基に纏めた．

従来技法はレイアウトの表現方法によって離散表現(Discrete Representation)と連続表現

(Continu-ous Representation)^の2つに大別する事ができるが, 離散表現ではグリッド状の配置領域に職場を配置

する表現方法であり,問題はシンプルになる代わりに「表現できないレイアウトが存在するため解表現の 柔軟性が失われてしまう」という問題点があり,上述の具備すべき要件を満足できない事を示した．これ に対し，連続表現では,レイアウト（職場の座標・形状）を連続変数ベクトルにより表すため非常に柔軟 な解表現が可能となり,離散表現では表現できなかったレイアウトが表現可能となり上述の具備すべき要 件を満足できる事を示した．この様な柔軟性から,近年の研究では連続表現が主流となってきている事を 述べた．しかしながら,解表現を連続的に行う事で,求解は非常に難しくなる事を纏めた．

具 体 的 に は, こ れ ま で に 連 続 表 現 を 用 い た レ イ ア ウ ト 技 法 と し て MIP(Mixed-Integer Program-ming),NLP(Non Linear Programming),MH(Meta-Heuristics) を用いた解法が提案されているが,^連 続表現を用いた難しさゆえ,それぞれの解法に何らかの”妥協”が含まれる事が知られている事を示した．

NLPを用いた解法では,局所解法であるため得られる解の質が初期解に依存してしまうという問題があ る事を述べた(^{解の質に対する妥協})^．MH^{を用いた技法では},文字列として表現できないレイアウトが存 在するという問題点があり,解表現が限定的になってしまう事を述べた(解表現の自由度に対する妥協)^． MIPを用いた解法では厳密解法であるため扱える問題規模が非常に少ない事を述べた(^{問題規模に対す} る妥協)．近年ではSEQUENCE(Liu and Meller[32])やGRAPH-PAIR(Bozer Wang[33])等，MHと MIPをハイブリッドで用いる方法が提案され，35職場等，大規模な問題でも十分な精度の近似解を導出 する技法が提案されているが，その探索過程においてはランダムな近傍解を生成しそれを取捨選択すると いう構造になっており,職場レイアウト問題では「物流量が多い職場同士はなるべく近くに」という自明 の良解条件が考慮しておらず探索過程において多くの無駄な探索を行っていると考えられ，多大な探索時 間を必要とする事を述べた．また,MDS(Multi Dimensional Scaling),^{力学的モデル},^{凸緩和等を応用し} て物流量が多い職場同士が近くに配置される様な好適な相対位置関係を探索する試みもいくつか提案され ているが,職場レイアウト問題が多峰性の構造(非凸性)を有している事から,これらはNLPを用いた解 法同様,局所解法となり初期解に依存してしまうという問題点がある事を述べた．

一方,^{最適化の分野では},非凸連続最適化問題に対する解法として,連続メタヒューリスティクス(^連続 最適化問題に対するメタヒューリスティクス)^が,近年目覚ましい効果をあげており,^{初期解に依存する事} なく質の良い近似解に辿り着ける事が種々の実験から明らかにされている．従って,連続表現された職場 レイアウト問題においても,この多峰性を克服する能力により質の良い解を効率的に探索できる可能性に 着目し適用の必要性として纏めた．

第5^{章 結論} 101 二点目として,職場レイアウト問題と相性の良い連続メタヒューリスティクスの調査を行った．連続 MHは様々な問題に対して汎用的に用いる事ができるが,それぞれの技法の探索戦略に偏りがあるため特 定の問題に対しては,技法との相性の良し悪しが結果に大きな影響を与える事がある．そこで,^本章では 代表的な技法に対して性能比較を行い,職場レイアウト問題に最も適した連続MH^{を明らかにした．具体} 的には下記7^{種類の連続}MHをテスト問題に適用し性能の比較考察を行った：1)PSO(Particle Swarm Optimization)，2)RCGA(Real-Coded Genetic Algorithm)，3)FA(Firefly Algorithm)，4)CS(Cuckoo Search)，5)CSA(Continuous Simulated Annealing)，6)MSLS(Multi-Start Local Search)，7)CA(Chaos

Annealing)．これらの性能比較の結果より，CAが職場レイアウト問題に対しては最も相性が良い事を結

論付けると同時に，改良すべき点として「1．職場形状非固定の問題に対応できない」「2.^{局所探索に時間} がかかる」「3.実行不可能解の割合が高い」という3^{点を述べた．}

「1．職場形状非固定の問題に対応できない」という問題点に関しては職場の縦幅・横幅(wi, hi)^を決 定変数として扱った場合,探索の過程でこれらの変数がマイナスの値を取る場合があり,これにより解を 正しく評価する事ができないためである．これを排除するため,職場の縦幅・横幅(wi, hi)にマイナスの 値が出た場合に,強制的に予め設定した最小値まで繰り上げられる方法も考えられるが,^{ペナルティ関数} が微分不可能になるためCAの適用条件に反する．特に大域的最適化フェーズでは,^{ステップ幅}ht を大 きくとるため非常に多くの解更新においてマイナスが発生してしまう事を述べた．

「2.局所探索に時間がかかる」という問題点は,効率性の観点からの問題点であり,約88%の時間を局 所探索に用いている事がわかったため,この局所探索のフェーズを高速化する事ができれば，同程度の解 の質を維持したまま計算時間を短くする事ができ,これにより設計者が用いる際の応答性がさらに良くな る事を述べた．

「3.実行不可能解の割合が高い」に関しては,^{解更新を行う際に},職場同士の衝突が多発する事が理由と して述べた．この事による問題点として,CAでは解更新を行う際に「目的関数を最小にする方向」と「制 約違反を除去する方向」の2つのベクトルを合成して移動ベクトルを算出しているが，現状では制約違反 の割合が高すぎるため目的関数に関する項が軽視されすぎてしまう危険性があり探索範囲がせまくなる可 能性がある事を述べた．

三点目として,以上の問題点を解決するため,^{本研究では},大域探索と局所探索のフェーズを分離する事 で,上述の点を克服できる技法の提案を行った．提案する技法では,^{レイアウト問題は}MIP^{として定式化} を行った．MIPを用いるメリットとしては,「非重複制約」が非線形制約であったのに対し,「相対位置関 係」を用いる事により非重複制約を「線形化」する事ができる点である．これにより局所探索のフェーズ においてレイアウト問題をLP^{として扱えるため},求解を高速化する事が出来る．

「1．職場形状非固定の問題に対応できない」という問題点に対しては,局所探索フェーズにおける制約 条件の扱い方として,「バリア関数法」を用いる事で対応すした．CAを適用する際に用いた「ペナルティ 関数法」では,制約条件の違反度合いに応じてペナルティを課す事により制約違反を抑制していたが,^バリ ア関数法では制約条件の違反そのものを発生させない様にバリア関数を設定した．このバリア関数により 探索点は制約領域内のみを探索できるようになる．このため,職場形状(wi, hi)を用いる際にマイナスの 値を取る事を抑制できる．

「2.局所探索に時間がかかる」という問題点に対しては,局所探索フェーズにおいてニュートン法を適 用して最適化を行う事で対応した．ニュートン法は収束速度が2次収束となる事が知られており,1^次収 束である最急降下法よりも遥かに高速である事が知られている．これを用いる事で,局所探索の高速化を 行った．また,ニュートン法を用いる際に,連立方程式(ニュートン方程式)を解く必要があるが,その際に 行列の構造（帯性・対角性）を利用して求解の高速化を図った．また冗長な制約を除去する事により制約