物流の2024年問題とは
皆さんは、服や日用品、家電などを購入する時、実店舗に行きますか？それともネットショッピングを利用しますか？
近年の急速なデジタル化の進展に伴い、ネットショッピングが日常的な消費行動の一部となってきています。一方でこの便利なサービスを支える物流業界は大きな課題を抱えています。その中でも、最近は「物流の2024年問題」という言葉を耳にすることが多いのではないでしょうか？
2021年の国内貨物の輸送手段は、輸送量（トンキロ）ベースで、自動車が約50%、内航海運が約40%、鉄道が約5%で、全体の半分が自動車でした[1]。この自動車による輸送を支えるトラック運転手の労働環境は、長時間労働の常態化という課題を抱えています。そこで、働き方改革関連法に基づいて、2024年4月より自動車運転業務の年間時間外労働時間の上限が960時間に制限されることになりました。これにより労働環境が改善される一方、何も対策を講じなければ運転手不足による物流の停滞が懸念されています。
このような物流の2024年問題への主な対策には、労働環境の整備、輸送・配送方法の変更、業務効率化のためのDX推進などが挙げられます。本コラムでは、業務効率化の一つとして輸送・配送ルートの最適解導出に必要な概念である「巡回セールスマン問題」とその代表的な解法を紹介します。
巡回セールスマン問題の難しさ
巡回セールスマン問題は、複数の地点を巡る最短経路を求める最適化問題で、組合せ最適化問題の一つです[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年ぐらいで大きな変革がもたらされると考えられます。量子コンピュータを用いて多数の配送先を巡回する最適経路をリアルタイムの交通状況を考慮しながら瞬時に計算し、自動運転車が効率的に商品を配送する、ということが実現するのも、そう遠い未来ではないかもしれませんね。
参考文献
[1] 物流の2024年問題について, 第23回物流小委員会, 国土交通省, 2023年7月20日.
[2] 久保幹雄, "巡回セールスマン問題への招待Ⅰ", オペレーションズ・リサーチ：経営の科学, Vol.39, No.1, 1994年.
[3] 柳浦睦憲, 野々部宏司, "分枝限定法 ―さらなる計算効率の希求―", システム/制御/情報, Vol.50, No.9, 2006年.
[4] 西森秀稔, 大関真行, "量子コンピュータが人工知能を加速する", 日経BP社, 2016年.
執筆者
デジタルAI事業本部 アドバンスデータアナリシスビジネスユニット
川田丈浩（かわたたけひろ）
NTT研究所にてネットワーク設計・評価・管理技術に関する研究開発に取り組み、
現職ではAIデータ分析のビジネス展開に携わっている。
AIデータ分析コラム
このコラムは、NTT-ATのデータサイエンティストが、独自の視点で、AIデータ分析の技術、市場、時事解説等を記事にしたものです。
※本コラムの著作権は執筆担当者名の表示の有無にかかわらず当社に帰属しております。
AIデータ分析シリーズ
- ソリューション
※DeAnoSは日本電信電話株式会社の登録商標です。
※当社とNTTコム オンライン・マーケティング・ソリューション(株)は、TIBCO Spotfireの販売契約を締結しています。
※TIBCOおよびSpotfireは、米国およびその他の国におけるCloud Software Group, Inc.およびその子会社の商標または登録商標です。
