最適化楽屋話#12 ラインのディスパッチ問題の数理最適化モデル

Numerical Optimizer 開発責任者の田辺隆人でございます。

先日オペレーションズリサーチ学会では「生産の現場に現れる数理最適化問題の背景と考察」というタイトルで発表させていただきました。下の図のように、生産そのものはもちろん、生産を成り立たせている原材料の調達、製品の在庫や配送までいろいろな局面で、数理最適化が利用されつつあり、我々が蓄積した数理最適化のアルゴリズムやモデリングの知識がどのように役立つのか、というトピックでお話しをしました。

講演で題材としたのはラインのディスパッチ問題です。

Numerical Optimizer のライセンスをお持ちの方はExcelアドインを使った小規模データの解説スライドとエクセルブック、最適化モデルをダウンロードしてお試しください。製品1～4をライン A ～ F に割り振るときに負荷を按分しつつ切り替えコストを下げる、という典型的な問題ですが、LP緩和に基づく分枝限定法アルゴリズムを用いる場合、直観的でないネットワークフローに帰着する定式化が安定的に良い答を与えます。

線形緩和に基づくヒューリスティクスアルゴリズムの昨今の進歩におそらく依拠した話なのですが、こういった数理最適化モデル・アルゴリズムのノウハウが実は最適化システムづくりのキーとなり得るというのは実に興味深いと思っています。