読み方：じゅんかいセールスマンもんだい

巡回セールスマン問題【traveling salesman problem】TSP

巡回セールスマン問題とは？

組み合わせ最適化問題の一つで、複数の都市を一度ずつ訪れて出発点に戻るとき、移動距離や費用の合計が最小となる巡回経路を求める問題。単純な設定ながら、地点数が増えると計算量が急増するため、効率的な解法を巡ってコンピュータ科学で長年に渡り研究されてきた。

都市数が少ない場合はすべての順序を列挙して最短経路を選べるが、都市数が増えると組み合わせ数は階乗的に増大する。例えば10都市でも数百万通りとなり、20都市を超えると現実的な時間で総当たり計算を行うことは難しくなる。

計算量理論における「NP困難問題」として知られており、厳密解を求めるアルゴリズムだけでなく、近似解やヒューリスティック手法の研究対象となっている。代表的な手法には分枝限定法、動的計画法、遺伝的アルゴリズム、焼きなまし法などがあり、最適解に近い経路を効率的に探索する工夫が行われる。

応用範囲は広く、物流配送のルート設計、半導体製造における加工順序の最適化、プリント基板の穴あけ順序、DNA配列解析など、順序決定と移動コスト最小化を伴う問題に対応づけて利用される。距離だけでなく時間制約や容量制限などの条件を追加した拡張問題も多く提案され、現実の計画問題に合わせたモデル化が行われている。