k-means++ 階層クラスタリングとニューラル組合せネットワークを用いたマルチデポ閉路型複数巡回セールスマン問題の解法

多数のドライバーのための賢い経路

宅配バンから配送ドローン、災害支援車列に至るまで、計画者はしばしばパズルに直面します。異なる拠点から出発する複数の車両が、何百、何千もの訪問先の作業をいかに無駄なく分担するか、つまり燃料や時間を浪費しないようにするにはどうすればよいか。 本論文は、そのパズルを分割して征服する新しい方法を提示します。古典的なクラスタリングの手法と最新のニューラルネットワークを組み合わせることで、コンピュータが何分・何時間もかかる代わりに数秒で効率的な経路を設計できるようにします。

多数のデポと多数のドライバーがもたらす課題

本研究は、有名な巡回セールスマン問題の難しいバリエーションに取り組みます。そこでは一人の旅行者ではなく複数がおり、それぞれが自分の拠点から出発して戻ります。彼らは協力して、すべての都市をちょうど一度ずつ訪れつつ総移動距離をできるだけ短くしなければなりません。この設定は、トラック車隊の調整、ロボット群、あるいは領域内で仕事を分担する航空ドローンの管理といったタスクを模しています。都市やドライバーの数が増えると可能な経路の組み合わせは爆発的に増え、厳密解法は遅すぎるようになり、従来の試行錯誤的探索法は苦戦したり、解の品質を速度と引き換えにしなければならなくなります。

古典的探索と単純分割の限界

長年にわたりエンジニアは遺伝的アルゴリズム、アントコロニー探索、粒子群最適化などの「メタヒューリスティクス」に頼ってきました。これらは自然現象を模倣して多数の候補経路を探索し徐々に改善します。柔軟性はあるものの二つの大きな欠点があります。ひとつは解の良さに関する確固たる保証がないこと、もうひとつは大規模な地図では非常に遅くなることです。特に各新しい課題ごとに探索を最初からやり直す必要がある場合に問題になります。よく使われる高速化策として、まず k-means のような手法で都市を領域にクラスタリングし、各クラスタ内で小さな問題を解く方法があります。分割してから解く戦略は有用ですが、最終的な品質は内部で使われる探索手法に制約され、より良い経路を目指すほど実行時間がさらに増えることが多いという限界があります。

ネットワークに経路を学習させ、拡張を助ける

近年、別のアイデアが登場しました。ニューラルネットワークを訓練して直接良好な経路を出力させるという方法です。多くの都市配置の例で学習した後、この種のネットワークは言語モデルが文を書くのと同様に、単一のフォワードパスで全巡回路を提案できます。これらのニューラルソルバは適度なサイズの単一ドライバー問題で非常にうまく機能しますが、多数のドライバーを調整する場合や訓練時よりはるかに大きな都市集合を扱う場合にはつまずきます。著者らの重要な工夫は、このようなニューラルソルバを慎重な二段階プロセスの中に組み込み、巨大なマルチドライバー課題をネットワークが快適に処理できる小さな馴染みのある部分問題群に変形することです。

二段階法の仕組み

提案手法 KHC-NCN は、改良版 k-means クラスタリングをまず用いて都市を各デポやドライバーに割り当てることから始まります。もし得られた領域にニューラルソルバが確実に扱えないほど多くの都市が含まれていれば、その領域は自動的にさらに小さなピースに分割され、各ピースはネットワークが訓練で見たサイズに近づけられます。各ピース内の座標は標準正方形に再スケーリングされ、訓練データにより近い形に整えられます。ニューラルネットワークはその後、各小領域ごとに経路を生成します。最後に、マージステップでこれらの部分経路を簡単な幾何学的ルールを用いて縫い合わせ、余分な距離が最小となるように各ドライバーの単一の閉ループにまとめます。

実ベンチマーク地図での速度と品質

著者らは、ルーティング研究で広く使われる公開ベンチマークセットからの標準的な地図群で手法を検証しました。多くの既存探索手法、トップレベルの手作りソルバ、別のニューラルアプローチと比較しています。異なる地図サイズとドライバー数を含む44のテストケースのうち、彼らの手法はほぼ4分の3のケースで総距離を短縮し、しかも劇的に高速であることが多く、しばしば桁違いの速さを示しました。都市数が数百〜数千に上るほど、本手法は特に堅調であり、多くの古典的手法が遅くなったり弱い経路を示した状況でも優位を保ちました。

実世界のルーティングにとっての意味

簡潔に言えば、本研究は高速なニューラルネットワークに多数の小さく良形な部分問題を解かせる方が、ひとつの巨大な問題に多くの時間を費やすより有利であることを示しています。ネットワークが得意とする領域に合わせて都市をクラスタリングし、部分解を巧みに結合することで、短く迅速に計算できる経路を提供します。物流、マルチロボット計画、緊急対応といった応用において、これは既存ツールよりも車両とエネルギーをより有効に使える、ほぼリアルタイムの経路計画を実現する実用的な方法を示唆します。

引用: Zhao, CS., Wong, LP. & Fung, C. Solving multi-depot closed-path multiple traveling salesman problem using k-means++ hierarchical clustering and neural combinatorial networks. Sci Rep 16, 15631 (2026). https://doi.org/10.1038/s41598-026-45824-3

キーワード: 車両経路最適化, ニューラルネットワーク, クラスタリング, 最適化, 物流