交通・物流分野等において従来より大規模な順列型組合せ最適化問題を解くための新手法を開発

背景

昨今、持続可能な社会の実現が世界共通の認識課題となっています。NTTデータグループにおいても新中期経営計画で「Realizing a Sustainable Future」を掲げ、サステナブル社会の実現を目指しています。持続性を実現するうえで、消費するリソースやエネルギーの無駄を最小化しながら価値を最大化することは、重要な要素の一つです。例えば社会課題の一つとされている物流の2024年問題において、最適な人員配置、最適なルートによる最短時間での配送を実現することは労働環境の改善や温室効果ガス排出量の削減などにつながります。
こうした社会情勢やコンピューティング技術の進歩を背景に、いわゆる「最適化問題」への取り組みが再び注目を集めています。例えば、量子アニーラーと呼ぶ組合せ最適化問題に特化した量子コンピューターが登場し、年々性能を向上させています。しかし、実ビジネスへ応用するには要求性能と実性能にまだ差があることも事実です。
NTTデータグループと広島大学はこうした課題をソフトウエア面で解決する観点から、順列生成イジングモデルのサイズと要求解像度を大幅に削減する「dual-matrix domain-wall法」を開発しました。同じハードウエアでも、より大規模な最適化問題に適用できるようになります。
NTTデータグループは、2023年4月に当社イノベーションセンタによる先進技術導入支援サービス^注12においてコンサルティングサービスの提供を開始しています。今回の取り組みは、その一環として実施している広島大学との共同研究成果になります^注13。

成果概要

順列型組合せ最適化問題は、n！通りある順列の中から最適なものを選ぶ問題で、その代表格が巡回セールスマン問題です。必要とされる範囲は幅広く、例えば製造工程のスケジューリング最適化など、数多くの業務へ応用が可能です。しかし、n！通りの膨大な組合せの中から最適なものを見つけることは容易ではなく、膨⼤な計算時間を要します。
このような順列型組合せ最適化問題を量子アニーラーで解く場合、順列をイジングモデルとして表現する必要があります。同じ順列であっても、その表現方法により、イジングモデルのサイズと要求分解能が異なります。量⼦アニーラーの規模と計算精度には制限があるため、大規模な順列型組合せ最適化問題を解くには、イジングモデルのサイズと要求分解能をハードウエア仕様の制約以下まで小さくする必要があります。
今回開発したdual-matrix domain-wall法では、順列の表現に必要な変数の数は約3倍になりますが、順列生成イジングモデルのサイズをone-hot法の「n3」のオーダーから「n2」のオーダーへ、要求分解能も「n」のオーダーから「定数」へ大幅に削減できます。
効果を定量的に示すために、すべての頂点を一度ずつ訪問する巡回セールスマン問題の無向グラフの頂点数（訪問する都市数）を40/100/200/300と順次増やしてイジングモデルのサイズを計算したところ、グラフの頂点数が多くなるとともに従来のone-hot法ではサイズが急激に増加しますが、今回開発したdual-matrix domain-wall法は、頂点数の増加にともなうサイズの増加が緩やかであり、無向グラフの頂点数が300のときは、従来のone-hot法に比べて25分の1以下に削減できました。

図：無向グラフの巡回セールスマン問題を解くイジングモデルの二次項の個数

今後について

NTTデータグループでは、本手法に限らず、量子アニーラーや組合せ最適化問題に対するさまざまな新手法の開発・適用を進めていきます。今後、グローバルにおいて量子コンピュータ／次世代アーキテクチャ・ラボのサービスを展開し、新たな手法によるお客さまの業務改善案件で、2026年までに100件以上の受注を目指します。

参考発表

広島大学とのこれまでの取り組みに関する発表。
数理最適化によるプリント基板加工の生産効率改善の実現
組合せ最適化問題の計算手法「アダプティブ・バルク・サーチ」の実行環境を無償公開
GPUの計算性能を最大限活用する組合せ最適化問題の新解法を公開