最適化一口話

仕事として数理最適化を実践している立場から、その中身や可能性について概説しております。

「厳密さ」は人を惑わす(ビーズ問題その1)

ここは手作りアクセサリーの店。 ビーズの残りがなくなってきました。良く使うタイプなので多めに、予算 6000 円で調達します。 調達先の候補をネットショップでざっと探してみると次のような感じです。

店舗 価格(一袋あたり) 分量
A 250円 100個
B 1000円 約400個 (70g)
C 1500円 約600個 (105g)

店によって袋の大きさは様々ですが、ビーズの単価はどれも似たりよったりで、 どこで買うのでもよいかなあというところですが、 ここに、何事もきっちりとしないと気が済まない今回の主人公 M 君が登場します。 そもそも分量の「約」というのは何事だと、サンプルを取り寄せて数え始めた彼を、 誰にも止めることはできません。結果、

B店の袋には 406個、C店の袋には 610個入ってた!

そうな(これがその店が売っているすべての袋に通用すると思い込んでしまう彼の単純さはとりあえずおいておきます)。せっかく苦労して得たデータなんだし有効に使わないと意味ないっす。 と彼、最近どこかのブログで読んだ数理最適化という手法を使ってこれを解くことにしました。 A、B、C から一袋購入すると、ビーズと費用が「セットになってやってくる」。 こう考えるとこれは 「重ね合わせ」タイプ のモデルです。

f:id:optimizationTanabe:20160623002617p:plain

さて、M君、自分で苦労して得たデータを入れて解きました。 答は「C店の袋だけ4つ買う」です。 データ取りも、定式化も慣れない中あんなに苦労したのになんだか面白くない。 A,B,C 全部取り混ぜて買う、とか苦労に見合った思いもよらない答が出ればよいのになあと思いつつふと気がつくと机の上にビーズが一個転がっているのを見つけました。 どうやら B店の袋にあったのを一つ数え上げ忘れていて、B 店の袋のビーズの個数は都合 407個 だったようです。きっちりした彼のことなので、最適化のデータを 406 から 407 に変更して、数理最適化をやりなおしてみました。 するとどうでしょう、がらっと答が変わってしまいました。 沢山買っていた C 店の袋は一切無視して、「B 店の袋を6袋」という答です。 入力はわずかしか変えてないのになぜこんなことが起きるのかと彼はPCを前に首をひねっています。

M 君、自分の業務に数理最適化を積極的に役立てるのはとても素晴しいのですが、ちゃんとした予測を立てずに計算を走らせるだけでは機械が出す結果に振り回されてしまいます。最初は結果を想像しながら手を動かしてみて計算機の答を「評価」してやるべきですね。 B 店の袋と C 店の袋で1円あたりで買えるビーズの個数を計算してみましょう。最初の設定だと B 店の袋では 406個/1000円 = 0.406個/円なのに対して、C店の袋では 600個/1500円 = 0.4067個/円と僅かに多い。 じつは数理最適化がC 店の袋をすべて買うべしとしていたのは、この差に反応してのことでした。 その差がB 店の袋にビーズが一個余計に入っていると逆転されてしまうくらい僅かだったので、 B 店の袋のデータを修正すると今度は B 店の袋をすべて買う、という答になった、というわけです。 そんなに固いこと言わずにC 店の袋でもそんなに悪くないんだから派手に変える必要ないじゃないかね? それは人間の適当な(実は別の判断基準を導入している)発想というもので、 数理最適化は一旦 C 店の袋よりも B 店の袋の方がコストパフォーマンスが良いと判明し、 B 店の袋で予算を使い切れるとわかったら、C 店の袋を一つも買いません。 そうでなければ、「最適解を見つけよ」との命令に忠実でないことになってしまうから。

非常に単純なケースで説明しましたので、 何をあたりまえのことを言ってるんだと思われるかもしれませんが、 これは頭で追い切れないくらい複雑な問題についても起き得て、 時折数理最適化ユーザーを惑わすので注意が必要です。

それほどデータは変化させてないのに・・・

  • 「先月はこのポンプが動いてたけど、今月は全く動かない結果になったぞ!」
  • 「先月まで掃除ばかりしてた人が今月は掃除を全くやらなくなったぞ!」
  • 「ポートフォリオががらっと変化したぞ!」

一体どうしたんだ?といった具合。

これは多くの場合拮抗した結果(目的関数値)を出す、様相の違う答が複数存在することを示唆しています。 ビーズ問題の場合、「B店のみ買う」「C店のみ買う」、という全然違った二つの答がもたらす結果の差は、二千を超えるビーズの個数にして数個でした。 この二つの答がいわば「水面下」で争っていて、 数理最適化は僅かなデータの差で一番に来たものを拾いあげて報告するので、 結果だけ見ているこちらはびっくりさせられるわけです。

掴むのは常に1番の答だけで 2番を掴まない、 というのが数理最適化アルゴリズムの「精度の良さ」とか「厳密性」というもちろん誇るべき性能ですが、 選ぼうとする答のもたらす結果が僅差である場合、 ときに人を惑わすことがあるのは知っておいて頂いて良いことだと思います。 特にスケジューリングなどに多いのですが、実務の現場でははっきりした良し悪しがつけられない答が大量に発生するので、厳密な1番に拘らずにキーワード検索のように最適解の周辺の答 2,3 個をなんとなく表示してくれている方がよほどありがたいのになあ、と思うことも多々あります。 ただいかんせん、現在スタンダードな数理最適化アルゴリズムの多くは 「最適でないものを早い段階で削る」という動き方をして速度を稼いでいますので、 これはちょっと先のことになるかもしれません。 将来はぜひこういう複数解提案型アルゴリズムの普及に期待するとして、 「厳密すぎる」アルゴリズムに対するユーザー側には、データを変化させて沢山の答を出して目を慣らしておく、「前回の答と大きくは違わない」といった制約を入れる、目的関数を工夫してあり得る答に差をつける、といった自衛策が必要になります。このあたりはまた別の機会にお話ししましょう。

さて、次回は予算上限を変化させて、まさにM君が望んでいた「面白い答」が出るようにしてみます。

居酒屋シフトモデル化いろいろ (3. 「対応付け」タイプの適用)

前回は働き方(シフト)のパターンを列挙して、重ね合わせのモデルを解くことで 必要な人数を手当するために各シフトパターンを割り当てるべき人数を次のように明らかにしました。

f:id:optimizationTanabe:20160615162937p:plain

あとは、12人のスタッフ A ~ L にどれを割り振るかで、このモデルは 少し前の記事 で紹介した「対応付け」タイプそのものになります。 この記事で紹介している人に仕事を割り合てるケースと全く同じ構造で、 あるパターンに対して対応付けられる人数を重ね合わせモデルが教えてくれた数(パターン1 には 4人、パターン3 には 2人 ...)に制約すればよいのです。 対応付けられる人数 0 と出たパターン2は省いて描いています。

f:id:optimizationTanabe:20160615163014p:plain

モデルの骨組みができたらあとは個別の制約です。 お客さんからは

  1. A さんは午後の勤務ができない(結局Aさんはパターン1しかできない)
  2. 昼の繁忙期をカバーするシフト(パターン3)には新人(I,J,K,L)を割りあてない
  3. 仕込み時期の朝のシフト(パターン1)は教育のため、新人2人と旧人2人で担当する

といった制約が与えられました。 そもそも 3 番目の制約については、マス目タイプの場合にはどうやって表現してよいのやら見当すら付きにくいのですが、人とシフトの「対応付け」タイプならば大丈夫です(数式での表現が気になる方へ:パターン1と新人達(I,J,K,L)を結んでいる線のうち、正確に 2 本が 1になる(活きる)と制約する)。結果は以下です。

f:id:optimizationTanabe:20160615163043p:plain

どうでしょう、確かに満たす答になっていますね。 ではスケジューリングはすべて「マス目」ではなく 「重ね合わせ」 + 「対応付け」 すると万事大丈夫かというと、さにあらず。 一時は満足してくれていたお客さんが

「12:00 の繁忙期の時間帯に新人が 2人も交じっているのはちょっと。。。」

とか言いだすと、話はあっという間に荒れ模様に。 朝のシフトパターンを新人2人で担当させる、というのはお客さんの要望として与えられたもので、 4 時間勤務であることの帰結としてそうなるんですよ、とまずは落ち着いてお伝えします。 ここでお客さんの要請が矛盾していて困るとか文句など言っていては数理最適化のプロとしての経験を疑われます。 そもそも答を見ないで何個も制約を言って互いに矛盾しない方が珍しいことで、 要請の矛盾に気付くことができるのが数理最適化の意義とも言えるのです。 まあそれはさておき、しばらく黙って考えていたお客さんがこう切り出したのには我々も不意を突かれます。

「そもそも新人についてはまずは 3時間勤務にするのがよいかもしれないと思うんですが。。。」

うう、これって足りない人を補うために 5 時間勤務も追加されるっていうことかな、するとシフトパターンが増えるのでパターン列挙まで戻らねばならないなあ、これならいっそ「マス目」タイプの方が簡単かもしれない。。。などと逡巡しつつ我々の仕事は続きます。

このように数理最適化では、同じ問題に対するモデル化の方法が複数あって、 それぞれの得手不得手が分かれています。 このケースのようにマス目が結果だから「マス目」タイプが最善、とは限りません。 ぱっと見、手に負えないような問題が別の見方をすると、すきっと解けるということはままあって、 これがモデル化という作業の醍醐味の一つです。一方でお客さんにとっては大したことには見えない要請が一つ増えた途端に精緻に組み立てたモデルが形無しになってしまう、ということもままあります。まあ実務は数理最適化モデルのタイプなど気にせず移ろってゆくものですからそれもやむなし。 我々ができる最善は複数のモデル化の方法に通じて対応力を身につけること、 そしてモデル化の限界といった不都合な話を含めてお客さまときちんとコミュニケーションと取ることでしょうか。そのコミュニケーションのツールとして、この数理最適化モデルのタイプ分けと「絵」が使えればよいな、と手前味噌ながら考えております。

居酒屋シフトモデル化いろいろ (2. 「重ね合わせ」タイプの適用)

前回は最低限の要件から出発して、「勤務は連続」という「常識」を制約の形で入力し、まともなシフトの導出までたどり着きましたが、今回は発想の方向を変えてそもそもどんなシフトが許されるのか、まずは考えてみましょう。 「連続」という制約が効いて、許されるシフトは意外と少なく、 9:00 から 16:00 の連続勤務で 4 時間の勤務パターンは次の 5 つしかありません。

f:id:optimizationTanabe:20160608154046p:plain

こういうパターンの働き方をする人を何人か「重ね合わせ」て必要人数、すなわち

f:id:optimizationTanabe:20160601124114p:plain

を実現する方法を数理モデルを使って求めましょう。 重ね合わせ(人数の足し算)の結果と各時刻の必要人数の差を最小化する、次のようなモデル化が可能です。

f:id:optimizationTanabe:20160608154214p:plain

このモデルはまさに「重ね合わせ」タイプで、時系列がからむところも 重ね合わせによる生産計画問題 と同じです。解くと f:id:optimizationTanabe:20160608154251p:plain といった具合に 1 ~ 5 の各パターンに (4人,0人,2人,2人,4人) を割り合てれば丁度人数が満たせることがわかりました。 この人数構成で供給している労働力を積み上げ表示してみたのが次のグラフ(同じパターン毎に色分けしてみました)です。 確かに各時間帯の所要量を満たしていることがわかります。 f:id:optimizationTanabe:20160608154332p:plain

あとはこのパターンを適当に 12人に割り振れば前回の結果と同様のものが得られます。

前回に紹介した、制約を追加して解を絞り込んでゆく方法と、 あり得る解の列挙から出発する今回の構成的な方法は、 数理最適化モデル化の手法として対になるものです。 例えば下の絵の白地の部分を通る「経路」が許される解だとしましょう。

f:id:optimizationTanabe:20160608154413p:plain

前回の「解を彫り出す」やり方は、 次のように制約(青い領域)を追加して白地の部分を浮かび上がらせることに相当します。したがって解の領域の形が複雑だと、必要な部分を浮かび上がらせるための制約はかなり増えてしまいます。

f:id:optimizationTanabe:20160608154432p:plain

さらに無駄な制約も現れます。

f:id:optimizationTanabe:20160608211821p:plain

左下の青い四角に対応する制約は他の制約にすっぽりと含まれてしまうので不要なのですが、モデル化の時点でこういう重なりに気づくのは数学的にもかなり難しい。大抵の場合まずは安全サイドに制約を加えておこうとなってしまいますのでさあ大変。単純な結果に不釣り合いに「重たい」制約だらけの問題を解くことになりかねません。

一方で今回の構成的な方法は、白地の部分に「経路」のサンプルを複数描いてしまって、数理モデルに外から与えてしまう、ということに相当します。

f:id:optimizationTanabe:20160608154540p:plain

この方法であれば、解のあり得る領域の形の複雑さが味方して、考慮すべき「経路」の種類や数が少なく済み、手間なく結果を得ることができます。

制約を追加しても追加しても、 出る答が実際的ではないのかお客さんが首を縦に振らない。

「では、あり得る答をちょっと幾つか作って見せてもらえますでしょうか?」

「やけ」になっているみたいですが、 実はこれがきっかけで「列挙+重ね合わせ」の打開策が開けたり、 といったこともあるのです。

さて、解き方の話で進めてきましたが、 この数理最適化モデルの結果の意味付けは前回と若干異なっています。 前回の設定が 12人 のメンバーにどのシフトを取らせるかという、 現場のオペレーションの問題だったのに対して今回は そもそもどういう働き方をする人をそれぞれ何人募集すればよいのかという現場を離れた要員計画、 大袈裟に言うと経営サイドの問題になっていて、 前回の設定では前提条件になっていた 「12人(=4+0+2+2+4)」という人数が結果として導かれています。

  • こんな人数で現場を回せだなんて本社は何にもわかっちゃいない」
  • 「人数をこんなに投入してもまだ現場のパフォーマンスが思ったように向上しないんだよなあ」

一定サイズ以上の組織の様々な局面で聞かれる声だと思いますが、数理最適化ならある程度定量的な裏付けを持つ人員の配置が可能です。最適化を現場と管理サイドの「コミュニケーションツール」として用いる手もあるという事をここで申し添えておきたいと思います。

話が大きくなってしまいましたが、とはいえ、現場のオペレーションには所要人数がわかっただけでは不十分でもっと細かい話の考慮が必要ですね。A さんは夕方の勤務ができない?了解です。次回はこのモデルと「対応付け」タイプのモデルを連携させて、このモデルの延長線上で現場のオペレーションを与える結果を得ましょう。

居酒屋シフトモデル化いろいろ (1. 「マス目埋め」タイプの適用)

数理最適化問題のタイプ分けのご紹介が一通り終わったところで、 これらを用いてよく実務で現れる数理最適化のモデルの組み立て方について具体的に解説しましょう。 オフィス街でランチ営業しているある居酒屋のアルバイトスタッフ 12 人の 勤務シフトを決定する問題を解いてみます。彼らの勤務は一日 4 時間で出勤時間は 朝 9:00 から夕方 16:00 の間とします。

一時間ごとに、現場を回すために必要な人数がおおむね次のようにわかっているとします。 朝方は 4 人、昼時に向けてじわじわと忙しくなり、 昼時に 8 人というピークを迎え、そして同じ形で減衰しています。

f:id:optimizationTanabe:20160601124114p:plain

結果のシフト表は人と時刻のマトリックス、他ならぬマス目ですから、 まずは「マス目埋め」タイプとしてモデル化してみましょう。 「マス目埋め」タイプの紹介記事 での各列のインデックスを「週」を「時刻」と解釈すればほぼモデルは同じ。 勤務は 1 種類(するかしないか)、なのでかなり単純です。

f:id:optimizationTanabe:20160601124142p:plain

果たして結果は? 数理最適化では勤務する/しないを 0 と 1 で表現しますが、 1 と出たところを塗りました。

f:id:optimizationTanabe:20160601124208p:plain

確かに各人の勤務は丁度4時間、縦に見たときの必要人数も満たしています。 こういう結果に直面した場合における、率直な心情を人間代表として数理最適化にぶつけるとすると次のセリフになるでしょうか。

「人数が居れば、勤務時間を満たせば、良いっていうもんじゃない !」

先日の記事では偏りが気になる、といった程度でしたが今回は「使えない」 度合いがパワーアップしています(例えばBさんとかひどいものです)。 常識的に各人 4時間は連続して働く、 すなわち「1時間外してまた戻ってくる」といった勤務があり得ないことを数理最適化モデルには教えてやる必要があることがわかりました。 こういうときに我々が繰り出すのが、数式で実務的な制約を表現する「小技」です。 古くから様々なテクニックが知られており、大抵の実務的な条件は適宜余計な変数など定義が必要な場合がありますが一次式に書き下すことができます(ちょっと数式っぽくなるので詳細は別の機会に)。 ここでは「一度帰ったら職場に復帰してはならない」という制約を入れることにしましょう。 具体的には横に連続したマス目が 1 (勤務) -> 0 (非勤務) という並びになっているならば、 その右にはすべて 0 が並ぶ、という制約を入れます。

f:id:optimizationTanabe:20160601124243p:plain

この制約と各人の勤務時間が 4時間であることを合わせると 所望の形の勤務形態となるはずです。

f:id:optimizationTanabe:20160601124310p:plain

今度は無事、意図した形のスケジュールが出力されました。 このように「マス目埋め」タイプのモデルは、基本の縦と横の制約のみが入っている状態だと 解の自由度に比べて制約が少ない(解の自由度は行と列の数の積ですが、制約の数は和)ので通り一編の答はぱっと出すことができますが、実務的に使えるようにするには様々な小技を駆使した制約を追加して 所望の答をいわば「彫り出す」操作が必要になります。

次回は対照的に「彫り出す」やり方から「組み立てる」やりかたで同じ問題を解いてみましょう。 「重ね合わせ」タイプの出番です。

「対応付け」タイプのモデル:仕事アサインと座席表問題

人に仕事をアサインしたり、車に荷物を割りあてたり、 人に商品をおすすめ(レコメンド)したり、といった問題は 数理最適化の重要な応用の一つで、 これらは次の絵のような構造を持つ「対応付け」タイプのモデルで 記述されます。

f:id:optimizationTanabe:20160525091837p:plain

「人」や「車」が左の○、「仕事/商品」や「荷物」が右の□。 線分は対応付けの「可能性」を示していて、 仕事のアサインで言えば「人」と「担当できる仕事」を結んでいます。 対応付けタイプの数理最適化を解くことは、 線分のいずれかを取捨選択することに対応します。

「対応付け」タイプのモデルの最も基本的な制約は、 各○が対応付けられてよい数、 レコメンドで言うと各人に対して商品をおすすめすべき数で、 これは次のように左の○から出ている線分の根本に次のような注釈を加えて記述できます。

f:id:optimizationTanabe:20160525091926p:plain

数理最適化は対応付けられる「□」側の事情も同時に考慮できます。 仕事の割り当ての場合には誰かが選択した仕事を別の人は担当できない、 人に店をレコメンドするのでしたら、 店の容量以上のレコメンドを集中させてはならないといった 事情を右の「□」の根本にやはり注釈を加えて記述しましょう。

f:id:optimizationTanabe:20160525092008p:plain

対応付けの善し悪しを決める値を線分上に定義しておきます。 仕事のアサインだったら各人の仕事の「希望度合い」 レコメンドだったら「おすすめ度合」といった量を定義しておきます。 3人の仕事のアサイン問題を具体的に記述してみました。 各人が選べる仕事も1つだけ、仕事の定員も 1名とします。

f:id:optimizationTanabe:20160525092051p:plain

希望度合いの合計が最も大きくなるよう、数理最適化が導いた答は次です。

f:id:optimizationTanabe:20160525092146p:plain

「最適化」と言いながら、 Aさん、Bさんについては第二希望の仕事がアサインされています。 これは Aさん、Bさんが第一希望を担当する場合のメリットより C さんに第一希望の掃除以外を割り当てる損失が上回るため。 数理最適化の単細胞な損得勘定の結果なので調整は必要ですが、 この単純なモデルでも仕事が競合している場合には、互いの希望度合いと担当可能性が 影響し合ってしまう、という現実を写し取ることができています。

対応付けモデルが考慮できる制約はこれだけではありません。 実務的なケースによく現れる「対応付けの結果に対する制約」という種別を紹介しましょう。 ある小さな会社の社員旅行の幹事さんの悩み、席割り問題をやってみます。 参加人数の30名分の席を確保できたのですが、 取れた指定席が通路を挟んで微妙な感じに分かれています。

f:id:optimizationTanabe:20160525092224p:plain

社員は新人5名、若手15名、年長者10名という世代構成です。 どこに座らせれば良いでしょうか。 世代が似かよった人が近くに居ると会話が進むよなあと考えた幹事さん、 同じ世代に属する人の会話の頻度を 3 として、世代が一段階違うと 頻度が 1 減る、という少々強引な数値化を考えました。 例えば新人同士は会話の頻度が 3、若手対年長は 1 つ減って 2, 新人対年長は(世代が二つずれているので) さらに減って1、といった具合です。 こうしておいて 「会話の頻度が高い同士を物理的な距離が近い座席に割りあてる」 という制約を考えました。

「人」を「座席」に割りあてる点で基本的な構造は仕事のアサインと同じですが、 対応付けの結果全体の様子を制約する「会話の頻度の高い人同士を近くに」という 要件が入っています。 このタイプの制約が入ると問題はかなり難しくなり、 厳密な最適解を求めることは簡単でなくなってしまうのですが、 幸いこのタイプには簡潔な数学的表現 (どうやるのか気になる方へ:この制約は二次式を使うと簡潔に表現できます) があるので、数理最適化ソルバーに実装すること自体はかなり簡便にできますし、 この程度の規模ならば一分程度で結果が出ます。 どの程度制約が満たされるかはわからないので、 ここでは制約を満たす度合いを数値化して最小化してみました。 次が数理最適化が導いた座席表です。

f:id:optimizationTanabe:20160525092258p:plain

問題のセットアップは若干面倒でしたが、得られた結果は直観的でなるほど、 各世代の人をまとめて配置する結果になっていますね。 ただ、気持はわかるのですが新人を「半島状」に配置してできるだけ他の社員と接触させない、隔離した感じになってしまいました。 社員旅行は新人との交流を深めるといった意味もあるんだよなあと幹事さんはさらに考えて、 新人同士が固まってしまわないよう、 「新人同士だけについては特別に席を極力遠くすべき」 という要件を付け加えてみることにしました。 (これも数式表現が気になる方のための蛇足ですが、 これは新人同士についてだけ会話の頻度を示す指数を 負の大きな数にすると実現できます)。 以下、得られた結果です.

f:id:optimizationTanabe:20160525092322p:plain

新人が固まるのは避けられて、先輩社員の側に配置されました (左上のブロックに居る二人はちょっと可哀想ですが)。 ただ、最初にモデルを考えていたときには思いもよらないことでしたが 「極力遠く」という制約が災いして、新人が隅っこになっています。 これは「交流」という意図からは外れますね。 では新人は「へり」にやらないように対応付けの可能性を変更する(対応付けの絵で新人と隅っこの座席を「線」で結ばない)、 あるいはここまで来たら人手で細工すれば十分かもしれません。 まあ、いずれにせよ数理最適化のアシストでまずまずの座席表ができそうではあります。

「思いもよらない」なんてモデルを作った立場なのに無責任な? 最後まで数式できちっと片付けるべき? ええ、数理最適化モデルや解法アルゴリズムを実装している我々自身も 特定のデータを与えたときの数式モデルの結果を予測しきることはできないので、 バランス感覚が要求されるこうした問題の場合、 「黙って座ればぴたりと当たる」といった風にはならないことの方が多いのです。 じつは微妙で個別的な要件を実現するために「最後は手で修正」といったこともかなりあります。 それじゃあ最適化の役割はどこにあるのかって? そのあたりはまたゆっくりと別の回でお話ししましょう。

営業マンの担当区域の割り振り、商品の棚割り、ゲームの対戦表のスケジュールなど、このタイプのモデル化を知ると数理最適化できそうなネタは身の回りのそこかしこに転がっている気がしませんか。 「対応付けの結果に対する制約」まで考慮すると適用範囲はぐっと広がります。 例えば棚割りは上の座席表とほぼ同じ考え方で表現できますし(併売がよく行われる商品間は 座席のケースでの会話の指数が高い、というのと同じ) 対戦表スケジュールでは、ある試合に割り当てられた二人の強さの差が一定以下、 といった制約を考慮することができるようになります。

さて、ここまでで数理最適化モデルの 4 タイプ (重ね合わせ、保存、マス目埋め、対応付け)の紹介が一通り終わりました。 今後も数理最適化モデルのよもやま話を続けますが、 アルゴリズムやモデル化の手法などを紹介するにあたって これらのタイプ分けの話に立ち戻って言及させていただこうと考えています。

「マス目埋め」タイプのモデル:アルバイトの担当決め問題

いわゆる「シフト表」は「人」を行、「日付」を列とするマス目の形をしています。 5人のアルバイトさんA,B,C,D、Eの一週間のシフト表を数理最適化で作ってみます。 この職場では各人は「レ」(レジ打ち)、「日」(日勤)、「夜」(夜勤)、「休」(休暇) 、 のいずれかを担当します。

f:id:optimizationTanabe:20160517160409j:plain

職場の事情はこの表を縦に見ることで定義します。各日一定の役割の人は必要です。

f:id:optimizationTanabe:20160517160440p:plain

個人の事情は横に見れば定義できます。人間、休みが必要ですし、しんどい夜勤は そんなに偏ってはなりません。

f:id:optimizationTanabe:20160517160502p:plain

なんだか求人広告みたいですが、これでも立派な数理最適化モデルで、 もう解くことができます。このとっつきの良さがマス目タイプの問題の一つの特徴です。 果たしてその回答は?

f:id:optimizationTanabe:20160517160542p:plain

制約をチェックしてみてください。満たしてますね。 一秒もかからずこれを出せるのが今時の数理最適化の実力。 数理最適化を解く手法として特にマス目タイプに強い、 「メタヒューリスティクス」アルゴリズムの威力です。

皆さんどんどん使いましょう、じゃあまた来週 !

・・・とは行かないのが、この「マス目埋め」タイプのモデルの難しさで、 とっつきが良かった分、思いもよらない苦労をすることになります。 上のシフト表、E さんいきなり 2 連休ですね。 不公平だと文句が出そうだと思ってもう一度解くことにしてみました。 同じ問題なのだから同じ答が出るだけだろうって? ええ、普通はそうなのですが、 じつは「メタヒューリスティクス」をアルゴリズム(解き方)として採用している場合には 初期値を乱数で作ってから解を改良する方法なので、 (存在すれば)制約を満たす「別解」を得ることができます。 これが最初の別解。さて、どうでしょう。

f:id:optimizationTanabe:20160517160612p:plain

今度は A さんに夜勤が割りあたらず、レジも一回しかありません。 もう一度。

f:id:optimizationTanabe:20160517160643p:plain

これでは A さん B さん連続夜勤の過酷勤務です。これも没。

f:id:optimizationTanabe:20160517160713p:plain

C さん夜勤やらないわ、3人が連続夜勤をやるわ、 ある意味極めつけのシフト表が出てきてしまいました。 確かに最初に言った制約は満たしているんですが。

じつは10回やると10回とも違うシフトが出てきて、 うち 9回が連続夜勤や夜勤割り当てがされない人が居る、 何かしらの問題を抱えた結果が出力されてしまうことことが判りました。 実はこの「マス目埋め」タイプのモデルは、解が沢山出るが、 使えるものが少ないという状態に陥りがちなので注意が必要なのです。 どうすればよいでしょう。そうです。変な解が出るのは制約が足りないから。

  • 夜勤は続いてはならない
  • 各人 1 回は夜勤をする

という制約を入れれば、すぐさま次の答に行きつくことができます。

f:id:optimizationTanabe:20160517160739p:plain

もう大丈夫でしょうか。 D さんにレジが入らないのが気になる? 連続でレジは困る? わかりました。また制約を追加しましょう・・・

これまでのケースのようにモデルを定義する本質的な制約を入れて 答が出れば OK、だったのとはちょっとノリが違いますよね。 制約を満たす答が沢山ありすぎることと、どういう制約が必要なのかが あらかじめ予見しにくいのでどこまでも「アジャイル」にモデルの改変が続くのが このタイプの特徴と言えます。

特にこのケースは人的スケジューリングにおいて暗黙のうちに重視される「平準化」を 機械に意識させることが意外と難しい、という実例になっています。 でもちょっと待ってください。 「メタヒューリスティクス」アルゴリズムは 乱数を使っているから誰も特別扱いしていないので出る結果は 偏らないはずですよね・・・

じつは意外とそうでもないのです。 皆さん 1,2,3,4,5 の数字をランダムに 10 個並べてみてください。 私の手元のプログラムは

2,2,5,1,3,1,5,1,3,1

を出してきました。4 がないのが不自然でランダムとは思えない? いえ。数字の出方が均等でも特定の数字 1つが欠ける確率は 0.8 の 10 乗 = 10.7% です。 1 から 5 までのいずれかの 1 つの数字が欠ける確率だともっと多くなって、 計算がちょっと面倒ですがじつは 「47.7%」 と大体半分に迫る確率となります。 人間が自然に備えている「均等化」の感覚が働いて おそらく皆さんの作成された列には 1 から 5 までのすべてが現れたのではないでしょうか。 解が多すぎるとき、どこまでも自由な機械の振舞いを強制するためには制約が必要になる、 というお話でした。

この数理最適化モデルはかなり特殊なタイプとも言えますが、 実務的な利用価値が非常に高いので タイプの一つとして紹介させていただきました。 ここでは名前だけ出した「メタヒューリスティクス」って一体何なのか、 マス目タイプのモデルを使って質の高いシフト表を得るための悲喜こもごものお話はまた別途お話ししたいとと思います。

さて、次はいよいよ最後の「対応付け」タイプです。

「保存」タイプのモデル:大家さん蓄電池導入問題

「電力自由化」の波に乗って電力契約(プロバイダ)を乗り換えた、学生向けアパートの大家さんの話。 プロバイダのホームページの自分のアカウントを見ると電力使用量の履歴がわかります。 どれどれ、と平均的な一日の様子を見てみると次のような感じになっていました。

f:id:optimizationTanabe:20160510144438p:plain

「使用電力量」は夜のピーク利用量を 100(%) としています。 料金単価も単位換算することでこの電力量に単価をかけ算すると電気料金が出るようにしています。 この平均的な一日の電気料金は 5×30 + 9×20 + 7×100 + 3×40 = 1150円。 幸いなことに学生達は昼の最も電気の高い時間帯は出掛けているので ほとんど電気を使わない(ピークの 20%)のですが、 利用量ピークの夜の電気料金が 7円とそれほど安くなく、 深夜の料金が 3円 という思い切った料金設定のメリットはあまり活かせていません。

そんな折に電力プロバイダから営業マンがやってきて、 「蓄電池導入」プランを薦めてきました。 話は単純で、安い深夜に電気を貯めてピークに使うことで電気料金を浮かせましょうという提案です。 ただ設備投資には少なからずお金がかかるし、元がとれるか心配。 この評価、具体的にどうやってやればよいでしょうか。 じつはこの話にずばり対応する数理最適化モデルがありまして、 絵にすると次のようになります。

f:id:optimizationTanabe:20160510191842p:plain

この数理最適化モデルでは、購入した電気が消えてなくなることはなく(保存)、 電池に溜められるのか、外に出て使われるかの二通りであることに着目しています。 右向きの矢印(→)は時間の経過によって引き継がれる量を示していて、 下向きの矢印(↓)はその時間帯の電気の出入りを示しています。 この矢印が複数付いた「○」が連鎖している、 というのが「保存」タイプのモデルに共通の形です。

蓄電池の容量は 100。すなわちフル充電すればピーク時間帯をまるごと賄える、としましょう。 また、この大家さん、ピーク時間帯の利用量を参考に基本契約を調整したため、 電気の購入量についても時間帯毎に最大 100 という制約があるとします。 さて、仮に初期の蓄電量は 50 として、 この設定で最適な電力購入と蓄電池の利用方法を数理最適化に探させてみましょう。 思った通りのことが起きるでしょうか。次がとりあえずの答です。

f:id:optimizationTanabe:20160510144559p:plain

電気料金は 5×80 + 7×20 + 3×40 = 660円で、 1150円のほぼ半分になってますが思ったのとはなんだか違う。 昼の電気が高いときに蓄電された分を使っていますが、 最も安い深夜も必要最小限しか買っていない。 なぜ?これはモデルの欠陥のためです。 モデルにとっては深夜を迎えたら後は世界が終わる設定になっているので、 深夜に蓄電しようという意図が働かず、 単に使い切って終わり、という結果が出ているのです。 これは"end-effect" と呼ばれる、 時間の終端の条件によって解が決まってしまうという現象で、 実務的に結構複雑なモデルを組んでいる時にもよく現れる現象です。 人間、モデルの主要な構造にかかわる部分については、細心の注意を払うものですが、 終端条件についてはついつい注意が疎かになります。 すべてが同時に見えている数理最適化ソルバーはそこを突いて 「アリとキリギリス」でいうところの 「キリギリス」のような解を出してくるわけです。

end-effect を回避する方法としては 次の日の朝に向けて引き継ぐべき蓄電量を外から与える、 もう 1日分の需要パターンを予測しておいて 2 日分を解いて最初の1日だけを使う、 など、幾つかスタンダードな方法がありますが、 ここでは平均的な一日がずっと繰り返されると仮定できる場合に可能な ちょっと面白い方法を提案しましょう。 深夜の蓄電量の残りが朝にそのまま引き継がれると置いてしまうのです。 これで初期の蓄電量 50、という恣意的な設定も不要になります。 結果を次の絵に示しました。

f:id:optimizationTanabe:20160510144625p:plain

コストは 3割以上減らせてますし、 今度はちゃんと「アリ」になって 電気の安い深夜に目一杯買って朝に備える形になっています。 ただ、なぜか朝の充電が 100% ではなく、60% から出発していますね。 どうしてもっと買っておかないのかなと考えると、 それは大家さんが最初に行った電力の基本契約のために 購入量が 100 に制約されているのが原因になっているのがわかります。 蓄電池を購入するならば、少々余計なお金を払ってでも基本契約を変更し、 上限を拡張して、深夜に 140 購入して蓄電池をフル充電にしておけば、さらに割安になりますね。 蓄電池の容量をもうすこし大きくした場合や 夏休みなどで電力需要が変化した場合、 さらにこれはもっと未来の話かもしれませんが、 余った電力をもし売ることができた場合、といった 「シミュレーション」も数理最適化ならば簡単です。 設備投資したときの「最も良いやり方」を自動で導出してくれますので、 もしもこんな設備を増強したらどうなるのか、といった具体的な検討ができます。 「蓄電池導入」プランを売るべきプロバイダの営業マンが備えるべきツール、 だと思いませんか。

さて、数理最適化モデルのタイプのお話に戻ります。 下がこの保存タイプのモデルの「骨組み」の絵で、 連結の数は考える期間の長さ次第です。

f:id:optimizationTanabe:20160510182826p:plain

保存タイプは、 重ね合わせタイプほど多彩な応用があるわけではありませんが、 この例のような電力の融通とか 貯水層を含んだ水の流れ、蓄熱層のある熱の流れ、 倉庫を含む生産計画(ロットサイジング)といった状況においては ほぼ必ずといって良いほど現れ、 状況を実に明快に整理できるという「切れ味」の鋭さにおいて、 覚えておく価値のあるモデルのタイプかと思います。 実を申しますとこの問題の設定も、 Dantzig 先生の教科書の、倉庫の問題(「1.4.3 A SIMPLE WAREHOUSE PROBLEM」)を 構造を変えずに蓄電池に翻案したものです。 この翻案が簡単にできるところがこのタイプのモデルの汎用性を示しています。 深夜の蓄電量を朝と同じにするというアイディアもこの例題から頂きました。 このパターンのモデルは例に示したように end-effect が出やすい問題なので、 終端条件の設定には注意しなければならないという点も老婆心ながら 付け加えておきます。

保存タイプのモデルとその応用についてご紹介しておきたいことはまだ沢山ありますが、 またそれは後にしてタイプを紹介するテンポを上げて、 次回は「マス目埋め」タイプの話に進みましょう。