NTT DATA

DATA INSIGHT

NTT DATAの「知見」と「先見」を社会へ届けるメディア

キーワードで探す
カテゴリで探す
サービスで探す
業種で探す
トピックで探す
キーワードで探す
カテゴリで探す
サービスで探す
業種で探す
トピックで探す
background-image-careers
2012.11.8技術トレンド/展望

数理最適化の技術を活用するには

勤務表作成や配車計画等、数理最適化の技術は様々な分野で応用されています。

数理最適化という計算技術

数理最適化は「数理計画法」とも呼ばれ、近年注目を浴びている計算技術の一つです。これは"データ"と"ルール"が決まっている際、ルールに従う範囲内で可能な限り良い解を見つける方法です。「数理計画問題を解く」と表現します。最適化という名前からコスト削減の側面が強調されがちですが、数理最適化は、「複雑なルールを遵守する解を得る」場合にも使うことができます。勤務表作成、配車計画、広告配信等、幅広い分野で適用可能です。株式会社NTTデータ数理システムでは、数理最適化の技術で数理計画問題を安定かつ高速に解くツール「NUOPT」参考1を開発しており、東日本旅客鉄道株式会社様の勤務表自動作成機能参考2や、時事通信社様と共同開発したCS進出ナンバー導出プログラム参考3など、数多くのシステムに導入されています。

数理モデリングで数理計画問題を作る

数理計画問題の中で、最も広く実務で扱われている問題が「整数計画問題」です。これは、変数に対して整数値をとるよう制約を課した問題になります。先にあげた勤務表作成や配車計画等、ビジネスにおける意思決定問題の多くがこの整数計画問題として定式化されます。この定式化作業のことを「数理モデリング」といいます。数理モデリングについて、株式会社NTTデータ数理システムが将棋連盟様向けに開発した「対戦表自動作成システム」参考4を例にとって説明します。まず、会員Aと会員Bに対してx[A,B]という0-1整数変数(0か1のみを取る変数)を用意します。これを用いて対戦の組み合わせを以下のように表現します。

  • x[A,B]=1⇔AとBが対戦する
  • x[A,B]=0⇔AとBが対戦しない

この変数を用いて「過去に対戦した会員とは対戦しない」「履歴を考慮してバランスよく対戦を行う」といった制約を記述し、整数計画問題として定式化を行います。

数理最適化のアルゴリズム

先に挙げた数理最適化ツールNUOPTでは、整数計画問題を解く際「WCSP」参考5と「分枝限定法」参考6という2つのアルゴリズムを用いています。「WCSP」は、重みを付けた制約を可能な限り満足する解を出す際、適当な初期解から出発し、解の近傍にそれより良い解があれば置き換える操作を繰り返し実行することで、より良い解に辿りつこうとする方法です。「分枝限定法」は、変数の一部を整数に固定した子問題を列挙し、順に解いていくことで最適解の候補を絞っていき、厳密解を得ようとする方法です。これらのアルゴリズムを元に、数理計画問題を安定かつ高速に解くことができます。

【図】

図:数理最適化の流れ

お問い合わせ