………ll…lll…ll…‖‖‖‖‖＝‖‖＝‖‖＝‖川l…………………………l…州………lll…llll…llll‖‖‖＝‖＝‖‖‖‖‖‖＝‖‖＝‖冊l…………川…………l…ll刷Il…lll………＝‖‖＝‖‖＝‖‖＝‖‖＝‖‖＝‖‖‖‖‖‖‖‖＝‖‖‖‖‖＝‖‖‖‖‖＝‖‖＝‖冊l

タグより安い数理計画入門
久保 幹雄………………………llll………l………………l…l…＝‖‖＝‖‖＝‖‖‖＝‖‖＝‖‖‖‖‖＝‖‖＝‖‖‖‖‖＝‖‖＝‖‖‖‖‖＝‖‖＝‖‖‖‖‖＝‖‖‖‖‖‖‖‖‖‖＝‖‖＝‖‖…‖l…ll…………………………l…lI……lt……‖‖‖＝‖‖＝‖‖＝‖‖＝‖‖＝‖‖‖‖‖‖‖…

ationsReasearchandManagementScienceシリーズ
登場人物紹介の第8巻に NetworkRouting が最近登場したのだけ

N教授： 元女流物流コンサルタント．現在，大学教授．趣味「お昼寝」
Rさん：某有名メーカー物流部長．倹約家．
好きな言葉「タダより安いものはない．」
暖かい日差しが差し込む午後，いつものようにN教授は教官室でウトウト，もとい，熱心に研究をしていました．そこに，あるセミナーで知り合った某メーカー物流部長のRさんが物流費用削減の相談にやってきました．

「どうも，どうも，先生．お忙しいところ申しわけありません．早速ですが，先日電子メイルでお話したように，我が社では，物流費用の大幅な削減のためにトラック輸送の見直しをしているのですが，どうも問題が複雑で．‥」れど，800ページ近くあるこの大著のほとんどが運搬経路問題という一つの問題とその変形に対する解析に費やされているほどよ．」「でも先生，私も会社にあった物流関連の本をいろいろ調べたのですが，だいたいが哲学とか理念とか，もしくは新聞の切り貼りみたいな事例の紹介ばっかりで‥．，それに先生のご専門の数理的なモデルといえばKantrovichの輸送モデルとか，IBMのVSPXとか，Weberの重心法などが載っていましたが，どうも我が社の問題とは若干異なっているようで… そう，なんと言ったらいいか… あの，大変申し上げ難いのですが… 使いものにならいないというか…」「たしかにそういった教科書レベルのモデルだけで実際の問題が解決できることは滅多にないわね．この分野の教科書に書かれているのは，ほとんど四半世紀前までの研究成果だから，Rさんが誤解されるのも無理はないわ．でもね，Ⅸantrovichの論文は1939年，VSPXのもとになったClarkeとWrightの論文は比較的新しいといっても1964年，Weberの論文にいたっては1929年のものなのよ．」「そんなに昔の話なんですか… ということは，この分野の研究はその後あまり進んでいないということなんですね．」「いえいえ，とんでもない！この分野の研究はここ10年で飛躍的に進んだのよ．専門雑誌を見ていただ

ければお分かりになると思うけど，ものすごい勢いで
図1：N教授とRさん論文や事例が出てきていて，今では数千本の論文が出ていると言われているのよ．もちろん，その数千の論N教授は眠そうな目を擦りながら答えた．

文を全部読んでから来てちょうだいと言っている訳じ「たしか配送計画の問題ね．この間題に関しては実やないわ．問題の概要を教えていただければ，我々専にたくさんの研究がされているわ．たとえば，EIse−

門家がその間題に近い論文を探し出して，それに若干vierという出版社から出ているHandbooksin Oper−のスパイスを与えてあげると言っているだけなのよ．」「はあ，問題の概要ですか．それなら簡単です．数

くぼ みきお 東京商船大学 流通情報工学

十台のトラックの一日のスケジュールを決めるだけな〒135東京都江東区越中島2−ト6e−mail：kubo￠ship2・ipc・tOSho−u・aC・JP

1996年6 月号

んですが，勤務時間とか積載量の制約とかがついてい© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（29）33丁ますし，大きいトラックだと入れないお客様とか，何答を配ってしまうようなものですよ．」

時から何時までに持って来いというお客様がたくさん「あら，ごめんなさい．私が言ったのは実行可能ないるために問題がとても複雑になっているんです．」

ルートの候補のことなの．つまり，−Iヨの連行スケジ

Rさんは黒板に図を書きながら説明をしていたが，ュールになりそうなものを列挙しておくということな

途中で教授が質問をした．の．もちろん全ての実行可能なルートを列挙する必要はなくて，だいたいこんなルートが必要かなと思うものを選ぶだけでいいのよ．」
Rさんは領きながら言った．
「なるほど，それなら分かります．要は，あまり遠回りをせず，かつお客さんの時間指定を守って，かつトラックの重量や容量の制約を守ったような連行スケジュールをたくさん並べておけばいいんですね．我社の場合は簡単です．なんといっても，わがままなお客さんが多いため制限がたくさんついてしまうので，実行可能なルートの数はそれほどたくさんはありませんから．」
図2：Rさんの会社の配送計画「ちょっといいかしら，トラックが配送センターを出た後，何人くらいのお客さんを廻ってから帰ってくるかを教えていただけない？それによって問題の難しさ，言い換えれば使う解法が変わってくるのよ．」
Rさんは持ってきた資料を開いた．

「はい，この間題の場合には多くて4件です．我社
ではかなりの重量物を運ぶので，4件のお客様を廻れば，再び配送センターに戻ってこなければならないからです．」「4件！たった4件ですって？それならルート生成法とよばれる解法がいいわね．この解法は単純だし，既図3：ルート生成法の参考図．ブドウ，リンゴ，オレ存の数理計画のソフトウェアを利用できるので開発もンジ，バナナ，ナスをちょうど一回づつ含むように列短時間でできるし．‥ それで，この解法のためには，（ルート）を選択する．

あらかじめルートを生成しておくことが必要ね．」「えっ？ルートを生成しておくですって？教授のおっしゃっているルートというのはトラックの一日の連行スケジュールのことなんですか？」「そうね．ルート生成法というのは制限がつけばつくほど有利になるのよ．で，実行可能なルートがたくさん生成されたとして，それぞれのルーートのコストを計算する必要があるわね．本来ならル・−トに含まれる「ええそうよ．もっと正確に言うと，ルートというのは 配送センターを出発して，何人かのお客さんをお客さんを与えたときに，どういう順番で廻ってくるかを決める問題は巡回ゼールスマン問題1といって難訪問して，再び配送センターに戻ってくる巡回路，，のことよ．」「だったらおかしいじゃありませんか？だってルートを見つけることが相談に来た問題の目的なんですよ．
それをあらかじめ与えておくなんて，テストの前に解338（30）

1巡回セールスマン問題については，連載講座「巡回セールスマン問題への招待Ⅰ，ⅠⅠ，ⅠⅠI」オペレーションズリサーチ，Vol．39，No．1，2，3（1994）または筑波大の山本芳嗣教授と書いている「巡回セールスマン問題への招待」朝倉書店（1996）を参照してください．

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

オペレーションズ・リサーチしいクラスに含まれる問題になってしまうんだけど，minit3や内点法を使ったLIPSOL4なんていうのがあ

この場合は高々4件のお客さんを回るのだから，全てるわ．でも，やっぱりVanderbeiのLOQO5が二次計の回り方を調べても大した計算量じゃないわね．」

画も解けるし，東京工業大学の小島さん達が発明した「我社の場合にはトラックは全て借り物の車なの主双対内点法を使っているのでとても高速だし，お薦で，連行スケジュールが決まれば，料率表からすぐにめの一品だわね．あら，でもこれは企業で使うときはコストは計算できます．」

有料だわ．それから，読者の皆様のために付け加えて「それじゃ話は簡単だわ，ルートの候補から最も安いものを選択するところがこの解法のミソなんだけていうのもあるわね．これはJava言語で善かれていど，それはこういった問題を解けばいい訳ね．

るので，わざわざダウンロードしなくてもネットワー

最小化：選択されたルートのコストの和

ク経由で機種に依存せず動かすことができるの．これ

ただし：全てのお客さんは何れかのトラックからの主流ね．それから，ツウの間で注目を浴びていでちょうど一回訪問されなければならない．

る半正定借計画（semi−definiteprogramming）のプロ「あれっ？でも教授，数式を使って定式化をしないんですか？数理計画の論文誌を見るとそれはものすグラムSDPAも東京工業大学のftpサイト7でもらえるわ．」「でも，教授．そういったプログラムをダウンローごい数式が載っていますよね．」「ええ，でも本質は式を使わなくても同じよ．それに数式を使うと逆瀬川さん2に怒られるのよ．」「なるほど，でも教授，それで，この間題はどうやって解くのでしょうか？何か問題を変形しただけのようドして我社の複雑な問題を解くためには，ある程度のメモリを装備したワークステーションを用意しないといけないんですよね．ご存じのように昨今の不況で，我社は新しい計算機なんか購入できない状態なんです．せいぜい今あるパソコンを利用して何とかならなな気もしますが…」「そうね．数理計画ソフトウェアを買い込んできて，それに式を入れて解かせるというのが常套手段だわね．そういったソフトウェアも最近はだいぶ安くなってきたみたいだし，パソコンでも十分高速に動くと思いでしょうか？」「それならNEOS8がいいわね．ここではネットワーク上で問題を解いてくれるというサービスをタグで行っているのよ．電子メイルやWWWブラウザで問題を送ってあげると自動的にあちらの計算機で解いうわ．」「いや教授，ご存じにように昨今の不況で物流部門の予算は大幅に削られてしまいまして，新しいソフトウェアを買う予算などとうていありません．」●

おくと，教育用のツールとしてはAnima−LP6 なん「それならフリーのソフトウェアという手もあるけてくれて，答えだけを返してくれるわ．線形計画の他にも確率計画，ネットワーク関連の問題や非線形計画のサービスもしてるみたいね．」「うーん，何度聞いても タダ というのはいい響きですね．あれっ？でも教授，トラックの台数を決めるのど…」

N教授が言いかけると，Rさんは興奮して遮るように線形計画法ではまずいんじゃないでしょうか？だって半分のトラックで運ぶなんて真似はできませんよ．」にしてまくしたてた．

「フリーというのは無料，つまりタグってことですか？私の大好きな言葉です．無料！タダ！！なんていい響きなんでしょう．で，どこにいけばもらえるんです「うーん，確かにそうね．でも半分の積載量を持つトラックを借りてくればいいんじゃないかしら？たとえば，10トン車が半分使うとかいう答えがでたら5トン畢を調達するとか…」

か行列でもなんでも並びますよ．」「いえいえ，バーゲンの目玉商品じゃないんだから「いやいや教授，日本の場合は費用のほとんどが人何も行列に並ぶ必要はありませんよ．たとえば，線形計画のツールなら双対シンプレックス法を使った

3ftp＝／／ftp・uu・net／usenet／comp．sources．misc／volume7
4http：／／math・umbc・eduryzhang／lipsol／

5ftp：／／elib・Zib−berlin・de／pub／opt−net／software／loqo／1．08
2ダンディーなお髭がトレードマークの編集長．本特集は「分かり易くためになり」かつ「数式・プログラミングはダメ」という艶聞が付いている．
1996年6 月号

6http：／／gpu・SrV・ualberta・CaramOnga／informs／taids．html
7ftp：／／ftp・is・titech．ac．jp／pub／OpRes／software

8http：／／www・mCS・anl．gov／home／otc／Server／neos．html© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（31）339

件費ですから，トラックだけを半分にしたんじゃ駄目ですよ．人間も半分に切らなければ…」

図5：ついでに聞いた問題の説明図

図4：線形計画法による解ズ＝喜・運転手半分，トラック半分，荷物も半分．
途中で教授が遮った．

「うーん，そんなことをしたら人事部から文句を言われそうね．となると，やはり変数に整数条件をつけ「要は荷物を積まずに移動する空輸送の距離を最小にしたい訳ですね．」

なければいけないわね．こうなると問題は急に解きにくくなってしまうんだけど，やっぱりフリーのソフト「その通りです．もちろん運転手さんの稼働時間の制約なども付加されますが…」

ウェアがあるわ．たとえば，陰的列挙法もどきを使っ「それじゃ，まずは基本的な部分から解きはじめまたopbdp9とか1p＿SOIvelOなんていうのがポピュラーしょう．要は，配送センターや工場に入ってくるトラッね．1p＿SOlveは名前とは裏腹に混合整数計画問題も解クの台数と出ていくトラックの台数が不均衡だからいけるし，ソースコードで提供されているので結構便利けないのね．」「そうなんです，教授．台数の不均衡を最小費用でなツールね．」「分かりました．これで配送センターからお客さん是正するような方法が簡単に見つかればいいんです

への運行スケジュールは解決しました．早速それを使が，我社のベテランスケジューラーでも複雑すぎてよってシステム開発にとりかかります．で，ついでといくわからんということです．」ってはなんですが，今度は工場から配送センタ、−の問「まず問題を整理しましょう．入ってくるトラック題についてのお伺いしたいのですがよろしいでしょうの台数が出ていく台数より多い地点を左側にまとめか？」て書いて，逆に出ていくトラックの台数が入ってくる「ええ，0Ⅸよ．それじゃ問題の概要からお聞かせ願えるかしら．」

台数より多い地点を右側に書きましょう．すると問題
は左側の地点から右側の地点を最小費用で結ぶ問題

Rさんは再び黒板に図を書きながら説明をはじめた．に帰着されるわね．こういった問題をご存じないかしら？」「ェーと，問題はだいたいこんな感じです．工場か「輸送問題ですね！教授」

ら配送センターへは大型トレーラーで輸送をするのRさんは興奮していった．

ですが，一日に向台分といった輸送指示が来ます．そ「そう！先ほどRさんが使いものにならないとおっれから配送センターから工場や配送センター同士でしゃった輸送問題よ．現実の問題がそのままの形で教も，一日に何台分といった輸送指示が来るときがあり科書に載っていることは少ないけれど，こうやって問ます．さらに…」

題をすこし変形させてやることによって標準的な問題に帰着されることが多いのよ．」

9http‥／／www．mpi−Sb．mpg．de：／guide／staff／barth
lOftp：／／ftp．es．ele．tue．nl／pub／1p＿SOIve
340（32）「いやー，申しわけありませんでした．先ほどの発© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

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

言は取り消します．で，この輸送問題を解くためのタ「こうやって仮想の始点と終点を作ってやって，空輸送の必要な台数分の 物 を流すものとします．それグのツールとかはあるんですか？」「そうね．輸送問題だけに限定されたツールとしてから，仮想の始点から左側の地点に向かう枝にその地は，大型計算機用のFORTRANルーチンくらいしか点から出る必要のあるトラック台数分の容量を付けまないかもしれないけど，再びちょっと変形してフリーす．同じように，右側の地点から仮想の終点に向かうソフトがたくさんある問題に帰着させてあげればい枝にもその地点に入る必要のあるトラック台数分の容いのよ．たとえば最小費用流問題というのをご存じな量を付けます．最後に左側と右側の地点の間に移動にいかしら？」

伴う費用を付ければ出来上がりです．」「だんだん問題を標準的な問題に帰着させるコツが分かってきたみたいですね，Rさん」「まあ，このくらいならなんとか．それで，最小費用流のコードはどこへ行けばもらえるんでしょうか？
もちろんタグのものですが．」「そうね．たくさん出ているみたいだけど，やはり有名な研究者が作ったものが安定していて使いやすいみたいね．たとえば，MITのBertsekasが作ったRELAXは彼のホームページ11に行けばもらえるし，Stanford大学のGoldbergが作ったコード12も定評があるわ．それから，もっと複雑な非線形費用の多品種流問題なんかを解くツール13も出ているけど，この場合には必要なさそうね．」「なるほど，空輸送をどの地点間で行えば費用が最小になるかは分かりました．でも教授，運行スケジュールを組むためには，前の問題と同じように複雑な条件をつけなければいけないんですよ．」「そうね．前と同じように制限がたくさんついているのならルート生成法で大丈夫ね．」
図6：輸送問題を解いて空輸送を最小化する！

「残念ですけど今度の場合は制約がそれほどきつくないんです．それに配送センターの数や工場の数も大●「そういえば昔ネットワーク理論の授業で習ったよ
うな気がします．たしか，始点と呼ばれる地点から，終点と呼ばれる地点へ物を流すときに，彼の容量を超えず，かつ流すときに発生する費用の合計を最小にする問題ですよね．でも，私はパイプに物を流すようなときにしか使えないと思っていました．」「そのへんは想像力の問題ね．今回の問題の場合には，荷物を積まずに移動しているトラックをネットワ分多いし‥．」「そうなるとちょっと無理ね．汎用の数理計画ソフ
トも使い方によっては便利なんだけど，なんでもそれに入れれば解けるってもんじゃないし．‥ そもそも，こういった難しいタイプの組合せ最適化問題というのは，問題に依存した工夫をいかにうまく使うかが解決の鍵になるのよ．たとえば，時間枠が極端にきつい場

合には動的計画法とか，基本構造にちょっとイヤな条ーク上を流れる 物 と思えばいいのよ．」「なるほど．それでしたら最小費用流問題に帰着させる方法が分かりました．」
Rさんは立ち上がって黒板に図を書きながら続け

11http‥／／web・mit・edu／afs／athena・mit．edu／user／d／i／dimitrib／

WWW／home．html
12ftp：／／theory・Stanford．edu／pub／goldberg／opt−COde−info13ppRN（ftp：／／ftp−eio・upC．eS／pub／onl／codes／pprn）またはLSNNO（ftp：／／ftp・bilkent・edtl・tr／p11b／IEOR／Opt／Network）

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

（33）341

件がついているときにはラグランジュ緩和とかいう案

サーチと同じで付加条件には極めて柔軟に対応がで配にね．でも，こういった問題の場合は，現場で使おきるから，複雑な実際問題を解くときにはうってつけうとすると次から次へと付加条件が増えていくので，よ．ちなみに，タブーサーチや関連するメタ解法の詳後で苦労しないためにも専用のメタ解法を開発した

細については 離散構造とアルゴリズムⅠⅤ（近代科学方がいいかもしれないわね．」

社） を参照してくださると有り難いわ．」「メタ解法？何ですかそれは．普通の解法とはどう「また宣伝ですか？度が過ぎると読者の皆様に怒られますよ．」

違うのでしょうか7」「まあ，基本的には何の違いもないんだけど，最近の流行物の近似解法を総称してメタ解法とかメタヒュー1）スティックとか呼ぶのよ．例えば，GeneticAlgo−「ごめんなさい．でも，この本をあちこちで宣伝しないと室田さん16に怒られるのよ．」「閑話休題．でも教授．専用のプログラムを開発すrithmとかSimulatedAnnealing法とかが代表例ね．でるということは，膨大な費用がかかるんじゃないです

も私のお薦めはアダプティブ・メモリー・プログラミか？何度も申し上げましたが，我社は今，非常に切迫ングかしら．」

した状態で‥．」「はっ？何か難しそうな名前ですね．」「でも，多少の出費をしてもそれに見合うだけの費

Rさんは内心，また難しそうな名前でごまかしに来ンサルティング経験から，この事のものをきちんとシたぞ！と思いながら尋ねた．

「で，その アタクシハ・メアリー・プロモデル とステム化すれば，少なくとも10％くらいの費用は削減できると思うわ．それに，Rさんの会社の物流費用というのはいったい何なんですか？」「ちょっと違うわね．英語で言うと adaptivemem−oryprogramming

用削減があればいいんじゃないかしらて■私の長年のコで，日本語に直訳すれば適応型記憶いったら膨大な金額だと思うんだけれど…」「なるほど，損して待とれですね．分かりました．

計画というところかしら．まあ，簡単にいうと探索のなんとか社長を説得してみましょう．最終的に費用削

過去の履歴を積極的に使って探索をすすめるローカル

減ができればタダより安くなる訳ですからね．うー

サーチの変形のことよ．探索を知的なものにするた吟ん，タグより安いか！いい台詞だ．これから私のモッの工夫をたくさん取り入れたメタ解法のフレームワ

トーは タグより安い数理計画 にします！」

ークとでもいうのかしら．」

教授はRさんIこウインクをしながら囁いた．

「要は 何でもあり の解法ということですね．」「私への報酬も忘れずにね！」「まあ，そうともいうわね．昔はタブーサーチとも呼ばれていたの．こっちの方がポピュラーかしら．でも，Glover14がこっちの名前に変えようと言ってい謝辞

いろいろなソフトを検索する際に東京大学の松井知己さんのホームページ17 を参考にさせていただきるし…」「タブーサーチ… すなわち禁断の探索ですか．ますます怪しい名前ですね．」

ました．ここには最適化関連の他の便利なサイトへのリンクが張られているので，国内からはじめて最適化「名前は怪しいけど，実際問題を解くときにはとて関連の捜し物をされる方は，この辺から探し始めるのも便利な方法よ．運搬経路問題みたいな難しい問題にがいいと思います．それから，松井さんはこの原稿のはタブーサーチが極めて有効なの．運搬経路問題に対初稿にもたくさん修正を入れてくれました．あわせてする標準的ベンチマーク問題15 に対する系統的なテ感謝いたします．最後に，椅麗な図を措いて下さった

ストから判断すると，近似解法のベスト5は全てタブ

東京商船大学流通システム研究室の内田麻貴さんにーサーチをベースに作られたものになるって言えば，も感謝します．

その凄さが分かってもらえるかしら．それにローカル
14colorado大学のFredGlover，タブーサーチ教の宣伝係兼総16室田一雄京都大学教授，離散構造とアルゴリズムⅠⅤの編者

帥．
15http‥／／mscmga．ms．ic．ac．uk／info．htm1

17http：／／misojiro．t．u−tOkyo．a占．jp／〜tomomi

342（34）

兼宣伝部長．

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

オ〈ミレーションズ・リサーチ