読者です 読者をやめる 読者になる 読者になる

最適化一口話

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

居酒屋シフトモデル化いろいろ (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 さんは夕方の勤務ができない?了解です。次回はこのモデルと「対応付け」タイプのモデルを連携させて、このモデルの延長線上で現場のオペレーションを与える結果を得ましょう。