バックナンバー ( 2015 Vol.2 ) 2015 年 3 月 18 日 発行
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム 最適化メールマガジン http://www.msi.co.jp/nuopt/ 2015 Vol.2 ( 2015 年 3 月 18 日 発行 ) -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= 数理システム 最適化メールマガジンでは，数理計画法パッケージ 数理システム Numerical Optimizer をはじめとして，最適化に関する様々 な情報やご案内を提供していきます． ++++ [目次] ++++++++++++++++++++++++++++++++++++++++++++++++++++++ ■ <トピック> OR 学会 発表・出展のお知らせ ■ <トピック> 数理計画用語集 用語追加 ■ <セミナー> Numerical Optimizer セミナーのご案内 ■ < tips > 数理計画問題の豆知識（第 18 回） ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ****************************************************************** ■ <トピック> OR 学会 発表・出展のお知らせ ****************************************************************** 3 月 26 日・27 日に東京理科大学神楽坂キャンパスで開催される日本オペ レーションズ・リサーチ学会 2015 年春季研究発表会にて出展を致します． 学会ご参加の方は是非とも出展ブースにお立ち寄りくださいませ．今回の 発表会では当社から下記の発表を致しますので，併せてご紹介させて頂き ます． ◆ 非線形半正定値計画問題の各種アルゴリズムについて NTT データ数理システム 山下浩 いわゆる非線形 SDP 問題の解法について，1 時間のチュートリアル講演を します．SDP 問題の持っている基本的な性質から始まって，標準的アルゴ リズムの考え方について，なるべく分かりやすく解説したいと思っていま す．1 時間の時間を頂いたのですが，何とかその時間に収めるべく準備中 です．この機会に，この分野への研究者の新たな参入と，関連しそうな問 題を抱えている方々の認識を新たにする，という結果になれば幸いです． ◆ 「式」になっていない問題を解く:数理計画法の挑戦 NTT データ数理システム 田辺隆人 実務的な問題解決の現場では要件が「式」として与えられることはありま せん． 動的なプロセスを通じて定式化を掘り出す方法，実務的な制約を読んで式 にする方法など計算機環境と人間系の緊密な連携が必要になります． スケジューリング， 積み付け，プロ野球 CS ナンバー計算などの実例を 通じてそれらの技法について具体的にお話します． ◆ The randomized algorithms for optimal long-short portfolios using semidefinite programs NTT データ数理システム 藤井浩一 NTT データ数理システム 原田耕平 SDP 緩和を利用した乱択アルゴリズムによって，ロング・ショートポート フォリオモデルの実行可能解を高速に求めます．RNUOPT を用いると簡潔に 実装できることも当日発表にて示します． ◆ S^4 Simulation System の開発 5 ～意思決定を含むモデルの強化学習による最適化～ NTT データ数理システム 成瀬俊輔 NTT データ数理システム 雪島正敏 シミュレーションモデルには意思決定が含まれる場合があり，システムを 最適化する場合には意思決定ルールの最適化も必要とします． 意思決定ルールの最適化方法として強化学習による最適化が考えられます． 強化学習による最適化機能を用いたモデル例や実験結果をご紹介します． （佐藤 誠） ****************************************************************** ■ <トピック> 数理計画用語集 用語追加 ****************************************************************** 弊社数理計画部では「数理計画用語集」を公開しています． http://www.msi.co.jp/nuopt/glossary/index.html 今回は数理計画用語集の中でもアクセス数の多い用語の内容をさらに充実 させています．是非ご一読ください！ ＜新語＞ ・記憶制限 BFGS 法 ＜改修用語＞ ・BFGS 法 ・KKT 条件 ・ラグランジュ緩和法 ・二次計画問題 ・列生成法 ・浮動小数点例外 ・確率的勾配降下法 ご意見，ご要望等ございましたら，お気軽に用語集編集委員会 nuopt-glossary@ml.msi.co.jp までご連絡ください． （村山 昇） ****************************************************************** ■ <セミナー> Numerical Optimizer セミナーのご案内 ****************************************************************** ---- [ Numerical Optimizer 定例セミナー開催日程 ] ---------------- ・ 4 月 14 日 (火) 13:30 ～ 16:30 最適化セミナー（体験・事例紹介） ・ 4 月 15 日 (水) 13:30 ～ 17:00 スキルアップセミナー・入門編 ・ 5 月 28 日 (木) 13:30 ～ 16:30 最適化セミナー（体験・事例紹介） ・ 6 月 16 日 (火) 13:30 ～ 17:00 スキルアップセミナー・実践編 会場 : (株) NTT データ数理システム セミナールーム （東京都新宿区信濃町 35 信濃町煉瓦館 1F） アクセスマップ http://www.msi.co.jp/msi/location.html ------------------------------------------------------------------ お申込み・詳細は下記のページをご覧ください． http://www.msi.co.jp/event/index_nuopt.html （中野 雄介） ****************************************************************** ■ < tips > 数理計画問題の豆知識（第 18 回） ****************************************************************** 今回の話題は Vehicle Routing Problem (VRP) です．VRP については 本コーナーでも以前に [1] でご紹介させて頂いておりますが，今回は特 に，VRP の有望な解法である，ALNS についてご紹介します．非常に難し い問題と知られている VRP ですが，とても単純なヒューリスティックを 使うことで，実用に耐える良好な解を短時間で得られる，という妙味に ついてお伝えできればと思います． VRP は，一口で言えば，荷物の最適配送問題です．荷物が保管されている 拠点（普通は 1 箇所）があり，そこから複数の車両を使って客先へ荷物を 運搬する際，総経路長などの各種コストを最適化するのが目的です． VRP は主にロジスティックスを中心として，非常に応用の広い問題ですが， 一方で，非常に難しい問題としても知られています． 技術的には，解が与えられた場合にそれが最適か否かを判定することさえ， 絶望的に難しいこと（NP 完全）が知られており，そのため，厳密解法に 基づくソルバーを用いて最適解を得るという方針はあまり有望ではありま せん（実用に耐える時間で最適解が得られる保証がありません）． それに加えて，実務上は上記のような単純な問題設定だけではなく， - 複数拠点（Multi Depot VRP） - 車両の稼働時間や荷物の配達指定時刻（VRP with Time Window） - 車両の容量（Capacitated VRP） - 荷物の割当可能な車両に制限がある（クール便など） - 顧客からの荷物の引取も考慮（VRP with Pickup and Delivery） のような要件も考慮するのが普通です．また最適化も， - 総経路長の最小化 - 総稼働時間の最小化 - 稼働車両台数の最小化 - 配車コストの最小化（むやみに大きい車を動かさないなど） などを複合的に考慮して行う必要があります． したがって，VRP を実務問題として解決する場合には，要件に応じた何ら かのヒューリスティックを設計し，最適でなくとも十分に良い解を得るこ とを考えることが現実的となります． 最新の研究によれば，Adaptive Large Neighborhood Search（ALNS）と いう手法（[2]）が非常に有効であることが報告されています． ALNS のベースとなっているのは LNS（[3,4]）というとても単純な戦略で， [LNS] 1. 何かの方法で初期配送路を決める 2. 現在の配送路から一部の荷物を除去する 3. 2 で除去された荷物を配送路へ再挿入する 4. 配送路が改善されていなければ除去前の配送路へもどす 5. 2 へもどる というように，破壊・修復を繰り返すことで配送路を改善していきます． 2 の除去の方法としては， - 荷物をランダムに選択して除去する - 除去すると最もコストの下がる荷物を選択的に除去する - 稼働中の車両を選択し，そこに割り当てられた荷物を全除去する など，様々な方法があり得ます． これらを除去アルゴリズムと呼ぶことにします． 一方，3 の挿入の方法についても， - ランダムな位置へ挿入する． - コストが最も増大しない位置へ挿入する． など，色々な方法があり得ます． これらを挿入アルゴリズムと呼ぶことにします． LNS を動作させるためには，はじめに初期配送路を決める必要があります が，手っ取り早い方法としては，空の配送路に対して挿入アルゴリズムを 適用する，という方法があります． LNS も VRP に対して良好に動作しますが，若干効率化の余地があります． 例えば，2, 3 のところで使用する除去・挿入アルゴリズムとして何を選べ ばよいかについては LNS には基準がありません． もしもよい選択方法があれば，もっと効率的に改善が行えるはずです． どのような除去・挿入アルゴリズムが有効かは，実際のところ問題やデー タに依存するため，これらに応じて適応的に選択できるように微修正した ものが ALNS です．ALNS のアルゴリズムは以下になります． [ALNS] 1. 何かの方法で初期配送路を求める 2. 除去・挿入アルゴリズムの選択確率を適当に初期化する 3. 除去・挿入アルゴリズムを現在の選択確率にしたがって選択する 4. 3 で選択された除去アルゴリズムで，現在の配送路から荷物を一部 除去する 5. 3 で選択された挿入アルゴリズムで，除去された荷物を配送路へ 挿入しなおす 6. 配送路が改善されていれば，4, 5 で使用された除去・挿入アルゴ リズムの選択確率を増加させる． 7. 配送路が改善されていなければ，除去前の配送路へもどす 8. 3 へもどる LNS よりも少し複雑に見えますが，除去・挿入アルゴリズムに対して選択 確率を付与しておき，それを解の改善の成否に応じて変動させる点が異な ります．こうすることにより，除去・挿入アルゴリズムが適者生存されて ゆき，有効なものほど高確率に選択されるようになります． 弊社でもこの ALNS を実装し，複雑な要件を含んだ VRP に対して適用し た実績があります．実務上の標準的と思われるサイズの問題（荷物，車両 が数百）でも，短時間（数十秒から数分程度）で非常に良好な解を得るこ とができ，その性能に驚きました． このように単純な方法ですが，それが本来非常に難しいはずの問題にとて も良く効くというのが面白いところです．さらに，シンプルであるがゆえ に，複雑な実務的要件も比較的素直に組み込めるという利点もあります （実用上はこちらも非常に重要なポイントです）． いかがでしたでしょうか．そもそも数理計画問題として記述してしまえば 解けてしまうような問題の場合，Numerical Optimizer ならモデリング言 語 SIMPLE で問題を記述さえすれば後はよしなに解いてくれるので，問題 の記述方法にさえ少し慣れてしまえば何も難しいことはありません（これ で済む問題も非常に多いです）． そうでない問題の場合でも，今回ご紹介したように，適切な道具を選ぶこ とで，実用に耐え得る良好な解を効率的に得ることができる場合もありま す．どのような道具が適切かは問題にも依存するので難しいところですが， 弊社でも最新の研究を常時チェックしておりますので，皆様のお役に立て ることもあるかもしれません． 以上，皆様のご参考になれば幸いです． 参考文献: [1] 弊社最適化メールマガジン・バックナンバー（2011 Vol.6） 「<トピック> 数理計画の豆知識（第 8 回）」 [2] S. Kritzinger et al., "Adaptive search techniques for problem in vehicle routing, Part I: A survey", 2014 [3] P. Shaw, "Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems", 1998 [4] D. Pisinger, S. Ropke, "Large neighborhood search", 2010 （白川 達也） ================================================================== ※ このメールは，展示会・セミナー等で名刺交換をされた方，過去に 数理システム Numerical Optimizer に関するお問い合わせを頂いたこ とのある方，および本メールマガジンの配信を希望された方にお送り しています． ※ バックナンバーはこちらから御覧頂けます． http://www.msi.co.jp/nuopt/mailmagazine/index.html ※ 本メールマガジンは等幅フォントでお読みになることを推奨します． ※ 今後このメールマガジンが不要な方は，誠にお手数ですが，「メール マガジン配信停止」という件名のメールを nuopt-ms@ml.msi.co.jp にお送りください．なお，反映作業の都合上，数日間は旧情報にてメー ルが届く場合がございます．なにとぞご容赦ください． 発行：株式会社 NTT データ数理システム << 数理システム Numerical Optimizer >> 担当 東京都新宿区信濃町 35 番地 信濃町煉瓦館 1 階 tel : 03-3358-6681 e-mail : nuopt-info@ml.msi.co.jp ==================================================================