巡回セールスマン問題

巡回セールスマン問題（TSP)　　　　　【イラスト図解】

英語：travelling salesman problem　　　　中国語：旅行推销员问题

巡回セールスマン問題（TSP)とは

｢1回の旅行において各巡回地点を１度ずつ通過して出発点に戻るという条件のもとに旅行距離(費用又は時間)を最小にする問題．

備考：
いくつかの製品を一巡して生産しもとへ戻る場合に総段取費用を最小にする問題もこれに属する.｣
(Z 8121)
整数計画法などが利用できるが，最適解を効率的に求めにくい問題の一種である．

トラックの輸送経路の計画など，流通管理分野にその種の問題が見いだされる．

巡回セールスマン問題 わかりやすく

巡回セールスマン問題は、複数の決められた地点をセールスマンが巡回して元に戻る際、どう回れば最も移動距離が少ないか、という問題です。これは例えば、地域の移動手段として増えつつある、乗合タクシーやオンデマンドバスの経路を決める際にも応用できる、実用的な問題です。

単純な解き方は、考えられる全ルートの移動距離を計算し比較する、数え上げの方法です。しかし訪問先の数(n)に対し、（出発点や回る向きの違いは無視した）異なるルートの数は(n-1)の階乗(１から(n-1)までの整数を掛けたもの)÷2で、nが増えると急激に増えます。

5地点の巡回ならルートは12(=1×2×3×4÷2)ですが、15地点だとルートは400億以上です。このため訪問先が少ない場合も、単純な数え上げでは事実上解けず、AI等が活用されます。先端技術が身近な問題を解決する一例です。

巡回セールスマン問題