数理最適化のすゝめ

こんにちは、サービスデリバリーセンターのハガーです。

この記事は 『CRESCO Advent Calendar 2019』  13日目の記事です。

今回は最近私が仕事で行っている「数理最適化」について書きたいと思います。デジタルトランスフォーメーション(DX)による業務最適化への意識の高まりや、量子コンピューティングへの期待からか、「数理最適化」についても最近注目されつつあります。

数理最適化とは

「数理最適化」とは「ある制約が存在する中で、数ある答えの中から最も良いものを見つける」ための手法になります。昔からオペレーションズ・リサーチなどの分野で研究されてきました。

「数理最適化」が適用できる対象にはいくつか種類があるのですが、よく示されるのは以下のようなものです。

商品の仕入れのため、9kgまで入るバックを持って店を出た。
商品には以下の4種類があり、1度の仕入れで商品価値が最も高くなるよう仕入れたい。

商品Aは重さが2kgで、商品価値は3万円
商品Bは重さが3kgで、商品価値は4万円
商品Cは重さが4kgで、商品価値は6万円
商品Dは重さが5kgで、商品価値は7万円

どの商品をいくつ仕入れればよいのだろうか。

これを「数理最適化」で解くには、まずは変数、目的関数、制約条件という3カテゴリに分類します。

 カテゴリ  カテゴリの詳細 今回の問題だと
変数 目的のために選択する量 どの商品をいくつ、仕入れればよいか
目的関数 問題を解く目的、最も良い状態の定義 商品価値が最も高くなるよう仕入れる
制約条件 制約、守らなければいけないこと 9kgまでしかバックに入らない

その後、「数理最適化」で解けるように数式にする定式化と呼ばれる作業を行います。イメージとしては以下のような形式になります。

変数:商品A~商品Dの個数をXA~XDとする

目的関数:3×XA + 4×XB + 6×XC + 7×XD (→この結果が最大となるXA~XDを決める)

制約条件:2×XA + 3×XB + 4×XC + 5×XD <= 9、XA~XD >= 0

最後に「数理最適化」のアルゴリズムで数式を解くと、「商品Aを1つ、商品Bを1つ、商品Cを1つ仕入れるのが、商品価値が最も高くなる仕入れ」という解が導かれます。(実は他にもパターンがありますが後述。)

どのような数理最適化を行っているのか?

私が主に担当しているものは「組合わせ最適化」と呼ばれるもので、数ある組合せパターンから、最もよい組合せを見つけるというものです。具体的には以下のような問題について適用を実施しています。

・シフトスケジュール問題

・要員配置問題

このような問題の特徴としては、結果として条件を満たす解が多く存在するため、どれか一つの結果が出ても、お客様の認識との「ズレ」が生じる可能性があるということです。

例えば先ほどの最適化の例だと、「商品Aを1つ、商品Bを1つ、商品Cを1つ」以外に、「商品Aを3つ、商品Bを1つ」、「商品Cを1つ、商品Dを1つ」なども数式上は正解となります。実業務の中では隠れたルールや担当者の経験で実施しているなども多く、ヒアリングやデータ分析をすることで「商品点数が少ないほうがよかった」、「商品Dは入れたい」などのルールが見えてくることがあります。実務上ではこれらの隠れたルールを取り込み、お客様の認識との「ズレ」をいかに少なくしていくということが重要となります。

数理最適化の使いどころは?

「数理最適化」の使いどころは、まずは「物理的なリソース」が限られているが、その中で最大の成果・パフォーマンスを出したいというときです。「物理的なリソース」にはよくあるものとして人材、輸送機器、在庫、時間etcが該当しますが、その制限がそのまま制約条件として組込まれます。

またAIや機械学習なども近年の進化によって予測精度は向上していますが、最も良い状態であるかどうかは保証されない可能性があります。「数理最適化」ではこのような最適性が保証されるほか、制約条件により現実的に実行可能な解が出力されることから、すぐに業務の自動化に結び付けていくことができます。

おわりに

ハードウェアやアルゴリズムの進化によって、「数理最適化」の適用範囲も広がってきました。業務改善のための1つのヒントになれば幸いです。

 

  • このエントリーをはてなブックマークに追加