トラベリング・セールスマン問題（TSP）とは？定義・歴史・解法と最適化

TSP（巡回セールスマン問題）の定義・歴史・代表的解法と最適化手法を図解でわかりやすく解説。実務応用やアルゴリズム比較も掲載。

トラベリング・セールスマン問題（TSPと呼ばれることが多い）は、コンピュータ・サイエンスやオペレーション・リサーチの分野における古典的なアルゴリズム問題です。これは最適化に焦点を当てています。この文脈では、より良い解決策とは、より安く、より短く、より速く解決することを意味することが多い。TSPは数学的な問題です。それは、ノードの集合の位置を記述するグラフとして最も簡単に表現されます。

定義（形式的説明）

一般にTSPは次のように定義されます。重み付き完全グラフ G=(V,E) が与えられたとき、すべての頂点をちょうど一度ずつ訪れ出発点に戻る巡回（ハミルトン巡回）であって、辺の重みの合計が最小になるものを求める問題です。辺の重みは距離やコストを表し、対称（i→j と j→i が等しい）か非対称（異なる）の場合があります。距離が三角不等式を満たす場合は metric TSP（計量TSP） と呼ばれ、特殊な性質と近似アルゴリズムが存在します。

歴史的背景

巡回セールスマン問題は、1800年代にアイルランドの数学者W.R.ハミルトンとイギリスの数学者トーマス・カークマンによって定義された。ハミルトンのアイコシアン・ゲームは、ハミルトンのサイクルを見つけることに基づいたレクリエーション・パズルであった。TSPの一般的な形式は、1930年代にウィーンやハーバードの数学者、特にカール・メンガーによって最初に研究されたようです。メンガーは問題を定義し、明白なブルートフォースアルゴリズムを考慮し、最近傍ヒューリスティックの非最適性を観察しました。

我々はメッセンジャー問題をメッセンジャー問題と呼ぶ(実際にはこの問題は各郵便配達人によって解かれるべきであるが，いずれにせよ多くの旅行者によっても解かれるはずである)．もちろん，この問題は無限に多くの試行によって解くことができる．与えられた点の順列の数よりも試行回数を少なくするルールは知られていません．最初に始点から最も近い点に行き、次にこの点に最も近い点に行く、などというルールは一般的に最短ルートにはならない.

プリンストン大学のハスラーホイットニーは、すぐ後に名前の旅行セールスマンの問題を導入しました。

計算複雑性

TSPの最適化問題は一般に NP困難（NP-hard） であり、その決定版（与えられた長さ以下の巡回が存在するか） は NP完全（NP-complete） です。これは、入力サイズが増えると最適解を求める計算量が急増することを意味します。全探索（全順列を試す）では計算量は O(n!) で、実用上は非常に大きい n に対して現実的ではありません。

代表的な正確解法（厳密解）

• ブルートフォース（全順列探索）: 小さな n にのみ実用的。
• 動的計画法（Held–Karp 法）: 時間計算量 O(n^2 2^n)、メモリ O(n 2^n)。中程度の n（数十程度）まで現実的。
• 分枝限定法（Branch and Bound）: 上界・下界を用いて探索空間を剪定。実データではかなり効率的になることが多い。
• 分枝カット法（Branch-and-Cut）: 線形計画緩和とカット生成（部分巡回除去不等式など）を組み合わせた現在の最先端の実装。Concorde ソルバーなどが有名。
• 整数線形計画法による定式化: Miller–Tucker–Zemlin（MTZ）制約や部分巡回除去制約を用いる。

ヒューリスティックと近似アルゴリズム

大規模インスタンスに対してはヒューリスティック（実用的に良い解を速く得る方法）や近似アルゴリズムが使われます。代表例：

• 最近傍法（Nearest Neighbor）: 実装が簡単だが局所最適に陥りやすい。
• 挿入法（Nearest/Greedy/Christofides の前処理など）
• 2-opt / 3-opt: 局所探索に基づく改善手法。辺を交換して改善する。実務でよく使われる。
• Lin–Kernighan アルゴリズム: 高性能な局所探索で、実際的に非常に良い解を得ることで知られる。
• メタヒューリスティクス: シミュレーテッド・アニーリング、遺伝的アルゴリズム、アリコロニー最適化など。

近似アルゴリズムに関して重要な理論結果として、計量（距離が三角不等式を満たす）対称TSPに対してはChristofides のアルゴリズムがあり、最適解の長さの最大 1.5 倍の解を多項式時間で得られることが保証されています。一方、一般の（非計量）TSP は定数倍の近似アルゴリズムが存在しない（P≠NP のもとで）ことが示されています。

整数計画とカット平面

厳密解法としては、TSP を整数線形計画（ILP）で定式化し、線形計画（LP）緩和を解いてから不等式（カット）を追加して解を絞り込む手法が有力です。TSP ポリトープ（すべての有効なツアーの凸包）に関する研究は深く、様々な有効不等式（部分巡回除去不等式、スター不等式、パス不等式 など）が知られています。

実用上の応用例

• 配送・配達ルーティング（ラストマイル配達、ドローン配達など）
• 製造業における工具経路最適化（NC加工、プリント基板の穴開け順序など）
• 遺伝子配列の再構成や配列アセンブリでの近似問題
• 物流の最適化、営業巡回、センサー巡回計画など

実装とソフトウェア

研究・実務でよく使われるソルバーやライブラリには、Concorde（厳密解）、LKH（Lin–Kernighan 改良版、良好な近似解を高速に得る）、各種商用最適化ソルバー（CPLEX、Gurobi など）での ILP モデリングがあります。問題サイズや要求精度に応じて適切な手法を選択します。

まとめ（ポイント）

• TSP はグラフ上のハミルトン巡回を最小化する古典的な最適化問題。
• 一般には計算困難（NP困難）だが、特別な場合（計量TSP）では良い近似アルゴリズムが存在する。
• 小～中規模では厳密解法（動的計画法、分枝限定、分枝カット）が有効。大規模ではヒューリスティックやメタヒューリスティクスが現実的。
• 実世界の多くの応用で重要かつ直接的に役立つ問題であり、アルゴリズム研究の試金石となっている。

このページはTSPの定義・歴史・主な解法と応用を概観しました。より深い理論や実装に興味がある場合は、上で触れたアルゴリズム名やソルバー名を手がかりに文献や実装例を参照してください。

質問と回答

Q: トラベリングセールスマン問題とは何ですか?

Q: TSPはどのように表現されるのですか?

Q: TSPを最初に定義したのは誰ですか?

Q: 1930年代、誰がさらに研究したのですか?

Q: その後，ハスラー・ホイットニーは何を発表したのですか?

Q: 「より良い解」とはどういう意味か?

Q:メンガーがTSPを研究する際に、自明と考えたアルゴリズムは何か?

文字で検索