「問題解決エンジン」群とモデリング茨木 俊秀
Illlll‖＝‖‖＝＝‖‖‖＝＝‖‖＝‖‖＝＝＝‖＝‖‖‖＝‖‖‖＝‖‖‖＝＝‖‖＝＝＝＝＝‖‖‖＝＝‖‖‖‖‖‖‖‖＝‖＝‖‖‖＝‖‖＝‖‖‖‖＝‖‖＝‖‖＝‖‖＝＝‖‖＝‖‖‖‖‖‖‖‖‖‖＝＝‖＝‖＝‖附Il…llll…lll…＝＝‖＝‖‖‖＝＝‖＝＝‖‖＝‖‖冊Il……ll…lll……ll…lll……lll

現1．はじめに最適化モデリングというと，まずLP（線形計画）やIP（整数計画）による定式化が思い浮かぶ．LPは実相化されてすでに久しいし，IPも最近では優れたエンジンK● ／商用パッケージが出回るようになり，広く使われるよ標準問題Kうになっている．人上知能の分野ではCP（制約プログラミング）の枠組みが提唱され，実用化が進んでい

図1標準問題による閃題解決る．

組合せ最適化に興味を持つ研究者として，これらの恩恵に大し、に浴しているのであるが，しかし同時に，るので，その全体像を紹介し，利用に当たっての問題点，特にモデリングの部分について述べてみたい．

これらだけでは十分ではないという印象も払拭できな

2．標準問題のリストとモデリングいでいる．この事情をもう少し詳しく説明すると，まず，これまでに手采用した標準問題のリストを与え

NP完全性の理論によれば，ほとんどすべての組合せ問題は（つまリクラスNPの問題は）一つのNP困る．

雉問題（例えばIP）に定式化できることが分かって

1．制約充足問題（CSP）

いるが，定式化に際して多数の変数や制約条件を導入

2．資源制約プロジェクトスケジューリング問題

しなければならないとか，定式化自体は簡潔であって（RCPSP）も解くのが容易でない，という理由で実用的には使え

3．配送計画問題（VRP）ないことが結構あるからである．同様な感想は，応用

4．2次元箱詰め問題（2PP）の現場でORを利用しておられる実務家の方々からも5．一般化割当問題（GAP）

しばしば発せられている．

6．集合被覆問題（SCP）

広い範囲の組合せ問題を最適化手法によって解決す7．鼓人充足可能性問題（MAXSAT）

るにはどうすればよいだろうか．少々面倒でも，次の以上に加え，代表的な標準問題であるLPとIPにようなアプローチ以外にないというのが，いろいろなついては，商用パッケージの利用を前提にしている．

試みを経て得た私の結論である［1］．すなわち，いくそれぞれの標準問題は，多様な制約と目的関数を許容つかの標準問題を設定し，それらに対して「問題解決できるよう，柔軟な構造に設定されている．また，解エンジン」を開発しておき，解くべき問題に適した標を求めるアルゴリズムはすべてメタヒューリステイク

準問題のエンジンを利用するという図1のスキームでスのアイデアに基づき，性能向上のために問題構造をある．この日的に，ここ10年近く京都大学の柳浦睦利用したさまざまな工夫を加えて実現されている（こ憲さん，野々部宏司さんらとともに，学生たちの協力

れらの詳細は，科学研究費の報菩書［2］，あるいはそを得て，問題解決エンジンを開発してきた．最近，よの中に引用されている文献をご覧いただきたい）．

うやく実用的に使えるレベルに近づいてきたと思われいばらき としひで

上記の標準問題はいずれも理論的にはNP困難であって，厳密解を求めるのはきわめて困難と考えられ関西学院大′、r捜Ⅰ二学部ている．そのため，問題解決エンジンはすべて近似解〒669−1337 三田市サ園2−1を求めることを目的に作られている．現実の場では，2005年4Jl号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（11）229近似解で十分であることが多く，また，得られる近似もう一度強調しておくと，ここではモデル化すべき解の精度はきわめて高いので，開発された問題解決エ標準問題があらかじめ決まっているわけではない．つンジンを用いると，上記の標準問題はすべて現実的なまり，どの標準問題を選ぶかという問題と，その標準意味で解けると言ってよい．この認識は重要である．

問題へどのように記述するかという二つの問題を解決さて，問題解決エンジンが手に入ったとして，よくしなければならない．この二つは独立ではなく，相互ある質問（FAQ）は次のようなものであろう．いまにフィードバックを重ねつつ次第に固めていくという会社で解決しなければならないある課題を抱えていて，面倒なプロセスである．

組合せ最適化問題の一種ではないかと思っているが，それをどのように定式化してよいか分からない．定式3．標準問題へのモデリング化しなければ折角の問題解決エンジンを使うことがで

3．1ルート決定問題−VRPとSCPきない．どうすればよいか．

飛行機（列車，バスなど他の交通でもよいが）の操つまり，モデリングをどうするかという質問であっ縦士の勤務スケジュールを考える．一人の操縦士に対て，モデリング支援システムのようなものがないか，し，A空港を出発する便をB空港まで操縦した後，という質問もよく受ける．ある程度問題の範囲を限定

B空港からC空港までの便を操縦し，さらに…といして，例えば，スケジューリングで，さらに，例えばう具合に1勤務のスケジュールが決まる．このとき，多段工程に限定して考える，というのであれば，その連続する二つの便は，同じ空港に着発するものでなけ

目的に役立つモデリングツールを作ることは可能であればならないとか，着発の時間の先行関係を満たすもろうし，現にそのようなシステムも作られている．しのでなければならないという条件，さらに，安全上やかし，ばくぜんと組合せ最適化の範疇にあるといった勤務条件の考慮から，連続する便の時間間隔，1勤務問題を理解して，それに適した標準問題を選択し，定の総時間の制約などさまざまな条件が入る．さて，こ式化するというプロセスは，メタ・モデリングとでもの航空会社が保有している々人の操縦士ですべてのいうべき高度な思考を必要とし，問題領域の専門家と便を飛ばすためのスケジュールを組みたい．

アルゴリズムの専門家の両者が知識と経験を生かして協力しなければ成功しないだろう．

それぞれの便を点で表すと，一人の操縦士の勤務は，これらの点をつなぐ1本のルートと考えることができ逆に，だからモデリングは面白いともいえる．あるる（図2）．簡単のため，すべての操縦士はデポと呼先生が次のようにおっしゃっていたことを思い出す．

ばれる特別な点から出発し，同じデポに戻るとする．

「もし，世の中すべてが線形システムででき上がってさて，どの便にも少なくとも一人の操縦士が必要だかいるのであれば，それらを数学的に正確に記述し解明ら，この問題は，すべての点をカバーするように，々することができるが，そのかわり単純で予見できる現本のルートを構成する問題である．ただし，ルートは象しか生じないので，面白くも何ともない．幸いなこ

自由に作れるわけではなく，ある点（便）から次に訪とにこの世の中は大変非線形にできていて，いつまで問する点（便）は，先に述べたさまざまな制約を満たたっても未知な現象が残っている，だから退屈しないすものでなければならない．のである．」

この間題を解くために，二つのアプローチが考えら

組合せ数学の対象は，非線形の極限とでもいうべきれる．その一つは，一人の操縦士の勤務ルートとしてものである．NP完全とかNP困難という概念が，こ可能なものを，勤務に関する条件を考慮して，あらかれらの問題は一筋純ではいかないということを述べていると理解すれば，だから面白いのである．これら面
白い標準問題を相手にモデリングを考えるのは，当然もっと面白いにちがいない．
しかし，私にはモデリングの面白さについて総合的に述べる力はないので，次では，実際に標準問題へのモデリングを行った経験のなかから，定式化に少々工夫を要したという話題を二つ，簡単に紹介して，お茶を濁させていただく．

図2 全点をカバーするルート集合
オペレーションズ・リサーチ

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

じめすべて列挙しておき，それらの中から々個を選結局，どちらの標準問題を採用するかの判断には，ぶという方法である．もちろん，選ばれたルートを合一方では解くべき問題の詳しい知識がまず必要であり，せるとすべての便に操縦士が搭乗していなければなら

他方，定式化された標準問題のエンジンの動作を理解ない．これは，各ルートをそれが訪問する点の集合としておかなければならない．そのためには，現場で解捉えると，選ばれたルート集合の和集合が全集合にな決すべき問題を正確に把握している実務家と，アルゴるという条件である．すなわち，標準問題の中でリズムの動作をよく理解しているエンジン側の専門家SCP（集合被覆問題）に定式化できて，SCPエンジが協力して，知識と知恵を出し合う，という共同作業ンを用いて解くことになる．

が不可欠である．

もう一つのアプローチは，々本のルートを，勤務条3．2 巨大構造物の組立−RCPSPの意外な利用法件を考慮しつつ直接構成するものである．これは，平

RCPSPはn個のジョブを，それぞれのジョブが要面＿l二に置かれた顧客を点で表し，々台のトラックです

求する資源量（機械，作業員，材料，電力，経費なべての顧客へ荷物を配送するとし−う配送計画問題

ど）の制約を満たすように，時間軸上に配置する問題（VRP）と同じタイプであって，やはり，VRPエンである．多くのスケジューリング問題は，この形式にジンを適用することができる．ただ，各ルートの構成記述できるので，きわめて利用価値が高い．ここでは，は，先に述べたように勤務条件からくる制約を考慮し標準的なRCPSPの利卿列ではなく，定式化を工夫すなければならないため，ルート探索に工夫が必要であるとより広い応用があるという観点から，次の例を紹る．

介する．
この二つの標準問題のどちらを使うかは微妙なとこ

細長い工場内にいくつかの構造物（ブロック）を一ろであり，その判断によって大きな違いが生じる可能列に配置して，それらを完成させるという作業を行っ性がある．一般的に述べれば，ルート構成の際の制約ている．各ブロックの長さ（工場は細長いので，1次が厳しく，実行可能なルートの個数がそれほど多くな元の問題と考えられる），完成までの作業目数と必要ければ，SCPに定式化したときの規模が大きくない

資源量はブロックによって異なるが，あらかじめデーので，SCPの利用が有利であり，逆の場合は，VRPタとして与えられている．ブロックは大きく重いので，が有利になる．これは，問題のサイズからの考察とと一度ある場所に置くと同じ位置に留まるが，完成するもに，VRPのアルゴリズムが，ルートを少しずつ修と工場から出て行く．さて，すべてのブロックを鼓少正して改良していく局所探索のアイデアに基づいてい日数で完成するには，どのブロックをいつどの位置にるため，ルートの制約条件が厳しければ，近傍解の中置いて作業すればよいだろうか，そのスケジュールをに改良解を見つけることが困難になって，探索性能が作れ．
この間題は，ブロックをジョブと見なせば，標準問落ちるという理由もある．

交通の勤務スケジュールについて，過去の例を見る

題RCPSPにほぼそのまま定式化できる．しかし，と，SCPによるアプローチが多いようである．このRCPSPにはブロックの位置を決めるという機能は含場合，SCPエンジンの適用の前に，実行可能ルートまれていない．そこで，他の資源に加え，長さも資源の生成を行うルーチンを用意しなければならない．ルの一つと考えて，工場の全長⊥を消費するという考ート数があまりに多くなると，その中で重要なものをえで，RCPSPにかける．ただし，ブロックの配置に選択するための補助ルールの導入も必要である．簡便はある程度のすき間が避けられないことを考慮して，法として，ランダムに適当数のルートを選ぶという方0．9⊥程度に割り引いた長さを実際の全長と考える．

法も用いられるが，近似精度が落ちることは避けられこの計算で得られたスケジュールでは，長さ資源の和ない．この部分をどのように作るかでSCPアプローは0．9⊥以内に入っているが，ブロックを置く位置はチの成否が決まってくる．VRPのア7Cローチでは，まだ決まっていない．そこで，もう一度RCPSPを使局所探索にルートの制約条件をどのように組み込むかうが，今度は1次元工場における配置位置を示す座標がポイントになる．通常は，制約の違反度をペナルテを，スケジュールの時間軸と考えて，この時間軸に沿ィの形で組み込みつつ探索を進めることになるが，探って再スケジュールするのである．この時，各ジョブ

索性能が落ちないように，具体的なペナルティの形をの元の時間軸での位置が動いてはならないが，各位置慎重に決定しなければならない．とジョブに固有の資源を導入することによって，この2005年4Jjり・© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（13）231

l 仔細l 昏醐→ 時間軸

一−−→一 時間軸

H曽恕一

図3 RCPSPによるスケジュール

制約をRCPSPの枠内で実現できるというところがみくというのは，問題解決エンジンが高性能をだせるよそである．

うにモデル化するという意味でもある．改めてモデリ

図3の左に1回目のRCPSPの解を，右に2回目のングの重要さと難しさを実感している．

それを示す．1回目の解では，ブロックの上下位置はここでは，紙数の都合で二つの例しか書けなかった

決めていないので，工場の全長からはみ出ているものが，問題解決エンジンにおけるモデリングの役割を幾もあるが，2回目の計算でブロックを上下に調節して分でも伝えることができただろうか．究極的には，モ（左右には動かさない）うまく収めているところが見デリング作業の支援システムを作って，このプロセスてとれる．すなわち，RCPSPの適用を，変数の取りの簡略化に役立てたいものであるが，すでに述べたよ

方を工夫しつつ2度行うことによって，直接的には扱うに，今直ちに構築可能とは考えていない．しばらくえない問題を解いたという例である．

は，典型的なモデリング例を積み上げて，理解を深めるという努力を続けるつもりである．

4．むすび

参考文献

我々の問題解決エンジン群も，アルゴリズムの改良の結果，実用的に結構使えるということが認識されて［1］茨木俊秀：「問題解決エンジン」への通，応用数理，きたせいか，すでに何人かの研究者の方々，数社の企

Vol．14，No．1，pp．67−70，平成16年3月．

業で利用いただいている．なかでもCSPとRCPSP［2］茨木俊秀：メタヒューリステイクスによる汎用問題解は，汎用性が高いこともあって，利用例が多い．しかし，そのすべてが成功しているわけではなく，やはり，決システムの構築，科学研究費基盤研究（B）（2）報告書，平
成16年5月．

モデリングがうまく行かないと駄目である．うまく行

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

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