最適をめざさない最適化 ~ 勤務表作成にて ~ 久保 琢磨 (元総合研究大学院大学) ○宇野 毅明 (国立情報学研究所, 総合研究大学院大学) 2011年9月9日 OR学会中部支部シンポジウム 最適化活用の難しさ (たこつぼ) 応用の難しさ •よく、最適化の研究者から、実用化の難しさの話を聞きます 海洋大K先生: 「いろいろモデルしても現場でうまくいかないことがあるんだよ ね」 名古屋大学Y先生ら: 「それぞれの場面で制約が変わるので、解法の開発がその都 度場当たり的になってね」 成蹊大学 I 先生: モデルも解法もあるのに、なかなか現実に結びつかない.. ある種の解決 •やはり優秀な研究者は解決法を編み出すものです。 海洋大K先生: 著書、多数の書き物による現場、および類似する現場の人 へのノウハウの伝達、啓蒙 名古屋大学Y先生ら: 標準問題の制定と優秀な解法によるツールボックスの作成 成蹊大学 I 先生: 徹底したフィールドワークと、現場での実験による課題抽出 すばらしいの一言に尽きます。でも、なんでこんなにモデル化と 問題解決って、実用化が難しいんでしょう? 精緻な最適化 • OR「研究」では、現実の問題を上手に数理的に表すのが目標 その一方で、「上手すぎる」のも問題 例えば、ナビゲーションシステムで、 + 渋滞発生確率を元に、渋滞に遭う危険率を抑えた最短路 + 信号でつっかえる確率を厳密に扱うモデル + 寄り道したいところの中から1日で行けるところをなるべく多く 選び出して、全てを回るルートを自動で計算 + 景色の良さ、運転しやすさ、店の多さなどを考慮した多目的 最適化での最短路 • たぶん、「そこまでしなくていいよ」 という気分にな ると思います。 最適化モデルの落とし穴 • モデル化を行うときには、必ず現実の問題とモデルの間に乖離 があることを忘れてはいけない + どんなにモデルを細かくしても、「リアル」にはならない お節介になり、準備が大変になるだけ + ある程度までうまくいったら、あとは「数理モデルであること」の 味を出すようにしないといけない 似顔絵が人間の毛穴まで描かないのと同じ。それよりも「イ ラストならではの良さ」を、デフォルメや強調などで出す • でも現実には、「リアル」を追い求めすぎている研究もある • そもそも物理や経済で言うところのモデルは 「システムを簡単 な原理で説明するもの」。複雑なものは範囲外 一般的な解決法 • 一般的な問題(混合整数計画、非線形計画)に対する高速解法 を作る (CPLEX、ニューオプト) • 選び抜かれた「基礎問題」に対して高速アルゴリズムを開発す る (茨木研) • スクリプト言語(python)、モデリング言語を使い、実装を容易に する (AMPLEなど) • 携帯やRFIDなどのデバイスと連携する • 現場に無理を言う • 前に解いたのと似た問題に取り組む (学術研究者?) 見方を変えて最適化を見てみよう • 最適化(モデル)は、システムを改善するための一手段。 最適化をすることが目的ではない - 車を運転して目的地に到着する、という作業の中で、 ナビが関わる部分はほんのわずか - ナビを導入することで、プラニングの手間が減り、運転時間 も短縮されるだろう。でも、ナビの改善による手間の削減は、 全体の作業の中で何パーセントなんだろう? - ルートの精度を上げることより、入出力の便利さ(GPS、 音声案内)などのほうが、大きな効果を上げそうではある • ひょっとしたら、「うるさくないように、音声案内の数を制限して効 果的に案内するにはどうすればいいか」というような問題のほう が重要なのかもしれない 外から見た最適化 • 最適化の研究って、そもそも他分野から見ると - 連続最適化は、点列発生法とその解析 - 離散最適化は、近傍と凸性、あるいはボトムアップ的な集約 - 評価は、多項式性 • 正直、外から見ていたら、そんなことはどうでもいい • 科学として胸を張れるようになるには、もっとグローバルな視点 での大目標が必要 (自然科学の人は、宇宙の心理や生命の神秘、金回りの良さと いった大目標がある) • 自分の研究の基盤として、持っておくのも大事 応用での使えるものは • 最適化を他分野、産業で使うとき、最新研究は意外と役に立た ない。理由は先ほどの 凝りすぎ あと、そのモデル/解法を選ぶのが果たして本当に良いのか どうか、客観的に見てよく分からないという点もある。 • 正直むしろ、利用する立場からすれば、 モデルも解法も簡単なもので良い 20-30 年前の結果くらいがちょうどいい 簡単で扱いやすく、しかも手法の評価が確立されている • 応用分野の人たちと話をする(新しい問題を考える)ときには、 「難しく考えすぎず、論文にならない結果であるほど良い」 小規模ビジネスOR ~ 最適化を広く世の中に ~ 導入の話はなぜ必要か • なぜ、複雑なモデルの話を出したかというと、少しOR分野に閉 塞感が有ると思うので ☆ こういうときには、新しい視点の研究が必要 ☆ 新しい手法、新しい問題設定、新しい応用、原点に戻る、価 値基準の変更、他分野からの問題・技術・人の導入... • ここでも、新しい問題設定について、応用の市場規模やワーク ロード最適化の視点から議論したいと思います ORの問題(市場)規模 • zip則という、世の中の様々なものの分布を説明するものがある 例) 個人の収入、会社の従業員数、論文の共著者数・・ ・ • ORの問題にも、規模(もうけ)と件数の間にこんな感じのものが 有ると思います 古き良きOR: 製鉄、交通、施設配置・・・ 問題規模 (もうけ) パッケージビジネス: SCM、配送計画、 スケジューラ、金融工学・・・ 小規模ビジネスOR: ナビ、勤務表、グループ分け・・・ 件数 ロングテールへのアプローチ + 利益が小さく、人的な苦労が大きい、 + 同じような課題を抱える現場が多い ような問題に対して、解決技術を提供することを目的とする ただし、以下のような点が問題になる + お金がない。デバイスやパソコンの新規導入はできない + 技術力が無く、開発、カスタマイズができない + 導入を考えるゆとりもない (興味もない) + リテラシがない (システムを使いこなせない) + 現場ごとに異なる条件・制約がある + 現場に決定権がない + 件数が多すぎて、マンツーマンでの対応ができない ... こんな状況での問題解決を考えるのが 小規模ビジネスOR 小規模ビジネスOR(SBO)の例 • SBOが想定する現場: 商店、事業所、学校、役所、消防署・郵 便局など公共施設、ご家庭、、、 構成人員が少なく、数が多く、共通した労働の多いところ • 小規模配送計画、勤務表作成、時間割作成、作業割当て、小 規模スケジューリング、クラス分け・グループ分け・席替え、、、 •基本的に貧乏なので、早い安いうまいものでないとどうにもなら ないし、技術的にたいしたものも使えない •現在の状況では、集計ソフト・会計ソフトぐらいの導入がやっと 既存研究のスタイル ① 問題を見つけてくる ② 変数と条件を洗い出して定式化し、アルゴリズムを作る ③ アルゴリズムを実装する ④データをそろえて問題を解く 王道だが、実際にはめんどくさい ③ 個別の問題それぞれにアルゴリズムを考え、実装するのは大変 実装・アルゴリズムの再利用ができない • データ/制約をそろえる/入力するのが大変 ① いい問題がない... • 逆に言えば、② は簡単なわけです (で、ここの研究をしてしまう) SBOにおける最適化 • 一般的に、SBOの最適化では、最適化がボトルネックでないこと が多い 予算がない、運用が難しい、データ入力に時間がかかる、、、 • そういうところでは、「最適化の手法」自体が現実に貢献する比 率がとても小さい • 実際には、予算がない、運用が難しい、データ入力に時間がか かる、といった問題を解決できるようなシステムのほうが役に立つ と思われる • 最適化の手法ではなく、如何に「作業量を最小化できるか」、 という点に注目するのが、SBOにおける大事なところ SBO のまとめ ★ 今まで無視(?)されてきた、小規模なORに取り組む 非常に多くの、共通性を持つ小規模な業務が対象 Web などの情報学分野では一般的 ★ 最適化の外側での困難が多く、業務全体をスムースにして 「作業量を小さく」 する 「総合的な最適化システム」 が重要 ★ 規模が小さいので、大がかりな道具やデータを用いることはナ ンセンス。あるものを簡単に使うことが肝要 ★ モデル&最適化では、多くの業務に共通する問題構造を抽出 することが必要。ある種マーケッティングやフィールドワーク 小規模ビジネスOR @ 勤務表作成 (久保君の研究) 勤務表作成 (以後は久保君の研究です) • 日本に数多く存在する小規模事業所がかかえる標準的な問題 • 事業所で、だれがいつ(どこで)働くかを決める問題 基本は簡単だが、実行可能解を見つけるのが大変。 従業員には休みが必要だし、バイトやパートは限られた 時刻・時間しか働けない • 曜日による必要人数の変動や勤務可能日が主な制約 • 24時間稼働の事業所では、夜勤や準夜勤などを公平かつ無理 なく分配する点も制約になる (連続した夜勤の禁止、夜勤後の休日の必要性など) 勤務表作成の例 • 基本的には、スタッフ×日数の表を埋めることで作業する •日ごとに、 各人の勤務形態 (休みを含む) を決める • 夜勤が連続して いないか、休みは ちゃんと取れているか、 などチェックする 勤務表作成の難しさ • まずは最適化としての難しさを見る + NP完全 + 意外と変数が多い: 人数×日数(シフト数)) + 制約が全体的に影響するので (1日目を変えると、30日目に も影響がある) 局所的に解きにくい + そうはいっても、日ごと、あるいは人ごとの変化はある程度局 所的 ◇ 現実は、人数ぎりぎりのことが多く、頻繁に実行不能になる ◇ いわゆる「解くのが難しい問題」 ◇ 専門解法(メタヒューリスティック等)を作るか、ソルバを使う 現実の例を見てみましょう • とあるホテルの場合(久保君のバイト先) + スタッフは12-3人: 正社員が5-6人で、残りはバイト (こういう状況はそれなりに一般的と思われる) + 正社員が基本的に核となり、それにバイトを付ける感じ + 基本的にぎりぎり。ぎりぎりでないなら、ギリギリになるまで休 みを取ると思われる。 + 作成にかかる時間はおよそ2時間。1ヶ月分をまとめて作る。 休みの希望、バイトの希望などを考慮して、 うまくはまらないところを調整 最適化の貢献 • 最適化に関わる部分を考察してみる + まず、ほとんど実行不能。なので、調整が不可避 + 実行可能解が見つかればいい、というものではない バランス、公平さ、暗黙知などのいろいろなものがあり、 基本的には明文化できない評価項目が沢山ある 最適化でできることは限られている + 運用は比較的楽。勤務表通りに運用して、 突発的な自体には調整で対応 + 入力も楽。一回ベースを作れば、勤務希望日の入力のみ 最適化システムデザイン • 暗黙知や公平性の基準は事業所ごとに変わるので、モデリン グをするのは難しそう • モデリング言語を使っても、定式化は、現場の人には至難の業 「結果を修正する」ということを必須項目としよう • 調整や修正で、2時間のうち1時間以上とりそう データ入力と修正に時間がかかると意味が無くなる • 初期設定が大変だと、負担が大きそう (利用者が減りそう) 操作性・閲覧性が高いシステムであることが第一要件、 モデリングと最適化は2番目の要因となりそう 要件の達成に向けて 操作性・閲覧性を高くする: 洗練されたGUIが必要 データが表形式なので、既存の表計算ソフトを利用しよう ついでに、導入の容易さ、習熟の容易さも得られる 導入を容易にする: インストール、初期設定などの簡素化 表計算ソフトで実装。利用・開発両面で、簡素化が多い 便利な修正機能を盛り込む: 違反の可視化、修正の容易さ 違反してる制約に対応するセルを色づけ 簡便性: データ入力と最適化、修正が短時間で終了する モデル化はあまり精緻にせず、最適化も簡単に終わらせる 必要最低限の入力で動き、残りは追加的に設定可能とする 初期設定 • まず最初に、人数、 名前、職種、必要人員 などを設定。 これはしょうがない 毎月の作業 • 各スタッフの勤務希望を入力。基本的に月次設定はこれだけ 最適化 • ボタンを押したら最適化 修正 • 制約違反を色付けで可視化。修正は入力と同じなので、簡単か つ効率的 より高機能へのステップアップ • いったん慣れてから高次の機能を使う、という使い方が可能 + 推奨勤務形態パタン + スキル・相性 + 勤務形態回数制限 などなど 実利用 • 久保君のバイト先のホテルで実際に使ってもらいました 作成時間が 2時間から 30分。効果有り • ほとんどの時間は修正にかかる時間なので、GUIの占める貢 献は大きそうだ • 修正による暗黙知的評価の導入は、比較的うまくいっているよ うだ 作業になんら抵抗なく、それなりに満足できるものが得られてい るようだ 最適化を目指さない最適化 (久保君の研究) 最適化存続の危機!? • 勤務表が小規模ビジネスOR の代表だと思うと、小規模ビジネ スORのキモは使いやすいGUIをそなえたシステム 最適化(OR)の出番はない!? • しかし、最適化がないと、使いにくいのも事実 自動的に、それなりのたたき台を提供してくれる、 という意味では、必須の機能といえるだろう • それでも、修正やデータ入力など最適化の外側がメインである ことは事実 • ならば、「修正やデータ入力を省力化する最適化」が重要となる だろう 外側を向いた最適化 • データ入力を行わない最適化 無理。 しかし、「データ入力を少なくする」最適化は可能だろう + 細かい制約・項目は考えず、修正に任せる + デフォルト値の活用。最適解に利いてくるところだけ、 後から入力させる (対話型入力システム) + ある程度自動で決める。困るところは指摘してもらえばいい + 修正の履歴や最適解から、データ値を類推する • 基本的なコンセプトは 「新人君にお仕事をお願い」 とりあえずまかせておいて、必要なところだけ指摘すればいい (次回以降、覚えてくれれば、なおいいね。) 勤務表のデータ入力 • 毎月共通の事業所の業務形態、スタッフの基本勤務形態は、 入力しておかないと最適化できない • 各月の、スタッフの勤務希望、ここも重要 (希望は主に休みであり、他の勤務形態になる可能性が高いの で、あらかじめ指定した方がいいだろう) ここは必須であろう • 細かい制約・項目は無視し、これのみで考えるのがいいだろう 修正の容易さを目指す • 修正の容易さはどのように目指せばいいだろうか? どのように修正したいか分からないと、修正のやりやすさが わからない でもそれは、暗黙知だから指定しないという方針だった • やりたいことを知らずに、うまく仕上げるのは不可能では? 無理でしょう • でも、やりたいことにある程度の共通性があるのであれば、「平 均的に修正しやすい解」は存在するかもしれない 修正容易さ、のヒント • I先生から聞いたこと 「現場では、まず考慮制約だけを考えてスケジュールを作り、そ の後必須制約を満たすように変更していくんですよね。」 ある種の貪欲解法をしている。希望のみ満たされた初期解 から出発し、暗黙知と制約を満たすように希望を削っていく • こういうやり方が人間にとって都合がいいのかもしれない (制約を満たす方向に動くだけですむ) • 最適化の場合、制約を破ってからもう一度満たすので、欲しい 解から現在解の距離が遠いかも やってみた。 • ほんとかな、と思ったので、やってみました + 必須制約を重視、考慮制約を重視、両方ほどほどに (つまりいい加減に)最適化した解を準備 + ユーザに、「公平になるように、ちょっと相性条件も加えて、 最適化して下さい」とお願いする (計13人) + 公平さの尺度は、各人の感性に任せる (人々の自然な感覚が知りたいので) + これでいいだろう、と思ったところで終了(ある程度現実的) 結果発表 • 必須、考慮、両方ともほどほどに考慮した解が、もっとも扱いや すいようです (正確には、必須制約を優先すると時間がかかる、 考慮制約を優先したやつはだいたいよい、両方考慮した やつは短い時間(考慮優先より1割減)でできる、という感じ) • 制約に張り付くよう、きっちりと最適化をしたことが、「その制約を 守って他の解に変更する」ということを難しくしているようです • ということは、ある程度制約から離れた解を見つける、 というスタンスが重要なのかもしれない 制約伝搬 • 一般に、ある変数の値を変更すると、いくつかの制約が満たされ なくなる • それらの制約を満たすべく、多の変数の値を変更すると、さらに 多くの制約が満たされなくなる、という具合に、制約違反が伝搬し ていく 制約伝搬、という • こういうことが起きなければ、解の修正はある意味容易 制約伝搬が起きないような最適化を目指すべきかも • と具体的にどうするか、なかなか難しい 制約が利いてる変数を限定し、ブロック化できればいいか? ぎちぎちに最適化しない、というのは、一つの解答、かな? 最適化を目指さない、というスタイル • 厳密に評価関数を最適化しない、あるいは評価を厳密に定義し ない最適化は、このごろけっこう見かけるし、重要である • 例えば、ページランクやリコメンデーション。目的ははっきりして いるが、数理的にははっきりしていない。現実のデータやモデルか ら、ある程度頑強な評価値 を出すことを基軸としている (評価値を基盤にしていろいろなことを考えている) • 機械学習では、オーバーフィッティングを避けるため、わざと最適 化を途中でやめている 制約に張り付かないこと」 が評価値になっている まとめ 提言: 最適化研究、モデルや手法を突き詰めること以外の方向性 があると、この先の研究も面白いのではないか • 応用を見る場合に、市場(顧客)の量や質という点や、全体的な 傾向をとらえたモデリングがありえるのではないか 小規模ビジネスORの提案 • 勤務表作成での、小規模ORの実践 + 最適化をシステムのごく一部と位置づける + ごりごりと最適化をせず、修正を容易にする + 修正やデータ入力を省力化するような解を求める
© Copyright 2025 ExpyDoc