巡回セールス問題とは、複数の都市をすべて1回ずつ訪れて元の場所に戻る際の最短移動ルートを求める組み合わせ最適化問題です。都市数が増えると計算量が暴走する組合せ爆発が発生するため、NP困難な問題として知られています。配送ルートの最適化など実社会で広く応用され、遺伝的アルゴリズムや強化学習を用いた解法も研究されています。
巡回セールス問題とは
複数の拠点を一度だけ訪問して最初の場所へ戻る時の最短移動ルートを計算する、代表的な組み合わせ最適化問題のことです。
詳しく解説
訪問すべき都市の数が増えるにつれて、考えられるルートの選択肢が指数関数的に増大し、計算量が爆発的に増える組合せ爆発という現象が発生します。理論上、すべての選択肢を調べる手法では現実的な時間内に解けないケースが多く、計算複雑性理論においてNP困難な問題に分類されます。計算機科学やAIの分野では、現実的な時間内で十分実用的な解を導き出すため、近似アルゴリズムの利用や、生物の進化を模した遺伝的アルゴリズム、機械学習の一種である強化学習を応用した探索手法の研究が盛んに行われています。
具体例・使われ方
配送トラックが複数の荷受先を最も効率よく回る配送ルートの自動設計や、プリント基板に穴をあける産業用ロボットの最小移動経路の設定、観光地を無駄なく巡る旅行プランの作成などに活用されています。またAI分野では、強化学習を活用して複雑な都市ネットワークの最適な移動順序を学習させるシステムなどで利用されます。
似た用語との違い
指定されたすべての拠点を一巡する最短ルートを探す巡回セールス問題に対して、出発地と目的地という特定の2点間における最も速い移動経路を求める問題は最短経路問題と呼ばれます。最短経路問題は都市数が増えても比較的容易に厳密な最適解を計算できますが、巡回セールス問題は組み合わせが爆発するため計算難易度が大幅に高くなります。
注意点
拠点の数が大きくなると、コンピュータを使っても理論上の「絶対に100パーセント正しい最短ルート」を短時間で求めることは困難です。そのためAIや最適化ツールが出力する解は、厳密な最適解ではなく「現実的な時間で得られた十分に良い近似解」である場合が多い点に注意が必要です。