OR技術とその適用システム
築山 誠，森一之，安部 恵介……【………】lll……llll…l…ll川…lll川…llllll…………lllll……l‖‖＝＝‖‖‖＝‖‖‖‖‖‖‖＝‖‖‖‖‖‖‖‖‖‖‖‖‖‖＝＝‖‖＝‖‖‖‖‖‖＝‖‖‖‖‖‖‖‖‖‖‖‖‖‖＝‖‖‖＝‖‖‖＝‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖＝‖‖‖＝‖‖‖＝‖‖‖＝‖‖‖＝‖‖‖＝‖‖‖＝m】

大規模かつ複雑なシステムではモデル化の時点で問1．はじめに題を簡略化することも多いため，定式化した最適化問

産業システムの計画や運用は数理的にモデル化する

題の厳密解を求めても，それがそのまま現実問題の最とその多くは組合せ最適化問題となるが，一般には人適解にならないことも多い．そのような理由で，厳密間の経験と知識によって解決しているのが現状といえな最適性にこだわらないヒューリスティックアプロー

る．

チも多用される．
一方，情報制御技術の進展に伴い種々の分野で計算シミュレーションは大規模複雑システムの計画・運機による自動化，あるいは意思決定支援が進められて用問題の解決を支援する最も実用的でポピュラーなツいる．このコア技術としてOR技術が適用されている，ールである．しかし，シミュレーションそのものには

本稿では，産業システムにおける計画システム・運計画案作成機能はないため，メタ戦略との組み合わせ用システムにおいて，OR技術がどのように通用されているのか，電力，交通，製造，物流などの各分野の事例を用いて紹介する．

使用により解探索を行っている．

図2は最適化問題への適用手法を示す．図3は産業システム分野における運用制御システム，意思決定支援システムにOR手法がどのように組み込まれている

2．OR技術適用の概要のか，その概念的構造を示している．

産業システムにおけるOR技術の適用は図1に示す
様に，設計，計画，運用の3段階に分けて考えること

3．OR技術の産業システムへの適用ができる．これらの段階で，主に使用されているのは，

3．1エレベータ群管理システム

離散事象系シミュレーション技術，最適化技術，それオフィスビルには5台から10台のエレベータが並らを融合した技術である．

んで設置してある．呼びボタンを押すとどれか一つのエレベータの表示燈がつき数秒後にそのエレベータがプラント，物流システム
鉄道網，電力系統来る．これはエレベータ群管理システムが適当なエレベータを割り当てた結果だ．群管理システムは客の平均待ち時間やイライラ度を最小にするようにエレベー生産計画，輸送計画
列車ダイヤ，保守計画

エ場運用，出荷配車
運転整理，系統復旧
図1産業システムにおける最適化問題
つきやま まこと，もり かずゆき，あべ けいすけ
三菱電機㈱ 産業システム研究所〒661−8661尼崎市塚口本町8−1−1
1999年11月号

図2 大規模組合せ最適化問題の解法© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（3）589図3 0R技術適用の構造タを割り当てる．問題の難しさは，呼びが各階で，また時間間隔も確率的に発生すること，リアルタイムに

図4 連接水系運用計画問題の解法割り当てを実行しなければならないことにある．ファジー技術やニューラルネット技術が適用されている．

するダムならびに発電所を経済的に運用するために，3．2 自動車のナビゲーションシステム

翌日の発電計画を立案するものである［4］．運用計画

ナビゲーションシステムの機能の一つに，目的地経の立案にあたっては，系統運用者が，計画立案，シミ路案内がある．道路地図上で始点と終点を与えれば，ュレーションによる評価，計画の見直し，という手順最短距離や最短時間となる経路を探索をする．経路を繰り返すことで計画立案するのが一般的である．こ

探索問題は古くからあるOR問題のひとつであり，の計画立案プロセスを効果的かつ効率的に実施できる

Dijkstra法などの解法が苦からある．が，実用版でように支援システムが構築されている．

は計算時間短縮と記憶メモリーの効率的使用をポイン

3．4 送水運用計画システム

トに近似解法や事前探索解利用法などが使用されてい上水道システムでは，水は浄水場で飲料水にされパイプ，ポンプといった送配水設備によって需要家に送る［1］．
3．3 電力系統運用計画システム

られる．水需要は朝と夕に山をもつパターンで変動す

電力系統の巨大化，複雑化に伴い，各種計画業務のるが，浄水処理量は日間ほぼ一定している．これらを自動化が検討されている．そのような例として，系統バランスさせるためのバッファとして貯水池，配水池設備の点検／拡充等のための作業停止計画問題に対しが介在している．池のバッファを活用し送水ポンプのて組合せ最適化手法を適用したシステムが開発されて運転コストを最小にすれば大幅な省エネルギーとなる．

いる．これは，運用制約，実施要求日等を満足するた

このようなポンプ運転計画問題に対して混合整数計画めの日程調整問題と，作業実施時に系統の信頼度を確法やシミュレータとヒューリステックを結合した方法保するための系統構成立案問題とからなる二重の組合等が適用された［5］．

せ最適化問題として定式化し，メタヒューリステイク

3．5 エ場ライン設計支援システム

スを適用

生産システムの機能の大半は工場の能力に依存する．

また，停電等の事故時に，影響を最小限に抑えながその意味で工場設計は生産システムにおける最も重要ら速やかに復旧を図る系統復旧計画問題も代表的なもな問題といえる．図5に工場設計問題の概要を示す．
工場新設時や製造ライン改造時には，効率的生産をのといえる［3］．
連接水系日間運用計画立案システムは，水系に存在590（4）実現するために，ライン配置，製造機器の選択，工場© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ・装置割当．処理順序・顧客納期・ロット優先度

図6 生産計画問題＋ゝ）さ ・……・・・・・・・ヱト

データの流れ コントロール メッセージ交換

図5 工場設計問題

内物流を検討する．この検討の善し悪しが大幅なコスト増減に関わってくる．そこで，効果的な検討を目的に工場ライン設計支援システムを開発した．これは，計算機上に製造ラインをモデル化し，そのモデルを操作することで最適な製造ラインを求めるものである．
設備レイアウトは一種の組ノ合せ問題でありこれに対して種々のアルゴリズムが検討されているが，現在の世S L S：戦略レベルスケジューラの中の技術は実用レベルには至っていない．我々はこOL S：オペレーションレベルスケジューラの問題に対してインタラクティブな設計を行う新しい

図7 階層分散型スケジューラ支援システムを開発した［6］．これは，レイアウト決定サブシステムとスケジューリングシミュレータから装置が次に処理すべきジョブを選択するディスパッなる．レイアウト案に従って入力された製造ラインはチングルールを用いたシミュレーションによりスケジ3次元CGによって表示され，シミュレーションと連ュールを作成する．ディスパッチングルールによるス

動して搬送車や機械，ロボットが動き，その結果はリケジュール作成は，組合せ最適化問題の解法としては，ードタイム，WIP変動，稼働率などの指標に整理さ局所探索により一つの実行可能解を作成する構築型手れる．

法といえるが一般にこれだけで十分に良い解が得られ工場ライン設計支援システムは，製造組立機器や監視制御システムなどの個別システムだけでなく工場全る保証はない．そのため，対話型の修正によって逐次改善できるエディタ機能を実現した．

体の設計をとりまとめる総合エンジニアリングカとし（b）リアルタイムスケジューリングてのシステム製品と位置づけられる．

生産効率向上のためには，個々の装置においてライ3．6 生産計画・運用支援システム

ン状況にリアルタイムに対応するとともに，生産シス（a）オフラインスケジューリング

テム全体としての効率化を図り与えられた生産要求に工場の日々の生産では，図6に示すように，どの品対応していく必要がある．そのためには個々の装置レ種を何個，何時何分に製造ラインに投入するかを決定

ベルの自律的な意思決定とともにシステム全体としてするために，また特急品製造が要求されたときに受けの効率的なスケジュール作成機能が必要である．そこ入れ可能かどうかを判断するために，離散事象シミュで，システム全体の意思決定・管理レベルと個々のサレーションとインタラクティブ修正をベースとした生ブシステムレベルから成る階層分散型リアルタイムス

産運用管理システムが使われている［7］．

ケジュー

1999年11月号

リングシステムを開発した［8］．

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（5）591

匝弓

知識ベース
シミュレータ
集合分割モデルマッチングモデル
知識ベース

集合分割モデル
最小費用循環流
知識ベース

割当問題

作業計画

図9 幹線輸送計画

荷積・荷卸作業
容量・時刻制約

響等も考慮する必要があり，悪天候やオーダの追加／

図8 輸送計画問題

変更による計画修正も度々ある．

基本的考え方は図7に示すように，上位の階層でシ輸送コスト削減のためには，自社で保有する専用船ステム全体の観点から戦略的スケジュールを作成し，の稼働率を向上することが重要である．シミュレーシ

下位の各サブシステムは上位から与えられたスケジュ

ョンをベースとしたヒューリスティツールを規範として，個々の状況に対応したリアルタイムによる配船計画システムを開発した．解空間の探索

ムな意思決定を行うものである．

によりさらに最適化を図ることも可能である．

3．7 輸送・配送計画システム

3．8 鉄道ダイヤ作成・運行管理システム（a）幹線輸送計画システム

鉄道のダイヤ作成では，普通電車，急行，快速など物流システムにおいても設計は最も重要な課題であの電車をターミナル駅から何時何分に発車させるのか．

り，物流センターや集配送拠点等の物流拠点を適切な追い越し駅にて先行の普通電車を何分待たせるのかを規模で配置し，需要地，拠点，工場間の効率的な輸送決める．このダイヤ作成のために，離散事象シミュレ方式の設計を行う．拠点配置と輸送方式は相互に関連ーションとヒューリスティックを組み合わせた支援シしており，全体としてのコスト最小化を図る必要があステムが使われている．

また，情報システムの発展により乗客の輸送需要をる．

輸送計画問題は図8に示すように構成される．工場より正確に把握することが可能となってきている．そや物流拠点での生産計画や在庫管理による制約に基づ

こで，乗客需要に基づくより柔軟な列車運行計画作成

き，需要地（販売店，顧客等）のオーダに対する効率方式を提案した［10］．

的な輸送計画を作成しなければならない．この目的に列車運行計画は，列車本数，運行ルート，停車パタ対して，拠点間の幹線輸送計画手法を開発した［9］．

ーン，出発順序等多くの要因を含む大規模複雑な組合

これは，知識ベースと最適化手法を結合したものであせ問題である．提案手法は乗客の輸送需要を満足し総り，知識ベースにより制約条件の記述と解空間の縮小所要時間を最小とする列車運行計画を作成するものでを行い，最適化アルゴリズムにより効率的な解空間のあり，図10に示す部分問題により構成されている．

探索を行う．図9に本輸送計画の求解過程を示す．

列車運行はネットワークモデルとして実現されてお（b）出荷配船計画

り，また各駅での列車出発順序はシミュレーション実

化学プラント等の物流は船舶による輸送が主体とな行中において局所探索により自動的に決定される．

る．配船業務は各地点での生産／消費計画に基づく在庫バランスやユーザオーダに対応する出荷計画とこれ

4．今後の課題を実現する配船計画を同時に考慮して行う必要がある．

産業システム分野での計画，運用管理システム問題

さらに荷積／荷揚バースの制約や気象条件，潮流の影は一般に問題が複雑に絡み合った大規模問題である．

592（6）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

その意味で，OR技術の新たな適用分野として研究が進展することを期待する．

また本稿でふれなかったOR技術適用事例も多数ある．特に，道路情報システムやサプライチェインマネージメント等に関連して今後も種々の新たな問題が生じ，OR技術の適用が期待される．
参考文献
局所探索

［1］上川，梅津：車載ナビゲーションシステムの経路探索

技術，計測と制御，Vol．36No．11790／792，1997．
最長経路アルゴリズム［2］小島，石乳渡辺：組み合わせ最適化手法による電力設
備の作業停止計画の自動化，電気学会電力・エネルギー部門大会（1998）．

最短経路アルゴリズム［3］長澤，他：基幹系統事故時復旧支援のための復旧目標
系統・復旧操作手順立案手法，電気学会電力技術研資，
PE−92−160（1992）．

［4］Tomeoka，Nakajima，Kawachi，Nakamura，
図10 乗客流に基づく列車運転計画

Watanabe：NewDailyHydroSchedulingSystemfor
Multi−ChainHydroSystem，Proc．ofESAP，93，33／38

まず，漠然とした問題を解析，整理し全体構造を明確にしていく．この段階で複雑で漠然としていた問題は，

1993．
［5］小澤，築山：知識ベースによる送水系統運用支援法，電部分問題に切り分けられるが，この部分問題も依然と気学会論文誌D，Vol．109−D，No．5，1989．

して大規模であり，問題の構造は，組合せ最適化問題［6］森，安臥築山：設備レイアウト計画システムLayout−や非線形最適化問題となるものがほとんどである．

OR技術として主に使用されているのは，シミュレーション技術と各種最適化技術やヒューリステイクスとの組合せであった．その理由は，各部分問題でさえ最適化ツールの通用可能規模を越えていることにもあMakerの開発，計測自動制御学会システム情報部門シンポジウム，1999予定．
［7］森，築山，福田：ジョブショップ型スケジューリング問
題に対するハイブリッドスケジューリング法，電気学会

論文誌C，Vol．112−C，No．9，1992．
［8］森，築山，福田：階層型意思決定システムによるFMSる．相当規模の問題に対して真の最適解を短時間で求のオンラインスケジューIノング法，電学論D，113，No．9

めることができるならば，通用システム実現の仕方も（1993）．

違ったものになるであろう．非線形計画ツール・整数計画ツールの扱える規模の拡大，メタ戦略アルゴリズ［9］安部，築山：ロジスティクスにおける輸送計画手法，計測自動制御学会論文集，Vol．26，No．12（1990）．

ムの進展に期待したい．筆者等も，IA法（免疫的ア［10］安部，他：最長径路法を用いた列車運行シミュレーシルゴリズム），やIA法による多峰性関数の全局所解

ョン，情報処理学会論文誌，Vol．27，No．1（1986）．

［11］Fukuda，Mori，Tsukiyama：Immunity，Based探索法などを開発している［11］−［13］．
今後，適用問題としてダイナミックスケジューリングの要求が増えてくるであろう．これは，時々刻々と変化する状況をリアルタイムに把握するインフラが整備されていくからである．

ManagementSystemforSemiconducteorProduction
Line，Arti負cialImmune Systems and Applications，
EditedbyD．Dasgupta，pP．278−289，Springer1998．
［12］森，築山，福田：多様性を持つ免疫的アルゴリズムの提案と負荷割り当て問題への応用，電気学会論文誌C，Vol．113−C，No．10，1993．

7．おわりに［13］K．Mori，M．TsukiyamaandT．Fukuda，
産業システムにおけるOR技術通用システムについApplica−tion ofImmune Algorithm to MultiTOptimizationて述べた．実用化されているシステムを中心に紹介しProblem ，EEJ（ElectricalEngineeringinJapan），Vol．

たが，実用化に至っていないものが一部含まれている．

122，No．2，1998．

1999年11月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（7）593