巡回セールスマン問題#
読み: じゅんかいせーるすまんもんだい
英名: Traveling Salesman Problem
別名: TSP
都市の集合および 2 都市間の移動コストが与えられているものとする． この時，セールスマンが全ての都市を 1 回ずつ通って最初の都市に戻ることができるルートのうち， 総コストが最小になるルートを求める問題が巡回セールスマン問題である．
一般に巡回セールスマン問題は，\(V\) を都市の集合，\(c_{ij}\) を都市 \(i,j\) 間の移動コストとして，次のように 0-1 整数計画問題として定式化できる．
(64)#\[\begin{split}\begin{array}{lll}
\min & \sum_{i \in V}{\sum_{j \in V}{c_{ij}x_{ij}}} & \\
\mathrm{s.t.} & \sum_{j=1}^n{x_{ij} = 1} & (\forall{i} \in V), \\
& \sum_{i=1}^n{x_{ij} = 1} & (\forall{j} \in V), \\
& \sum_{i \in T}{\sum_{j \in V \setminus T}{x_{ij}}} \ge 1 & (\forall{T} \subset V), \\
& x_{ij} \in \{0,1\} & (\forall{i,j} \in V)
\end{array}\end{split}\]
なお，ある都市から別の都市へと移動する際に他の都市を経由しなければならない（つまり直接は移動できない）組み合わせがある，あるいは移動方向によってコストが異なるなどの様々な条件を取り入れることがあり，定式化の仕方も様々である．
組合せ最適化問題の代表的な例である巡回セールスマン問題は，配送計画問題やプリント基板へのドリルの穴あけ問題など幅広い分野に応用できる．しかし，大規模である場合厳密解を求めることが非常に困難であることが知られている．このため，短時間で十分に良い解を出す近似解法の研究が盛んに行なわれている．