博 士 論 文 概 要

早稲田大学大学院 創造理工学研究科

博 士 論 文 概 要

論 文 題 目

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

Facility Layout Problem

申 請 者

大森 峻一 Shunichi OHMORI

経営システム工学専攻 施設・ロジスティクスエンジニアリング専攻

2012 年 10 月

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

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

こ れ ま で 数 多 く の 職 場 レ イ ア ウ ト 技 法 が 提 案 さ れ て い る が ， レ イ ア ウ ト の 表 現 方 法 に よ っ て 離 散 表 現 ( D i s c r e t e R e p r e s e nt a t i o n ) と 連 続 表 現 ( C o n t i n u o us R e p r e s e nt a t i o n ) の 2 つ に 大 別 す る 事 が で き る. 離 散 表 現 で は グ リ ッ ド 状 の 配 置 領 域 に 職 場 を 配 置 す る 表 現 方 法 で あ り, コ ン ピ ュ ー タ は レ イ ア ウ ト を マ ト リ ク ス と し て 認 識 す る 事 が で き る ． 代 表 的 の 技 法 と し て は H i l l e r の 入 替 法, C R A F T, M U LT I P L E , S A B L E 等 が 挙 げ ら れ る ． こ の 様 に 解 表 現 を 離 散 的 に 行 う 事 に よ り 問 題 は シ ン プ ル に な る が, 代 わ り に 表 現 で き な い レ イ ア ウ ト が 存 在 す る た め, 解 表 現 の 柔 軟 性 が 失 わ れ て し ま う と い う 問 題 点 が あ る ． こ れ に 対 し ， 連 続 表 現 で は, レ イ ア ウ ト （ 職 場 の 座 標 ・ 形 状 ） を 連 続 変 数 ベ ク ト ル に よ り 表 す た め 非 常 に 柔 軟 な 解 表 現 が 可 能 と な り, 離 散 表 現 で は 表 現 で き な か っ た レ イ ア ウ ト が 表 現 可 能 と な る ． こ の 様 な 柔 軟 性 か ら, 近 年 の 研 究 で は 連 続 表 現 が 主 流 と な っ て き て い る ．し か し な が ら, 解 表 現 を 連 続 的 に 行 う 事 で, 求 解 は 非 常 に 難 し く な る ． こ れ ま で に 連 続 表 現 を 用 い た 職 場 レ イ ア ウ ト 技 法 と し て M I P( M i x e d - I n t e g e r P r o g r am m i n g) , N L P( N o n - L i n e ar P r o g r am m i n g ) , M H ( M e t a - H e ur i s t i c s ) を 用 い た 解 法 が 提 案 さ れ て い る が, 連 続 表 現 を 用 い た 難 し さ ゆ え, そ れ ぞ れ の 解 法 に 何 ら か の ” 妥 協 ” が 含 ま れ る 事 が 知 ら れ て い る ．N L P を 用 い た 解 法 で は,準 ニ ュ ー ト ン 法 等 の 非 線 形 連 続 最 適 化 技 法 を 用 い て 求 解 を 行 う が, 局 所 解 法 で あ る た め 得 ら れ る 解 の 質 が 初 期 解 に 依 存 し て し ま う と い う 問 題 が あ る ．M H を 用 い た 技 法 で は, レ イ ア ウ ト を 文 字 列 に 変 換 （ エ ン コ ー ド ） す る 事 で 組 合 せ 最 適 化 問 題 と し て 定 式 化 し S A ( S i m u l at e d A n n e al i n g ) , G A ( G e n e t i c A l g o r i t h m ) 等 の M H を 適 用 し 求 解 す る 方 法 で あ る ． し か し な が ら, 文 字 列 と し て 表 現 で き な い レ イ ア ウ ト が 存 在 す る と い う 問 題 点 が あ り, 解 表 現 が 限 定 的 に な っ て し ま う ．M I P を 用 い た 解 法

で は, 職 場 同 士 の 相 対 位 置 を バ イ ナ リ 変 数, 職 場 の 座 標 ・ 形 状 を 連 続 変 数 と し て 定 式 化 を 行 い 分 子 限 定 法 等 を 用 い て 求 解 す る ． し か し な が ら, 厳 密 解 法 で あ る た め 扱 え る 問 題 規 模 が 非 常 に 尐 な い ． こ れ ま で に 様 々 な 改 良 が 提 案 さ れ て き た が, そ れ ら の 改 良 を も っ て し て も 1 2 職 場 の 問 題 ま で 扱 え て お ら ず, 適 用 範 囲 が 非 常 に 限 定 的 で あ る ．

近 年 で は S E Q U E N C E や G R A P H - PA I R 等 ，M H と M I P を ハ イ ブ リ ッ ド で 用 い る 方 法 が 提 案 さ れ ，3 5 職 場 等 ， 大 規 模 な 問 題 で も 十 分 な 精 度 の 近 似 解 を 導 出 す る 技 法 が 提 案 さ れ て い る ． こ れ ら の 技 法 で は, 相 対 位 置 関 係 の 探 索 に M H を 適 用 し て い る ．し か し な が ら ， そ の 探 索 過 程 に お い て は ラ ン ダ ム な 近 傍 解 を 生 成 し そ れ を 取 捨 選 択 す る と い う 構 造 に な っ て い る が, 職 場 レ イ ア ウ ト 問 題 で は 「 物 流 量 が 多 い 職 場 同 士 は な る べ く 近 く に 」 と い う 自 明 の 良 解 条 件 が 存 在 す る た め ， ラ ン ダ ム に 探 索 す る 方 法 で は 探 索 過 程 に お い て 多 く の 無 駄 な 探 索 を 行 っ て い る と 考 え ら れ ， 多 大 な 探 索 時 間 を 必 要 と す る ． ま た, M D S ( M ul t i D i m e ns i o n a l S c a l i n g ) , 力 学 的 モ デ ル, 凸 緩 和 等 を 応 用 し て 物 流 量 が 多 い 職 場 同 士 が 近 く に 配 置 さ れ る 様 な 好 適 な 相 対 位 置 関 係 を 探 索 す る 試 み も い く つ か 提 案 さ れ て い る が, 職 場 レ イ ア ウ ト 問 題 が 多 峰 性 の 構 造(非 凸 性) を 有 し て い る 事 か ら, こ れ ら は N L P を 用 い た 解 法 同 様, 局 所 解 法 と な り 初 期 解 に 依 存 し て し ま う と い う 問 題 点 が あ る ．

本 研 究 で は ， 以 上 の 問 題 点 を 解 決 す る た め ， 連 続 表 現 に よ り 定 式 化 さ れ た 職 場 レ イ ア ウ ト 問 題 に 対 す る 効 率 的 な 数 理 的 技 法 の 開 発 を 対 象 と す る ． 本 研 究 で は, S EQ U E N C E や G R A P H - PA I R と 同 様, M I P と M H の ハ イ ブ リ ッ ト 戦 略 を 基 本 と し た 技 法 の 提 案 を 行 う ．本 研 究 で は, 相 対 位 置 関 係 の 探 索 過 程 に お い て 連 続 M H を 適 用 す る 事 で 「 物 流 量 が 多 い 職 場 同 士 は な る べ く 近 く に 」 と い う 良 解 条 件 を 活 用 し た 好 適 な 相 対 位 関 係 を 効 率 的 に 求 め る 新 た な ヒ ュ ー リ ス テ ィ ク ス を 提 案 し た ．

連 続 M H は 最 適 化 の 分 野 に お い て 非 凸 連 続 最 適 化 問 題 に 対 す る 解 法 と し て 目 覚

ま し い 成 果 を 挙 げ て お り, 大 域 的 な 探 索 能 力 に 優 れ る た め 初 期 解 に 依 存 す る 事 な く, 質 の 良 い 解 に 辿 り 着 け る 事 が 種 々 の 実 験 か ら 明 ら か に さ れ て い る ．従 っ て, 連 続 表 現 さ れ た 職 場 レ イ ア ウ ト 問 題 に お い て も, こ の 多 峰 性 を 克 服 す る 能 力 に よ り 質 の 良 い 解 を 効 率 的 に 探 索 で き る 事 が 期 待 で き る ．こ れ ま で に 様 々 な 連 続 M H が 提 案 さ れ て い る が, そ の 中 で も 問 題 構 造 に よ っ て 有 効 な 技 法 が 異 な る 事 か ら, 予 備 調 査 と し て 7 種 類 の 連 続 M H を 適 用 す る 事 で, 職 場 レ イ ア ウ ト 問 題 に 最 も 相 性 の 良 い 技 法 を 調 べ た ． そ の 結 果 「 カ オ ス 最 適 化 」 が 最 も 相 性 が 良 い 事 を 明 ら か に し た ．更 に 相 対 位 置 決 定 下 に お け る 職 場 位 置 ・ 形 状 の 最 適 化 を 高 速 化 す る た め, 主 双 対 内 点 法 を 適 用 し 問 題 の 構 造 を 利 用 し た カ ス タ マ イ ズ を 加 え た ． 数 値 実 験 で は, 小 規 模 問 題 に お け る 最 適 解 と の 比 較, 及 び, 大 規 模 問 題 に お け る 他 の 技 法 に よ り 算 出 さ れ た 近 似 解 と の 比 較 を 行 い, 提 案 技 法 の 有 効 性 を 示 し た ．

本 論 文 の 構 成 は 以 下 の 通 り で あ る ． 第 1 章 で は 研 究 目 的, 及 び, 本 論 文 が 研 究 の 対 象 と す る 場 を 明 ら か に し た ．

第 2 章 で は 職 場 レ イ ア ウ ト 技 法 に 具 備 す べ き 条 件, 従 来 の 研 究 と そ の 限 界 を 纏 め る と 同 時 に, 本 研 究 提 案 の 連 続 M H 適 用 の 必 要 性 を 述 べ た ． 具 体 的 に は 職 場 レ イ ア ウ ト 技 法 に 具 備 す べ き 条 件 と し て 1)異 面 積 の 考 慮 ，2 )配 置 領 域 の 限 定 ，3 )職 場 矩 形 性 の 維 持 ，4 )職 場 形 状 の 柔 軟 性 ， と い う 4 つ の 条 件 を 文 献 調 査 及 び ゼ ネ コ ン エ ン ジ ニ ア リ ン グ 本 部 へ の ヒ ア リ ン グ を 基 に 纏 め た ． こ れ ら の 要 件 に 対 し ， 離 散 表 現 さ れ た 従 来 技 法 で は 解 表 現 の 柔 軟 性 が 限 定 的 で あ る 事 ゆ え ， こ れ ら の 要 件 を 満 足 で き な い 事 を 説 明 し た ． 一 方 ， 連 続 表 現 さ れ た 従 来 技 法 を 用 い た 場 合 非 凸 性 よ り 求 解 が 困 難 で あ る 事 を 述 べ た ．以 上 の 2 点 よ り 解 表 現 の 柔 軟 性,及 び 非 凸 性 の 克 服 を 達 成 で き る 手 段 と し て 連 続 M H の 必 要 性 を 述 べ た ．

第 3 章 で は, 本 論 で 提 案 す る 技 法 の 基 本 概 念 を 示 し, そ の 予 備 調 査 と し て, 職 場 レ イ ア ウ ト 問 題 と 相 性 の 良 い 連 続 M H の 調 査 を 行 っ た ．具 体 的 に は 下 記 7 種 類 の 連 続 M H を テ ス ト 問 題 に 適 用 し 性 能 の 比 較 考 察 を 行 っ た ： 1 ) P S O ( P a r t i c l e S w ar m O p t i m i z a t i o n)，2 ) R CG A ( R e a l - Co d e d G e n e t i c A l g o r i t hm )，3 ) FA ( F i r e f l y A l g o r i t hm )，4 ) C S ( C u c k o o S e a r c h )，5) C S A( C o n t i n u o us S i m u l at e d A n n e al i n g )， 6) M S L S ( M u l t i - S t a r t Lo c a l S e a r c h )，7) C A ( C h a o s A n n e a l i n g )． こ れ ら の 性 能 比 較 の 結 果 よ り ，C A が 職 場 レ イ ア ウ ト 問 題 に 対 し て は 最 も 相 性 が 良 い 事 を 結 論 付 け る と 同 時 に ， 改 良 す べ き 点 に つ い て も 言 及 し た ．

第 4 章 で は, 前 節 で 示 し た C A の 改 良 点 を 踏 ま え ， 本 論 文 で 提 案 す る ア ル ゴ リ ズ ム の 詳 細 を 示 し た ．提 案 技 法 で は, 大 域 探 索 と 局 所 探 索 の フ ェ ー ズ を 分 離 し, 各 フ ェ ー ズ に 工 夫 を 加 え る 事 で C A の 改 良 を 行 っ た ．「 大 域 探 索 フ ェ ー ズ 」 で は 職 場 を 円 近 似 し た 「 カ オ ス 力 学 的 モ デ ル 」 に よ り 好 適 な 相 対 位 置 関 係 を 得 る 事 を 提 案 し た ． こ の 際, 円 近 似 を 行 っ て い る た め 職 場 同 士 の 衝 突 や 建 屋 外 へ の は み 出 し が 発 生 し に く く な り, よ り 目 的 関 数 の 最 小 化 を 重 視 し た 探 索 が 可 能 と な る ． こ の カ オ ス 力 学 的 モ デ ル に よ り 得 ら れ た 職 場 位 置 に 対 し て 相 対 位 置 関 係 を 抽 出 す る ．

「 局 所 探 索 フ ェ ー ズ 」 で は 得 ら れ た 相 対 位 置 関 係 を 制 約 と し て 主 双 対 内 点 法 を 用 い て 職 場 位 置 ・ 形 状 の 最 適 化 を 行 う ． こ こ で 主 双 対 内 点 法 を 改 良 す る 事 に よ り 非 常 に 高 速 に 求 解 す る 事 を 可 能 に し た ．

提 案 す る ヒ ュ ー リ ス テ ィ ク ス で は, 職 場 レ イ ア ウ ト 問 題 は M I P と し て 定 式 化 さ れ る ．M I P を 用 い る メ リ ッ ト と し て は,「 非 重 複 制 約 」 が 非 線 形 線 形 制 約 で あ っ た の に 対 し,「 相 対 位 置 関 係 」 を 用 い る 事 に よ り 非 重 複 制 約 を 「 線 形 化 」 す る 事 が で き る 点 で あ る ． こ れ に よ り 局 所 探 索 の フ ェ ー ズ に お い て 職 場 レ イ ア ウ ト 問 題 を L P と し て 扱 え る た め, 求 解 を 高 速 化 す る 事 が 出 来 る ．

第 5 章 で は,結 論 を 述 べ た ．

Ｎｏ.1

早稲田大学 博士（工学） 学位申請 研究業績書

氏 名 大森 峻一 印

（2012 年 10 月 現在）

種 類 別 題名、 発表・発行掲載誌名、 発表・発行年月、 連名者（申請者含む）

論文

◎

◎

講演

◎

○

◎

○

（査読論文）

[1] Solving Facility Layout Problem via Particle Swarm Optimization，

International Journal on Computer Science， Vol.4， No.5， pp.441-452 (2010-10) Shunichi Ohmori, Kazuho Yoshimoto， Kenshu Ogawa

[2] 実数値Genetic Algorithmを用いた施設レイアウト問題の解法，

日本経営工学会論文誌， Vol.62， No.4， pp.1-8（2011-10）

大森峻一， 三好加奈子， 吉本一穗

（国際会議）

[1] Solving Facility Layout Problem –Continuous Simulated Annealing-，

The 8th International Conference on Supply Chain Management and Information System 2010 (IEEE) (2011-10)，

Shunichi Ohmori， Kazuho Yoshimoto， Kenshu Ogawa

[2] Solving Facility Layout Problem via Particle Swarm Optimization,

International Conference on Computer Science and Optimization (IEEE CS) (2010-5) Shunichi Ohmori， Kazuho Yoshimoto, Kenshu Ogawa

[3] A Continuous Representation and Chaos Theory Based Algorithm for Solving Facility Layout Problem

21st International Conference on Production Research (2011-8) Shunichi Ohmori， Kazuho Yoshimoto， Kenshu Ogawa

[4] A tailored primal-dual interior-point method for Facility Layout Problem with Relative-Positioning Constraints (2012-5)

Industrial Engineering Research Conference 2012. (Institute of Industrial Engineering) Shunichi Ohmori，Kazuho Yoshimoto，Fumi Sekimoto，Hiromasa Akagi

[5] Multi Floor Facility Layout Considering Multi-Floor Department,

Asian Conference on Management Science and Applications 2011 (2011-12) Shunichi Ohmori， Hajime Ichikawa, Kazuhiro Nomiyama, Kazuho Yoshimoto, Hiromasa Akagi

[6] Stochastic Facility Layout Problem Considering Investment-Operating Cost Trade-Off, Asian Conference on Management Science and Applications 2011 (2011-12),

Shunichi Ohmori， Kazuhiro Nomiyama, Hajime Ichikawa, Kazuho Yoshimoto, Hiromasa Akagi

Ｎｏ.2

早稲田大学 博士（工学） 学位申請 研究業績書

種 類 別 題名、 発表・発行掲載誌名、 発表・発行年月、 連名者（申請者含む）

○

○

[7] Simulation Model to Determine Optimal Buffer Spaces for Minimal Production Cost, Asian Conference on Management Science and Applications 2011 (2011-12),

Takashi Masumitsu， Komine Naoya， Shunich Ohmori， Kazuho Yoshimoto

[8] Facility Layout System using Interactive Evolutionary Computation

Asian Conference on Management Science and Applications 2011 (2011-12) Kanako Miyoshi

Yuuki Nouno

Shunichi Ohmori

Kazuho Yoshimoto

[9] A Study on Commercial Facility Location Problem by Binary Particle Swarm Optimization

Asian Conference on Management Science and Applications 2011 (2011-12) Shu Ando

Hanyong Choi

Shunichi Ohmori

Kazuho Yoshimoto

[10] Optimal 3D Facility Layout Technique Considering Pipeline Route Arrangement -For Industrial Facilities and Plant Layout-

Asian Conference on Management Science and Applications 2011 (2011-12) Yuki Nono

Kanako Miyoshi

Shunichi Ohmori

Kazuho Yoshimoto

[11] Improvement of Particle Swarm Optimization of the Mutation Concept for the Escape from Local Minima，

The 8th International Conference on Supply Chain Management and Information System 2010 (IEEE) (2011-10)，

Hanyong Choi

Shunichi Ohmori， Kazuho Yoshimoto

[12] A study on the application of Simulated Annealing with Continuous Neighborhood to Facility Layout Problem, Industrial Engineering Research Conference 2010

（2010-6）

Shunichi Ohmori，

Kazuho Yoshimoto

[13] A Scheduling Method for Hybrid Flowshop Scheduling Problem: Proposal of the Chain Assigment of Jobs by Earliest Starting Time,

19th International Conference on Production Research (2009-8)

Kazuho Yoshimoto， Kenshu Ogawa

（国内会議）

[14] 連続最適化アプローチを用いた施設レイアウト技法の開発～カオス最適化技法の適

用～,

日本経営工学会2010秋季研究大会 （2010-10）

大森峻一，吉本一穗

Ｎｏ.3

早稲田大学 博士（工学） 学位申請 研究業績書

種 類 別 題名、 発表・発行掲載誌名、 発表・発行年月、 連名者（申請者含む）

[15] Particle Swarm Optimizationの改良

日本経営工学会2010秋季研究大会 （2010-10）

崔漢龍，大森峻一，吉本一穗

[16] 需要が変動する多期間配送計画問題に関する研究（2010-5）

日本経営工学会2010春季研究大会 益満崇，大森峻一，吉本一穗

[17] Multi-Depot Vehicle Routing Problem に 関 す る 研 究-Multi-Route,Dynamic Partitioningの考慮- （2010-5）

日本経営工学会2010春季研究大会 小峰直也，大森峻一，吉本一穗

[18] 実数値 GA(Genetic Algorithm)を用いた施設レイアウト設計の提案-シンプレクス

交叉の適用- （2010-5）

日本経営工学会2010春季研究大会 三好加奈子，大森峻一，吉本一穗

[19] 第2 工程が複数台マシンを持つ2 工程HFS（Hybrid Flowshop Scheduling）問題に対 する最早開始時刻の連鎖割付の最適性の証明，

日本機械学会第20回設計工学・システム部門講演会 （2009-11）

大森峻一，吉本一穗

[20] 複数工程・複数機械の加工職場におけるフローショップスケジューリングに関する

研究，

日本経営工学会2008秋季研究大会 （2008-8）

大森峻一，吉本一穗

[21] 充電を考慮したＡＧＶスケジューリング技法の開発〜レイアウト技法（ＢＬ法）を

用いたガントチャート表現，

日本経営工学会2007春季研究大会 （2007-4）

大森峻一，千葉真人，関本章，吉本一穗