目次

• ビジネスと数理最適化
• 数理最適化とは？
• 伸光製作所におけるプリント基板の製造業務
• 実証実験の結果
• 技術的な工夫点
• NTTデータでの今後の取り組み

ビジネスと数理最適化

昨今、DXやAI導入など、先進的なIT技術による業務効率化や社会課題の解決が進んでいます。実は、これらと深く関連しつつ、ビジネス上の痒いところに手が届く技術として、数理最適化（Mathematical Optimization）が注目され始めています。
数理最適化を一言で表すと、「コスト（or利益）といった指標を最小化（or最大化）するために、コンピュータによって定量的にベストな選択肢を決定すること」といえます。

活用できるイメージしやすいシーンを挙げると、

• 都市全体のCO2の排出量や渋滞が最小化されるように、自動車の交通流制御を行う。
• 工場で生産効率が最大化されるように、サプライチェーン・物流の計画を策定する。
• シフト・配送日・労働条件などを守りつつ、配送担当者をトラックや現場へアサインする。

などがあり、ビジネスの現場の課題に対し、非常に大きな役割を果たすことがわかります。

数理最適化は幅広い応用先を持つ一方で、そもそもどのような技術か・メリットの大きい導入先は何か・どのような流れで開発されるのかなど、初めて聞く方には想像しづらい点も多くあります。この記事では、数理最適化の概要と、ビジネスでの応用イメージが分かるように、NTT DATAでの具体例を交えて解説します。

数理最適化とは？

「数理最適化」という言葉を初めて聞いた人にとっては、何やら馴染みのない未知の技術が新しく出現したかのように思えるかもしれません。しかし、実は中学校や高校の数学でも、非常にシンプルではありますが、数理最適化の例が取り上げられています。

問題：りんごを120円に設定すると、1日に40個売れ、120✕40=4,800円が売上になることがわかっています。経営者はりんごの価格の再設定を考えていますが、一方の消費者は価格が高騰すると買い渋ります。仮に10円だけ値上げされると、1日の販売個数が2個減ることがわかっています（逆に10円値下げすると2個増える）。経営者が売上金額を最大にするためには、りんごを何円に設定すればよいでしょうか？

答え：10円値上げの回数がx回であり、りんごの価格を120+10x円に設定するとしましょう。40個が売れていた状態から、1回の10円値引きあたり2個だけ販売個数が減るので、x回の10円値上げで40-2x個に変化します。「売上=価格✕個数」であるため、(120+10x)(40-2x)=-20x^2+160x+4800が売上です。この二次関数を学校で学ぶ手法により最大化するとx=4であり、りんごを160円に設定して32個を売り、5,120円の売上とすることが最適な選択です。

りんごの価格をコントロールする未知の変数xによって売上を表現（二次関数）し、その最大解を決められた手順（二次関数最大化のための平方完成や微分）を用いて、計算しています。
もしも経営者が価格設定を闇雲に試行錯誤すると、その分売上が落ち込む日が生じたり、現場やお客さまへの価格変動による負担が生じたりします。
一方、数理最適化では与えられたデータを用いて、「何をどう設定すれば売上が上がるか？」という疑問に定量的に応えており、売上の最大化やコストの削減などに対し、幅広く役立ちます。

ここでは説明のために非常にシンプルな一例を挙げましたが、実社会における課題は遥かに複雑です。値上げに対する個数の変化が一定ではない場合や、お客さまからの信頼といったデータ化が難しい要素を含む場合、業務上の法律・物理的制約・安全性などに由来する、複雑な制約を守る必要がある場合などがほとんどです。また、学校で学んだ手順だけで簡単に最適解が計算できることも、滅多にありません。そのため、数理最適化の応用には、業務の課題を定量化しきるレベルでの綿密なビジネス理解力と、それらを数理モデル化した後に計算基盤上へ効率的に実装する技術力の、両方の専門性が求められます。

伸光製作所におけるプリント基板の製造業務

NTT DATAでは、お客さまのビジネス課題に対して、数理最適化の技術を用いて解決する取り組みを行っています。本章では、最近報道発表した具体的な案件をもとに、数理最適化のビジネス活用事例を説明します（※1）。

伸光製作所では、プリント基板を製造しています。プリント基板は、半導体や抵抗器、コンデンサーなどの電子部品を配置して、相互に接続する基材であり、ほぼすべての電子機器に搭載されています。昨今の自動車のEV化や自動運転の進歩、5G／6Gなどの次世代通信による高速化、IT社会を支えるデータセンタの増加など、先進的なIT技術を社会実装していく中で、プリント基板への需要は増加を続けています。

プリント基板自体の複雑度も高まる中で、効率的な生産を続けるためには、加工装置の物理的な高性能化だけではなく、その動作順序や作業工程といった、業務プロセス自体の最適化が重要です。プリント基板には部品を設置するための数万点以上からなる大量の穴が存在し、予め決められた順序に沿って、ドリルを移動させて開けていきます。しかし、決めた順序によっては、ドリルが穴を巡るための移動時間が非常に長くなり、1枚を作り終えるまでの生産効率が落ちてしまう問題が生じます。

実は、この訪問順序を探索する問題は、数理最適化の問題であると捉えることができます。ドリルが移動する距離を「最小化したい定量的な指標」として定めて、どの穴に対してどの順序で訪問するのかを計算します。

実証実験の結果

技術的観点の前に、先に開発したプログラムによる実証実験の結果から紹介します。

今回は、お客さまの現場にて作業員の方が手軽に動かしたいという要望など、さまざまなヒアリングを行った後に、下記のような通常のデスクトップPC上で動くプログラムをC++で開発しました（※2）。

• OS：Windows 10 Pro Workstations用
• CPU：Intel Xeon W-2223（4コア8スレッド、3.6GHz）
• メモリ：32GB

訪問順序の探索対象となる穴の配置や座標の数は、プリント基板ごとに大きく異なります。下の図では、約10,000点からなる配置での実施例を紹介します。

10,000点の穴の座標（9つのゾーン制約を含む）に対し、本技術で順序の探索を行った結果

この探索によって、現場で行っていたドリルによる加工時間を、次のように削減できました。

また、実際のビジネスの現場で活用する際には、数理最適化部分だけが課題になるのではなく、人手で行っていた作業工数の短縮も重要です。プリント基板の場合、後述するゾーンと呼ばれる座標情報を人手で付与していましたが、目視での作業に手間がかかるため、その自動化のプログラムを作成しています。最終的には、業務の現場で作業員の方がデスクトップPCで本プログラムを利用する際の工数が削減できるよう、ファイルを置いてクリックするだけで計算結果が全て得られる仕様とし、使い勝手の良いものに仕立てました。

技術的な工夫点

最後に、このプログラム開発における、技術的な工夫の一部を大まかにと説明します。この章は、アルゴリズムやデータサイエンスの知識を前提とした技術者向けに書いているため、必要に応じて飛ばしながらご覧ください。

距離基準の設計について

まず、距離を測定する場合には、しばしばユークリッド距離が利用されることがあります。平面上の物理的な移動を考えているため、一見妥当な基準に見えるかもしれませんが、実はドリルの移動のメカニズムを考えると問題に気づきます。ドリルが平面上を移動する際には、東西に移動するモーター、及び南北に移動するモーターの2つを同時に動かして、斜めの移動を実現しています。したがって、点(x_i, y_i)から点(x_j, y_j)へ斜めに移動するときには、点iと点jのうちの東西側もしくは南北の長い方である max(|x_i-x_j|, |y_i-y_j|)に依存します。これは、ユークリッド距離ではなくチェビシェフ距離とよばれる基準です。目についた距離を最小化の対象にすると、現実の対象と数理最適化の間でギャップが生じてしまうように、定めたモデルが真に最適化したい対象か検討することは、要件定義における重要なポイントです。

さらに深掘りすると、ドリルは各モーターにより等速直線運動をしているのではなく、速度が一定ではないことに注意が必要です。距離を速さで割れば時間になるため、速さが一定の等速直線運動ならば距離の最小化が時間の最小化に直結しますが、速度が一定ではない場合には必ずしもそうであるとは限りません。速い速度を維持できる急行列車と、減加速を繰り返す各駅停車における1kmの移動時間の差のように、止まる点の距離に移動時間が依存してしまいます。この対処として、性能だけを追う場合には、ドリルの移動をデータとして観測し、距離を変数とした加速度や時間を推定するモデルも考えられます。

ただし、このような推定を行うためには、現場でのデータ化などの工数がかかるため、現実的には開発の目的やQCDを含めた総合的な優先度付けが必要です。今回は、コンサルティングしながらいくつかの距離基準を分析比較した結果、実験結果のようにチェビシェフ距離を採用しています。

ゾーン情報の付与について

従来の業務では、プリント基板上の穴に対しゾーンが始めから付与されるのではなく、人が目視により矩形領域を選んでいます。この矩形領域の間は、ある程度離れているため、人の目では分かりやすいですが、配置のされ方が直線で分けられず不規則な場合も多く、単純なしきい値ベースの条件分岐で分けることはできません。

ここでは、矩形領域選択のために、最小全域木を利用したクラスタリングを実装しています。
穴をノードとしチェビシェフ距離をエッジの重みとする無向グラフ上に最小全域木上を構築後、最大辺を順にカットしていき、同一の連結成分からなる座標を一つのゾーンとする手法です。
ただし、全結合グラフを想定した最小全域木の構築では、ノード数Nに対してエッジ数がO(N^2)となり、さらにKruskal法などの計算を要するため、Nが巨大になると計算時間が長くなります。実は、ユークリッド距離に基づく最小全域木を構築したときに、その解はVoronoi図の双対グラフである、Delauney図というグラフ上に存在することが知られています。
Delauney図は、エッジ数がO(N^2)である全結合グラフよりも枝数が遥かに少ないため、最小全域木の構築が高速化されるメリットがあります。今回の距離の基準はチェビシェフ距離であり、正確にはユークリッド距離と異なりますが、類似した結果になるという考察のもと適用しました。

このように、実際のビジネス課題の解決のためには、単に数理最適化のみを導入すれば良いのではなく、その前後に必要な前処理や機械学習を挟むための技術が役立ちます。

経路探索部分

ドリルには、1つのゾーンに属する穴を訪問しきった後に、次のゾーンに移動する制約が課されています。その他にも、実務で扱う数理最適化では、企業やビジネスに応じてさまざまな制約が入る場合がほとんどであり、問題に応じた独自のカスタマイズが必要です。ここでは、プリント基板製造時のさまざまな制約を満たすように、次のような流れに沿って訪問順序の探索を行っています。

ゾーン間最適化

• 同一のゾーンに属する複数の穴の座標を、一つの巨大な塊からなる1つの穴とみなす。
• 塊AとBの間の距離を、A,Bの境界面付近に存在する穴の座標に基づいて定義する（この塊AとBを繋ぐ部分をブリッジと呼ぶ）。
• ブリッジに基づいて、ゾーンの塊に対する最適な訪問順序を求める。

ゾーン内最適化

• ゾーン内に含まれる穴のうち、ブリッジを構成する穴を固定して、穴の最適な訪問順序を求める。
• ブリッジの固定や、最初・最後に訪問する穴の固定には、ダミーノードや負の重みを利用する。
• 訪問順序の探索手法には、よく知られている2-optや3-optなどの近傍を使いつつ、ヒューリスティックな手法を独自に実装。

NTTデータでの今後の取り組み

NTTデータでは、お客さまのビジネスの課題に合わせて、要件定義やヒアリングから実際の開発まで、トータルでサポートできる体制を整えています。

ビジネスで抱える課題が数理最適化と関係するのでは？と思った方から、既存の数理最適化に関わる課題でお困りの方まで、ぜひ気軽にお問い合わせください。