AIデータ分析コラム【11】巡回セールスマン問題　―「物流の2024年問題」解決の鍵―　～物流の2024年問題とは～

巡回セールスマン問題は、複数の地点を巡る最短経路を求める最適化問題で、組合せ最適化問題の一つです[2]。運転手が複数の地点を1回ずつ訪問して戻ってくる際に、最短距離を走行する経路を見つけることが目標です。一見、簡単に解けそうに思えるかもしれませんが、訪問する地点の数が増えると組合せの数が爆発的に増加し、必要な計算時間があまりにも増大するため、現実的な時間で最適解を求めることが難しくなります。

例えば、訪問先が5地点であれば、すべての経路の組合せの数は 5!=120 通りです（この中には同じ経路を逆順にしたものも含まれています）。これなら、パソコンで一瞬で計算できますね。しかし、訪問先が30地点に増えると組合せの数は 2.7×10^32 通りと膨大になり、2020年11月に世界第1位を獲得したスーパーコンピュータ「富岳」を使っても、すべての組合せを計算して最適解を求めるには約1900万年もかかってしまいます。このように巡回セールスマン問題は、計算理論においては「NP困難」という分類に属する、解くのが非常に難しい問題なのです。

一般に、最適化問題の解には厳密解と近似解があります。厳密解とは、すべての可能な解候補を試し、その中から見つける最適解で、これが「正しい」解です。厳密解を求める代表的な手法には分枝限定法があります[3]。一方、近似解とは、計算の効率性を重視した方法で得られる最適解に近い解で、実用的な時間で最適解を求めることが困難な場合に用いられます。局所探索やメタヒューリスティクスなどが代表的な近似解法です。一般には、大規模な問題に対しては近似解法を用いるのが、従来の考え方でした。

厳密解法である分枝限定法は、大規模な問題をより小さな部分問題に分割し（分枝操作）、各部分問題において既知の最適解よりも良い解が得られる見込みがなければ、その部分問題を省く（限定操作）ことで、効率的に最適解を求める方法です。これは、1960年にA. H. LandとA. G. Doigにより提案された歴史の長い手法ですが、2000年代に入ってコンピュータの急速な進歩とアルゴリズムの発展でより大規模な問題にも適用することが可能になったことで、再び脚光を浴び、現在も組合せ最適化問題の解法として主流です。

近年、物流の最適化に新たな可能性をもたらすテクノロジーとして量子コンピュータが注目を集めています。量子コンピュータは、量子力学の原理を計算に応用したコンピュータで、「重ね合わせ」状態を作り出すことで超並列計算が可能になると考えられており、NP困難に属する問題を実用的な時間で解くことが期待されています。特に、巡回セールスマン問題などの組合せ最適化問題は、量子コンピュータの得意分野の一つとされています[4]。既に、一部の量子コンピュータベンダから、商用販売やクラウドサービスの提供が始まっていますが、まだ研究開発段階にあります。本格的に実用化され、特有のアルゴリズムが考案されれば、大規模な巡回セールスマン問題を日常的に短時間で解くことができるようになり、2024年問題対策の1つである輸送・配送ルートの最適化に大きな変革をもたらすことになるでしょう。

本コラムでは、物流の2024年問題の対策のうち輸送・配送ルートの最適化に着目し、その解決の鍵となる巡回セールスマン問題とその解法を紹介してきました。現在は分枝限定法を用いた手法が主流ですが、今後、量子コンピュータを用いた手法が主流になると考えられます。現在実現している量子コンピュータには、数百～数千の量子ビット（量子コンピュータで使用される最小の情報単位）が搭載されていますが、世界の様々な問題を解決するために必要な量子ビット数は数百万個とも言われており、実用化にはまだまだ課題が山積みです。しかし、Googleが2029年までに100万量子ビットを搭載した量子コンピュータの実用化に向けたロードマップを発表するなど、2030年頃には量子コンピュータがビジネスで活用できるようになると期待されています。物流業界においても、今後5年から10年ぐらいで大きな変革がもたらされると考えられます。量子コンピュータを用いて多数の配送先を巡回する最適経路をリアルタイムの交通状況を考慮しながら瞬時に計算し、自動運転車が効率的に商品を配送する、ということが実現するのも、そう遠い未来ではないかもしれませんね。