🔢 mathematics

A Surface-Based Formulation of the Traveling Salesman Problem

この論文は、従来の辺の選択に代わり三角形の集合を選択して表面を構築し、オイラー特性制約を用いて部分巡回を排除する新しい厳密な巡回セールスマン問題の定式化を提案し、完全な三角形集合では厳密解を与え、デラウナイ三角形分割などの候補集合に制限すれば実用的なヒューリスティックとして機能することを示しています。

原著者： Yılmaz Arslanoğlu

公開日 2026-03-03

📖 1 分で読めます🧠 じっくり読む

CC BY 4.0

原著者： Yılmaz Arslanoğlu

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

この論文は、有名な「巡回セールスマン問題（TSP）」という難問を、「道（線）を選ぶ」のではなく、「面（三角形の集まり）を作る」という全く新しい視点で解こうとする画期的な提案です。

難しい数式や専門用語を抜きにして、日常のイメージに置き換えて説明しましょう。

1. 従来の考え方：「迷路の壁を塗る」

まず、従来の TSP の解き方を想像してください。
セールスマンが街を回り、すべての街を一度だけ訪れて戻ってくる最短ルートを見つける問題です。
これまでの方法は、**「どの道（線）を通るか」**を一つずつ選んでいくアプローチでした。

イメージ: 迷路の壁を塗るようなものです。「ここを通る」「ここは通らない」と、線（道）を一本ずつ選んで、最終的に一つの輪っか（ルート）を作ろうとします。
問題点: 線だけを選んでいくと、「小さな輪っか（部分ループ）」ができてしまい、全体が一つにつながっているか確認するのが非常に難しく、計算が複雑になります。

2. この論文の新しい考え方：「パッチワークの布を作る」

この論文の著者は、**「線を選ぶ」のをやめて、「三角形の布（パッチ）を繋ぎ合わせて、大きな布（表面）を作る」**という発想に変えました。

イメージ: たくさんの三角形の布切れ（パッチ）があります。
- これらをすべて繋ぎ合わせて、**「一枚の大きな布（表面）」**を作ります。
- この布の**「端（境界線）」**が、そのままセールスマンのルートになります。
- 布の**「内側」**は、セールスマンが通らない場所です。

なぜこれがすごいのか？

布の端は自然に一つになる: 布を一枚の大きなもの（ドーナツの穴がない状態）に繋ぎ合わせれば、その「端」は自動的に**「一つの大きな輪っか」**になります。
小さな輪っかが消える: 従来の方法で起こりうる「小さな部分ループ」は、布の端が一つにまとまるという性質上、自然に防がれるのです。

3. 具体的な仕組み：「魔法の消しゴム」

この方法には、とても面白い「計算の魔法」が使われています。

三角形を選ぶ: 複数の三角形を選びます。
重なり合う部分は消える: 2 つの三角形が隣り合って重なり合う「内側の線」は、お互いに打ち消し合います（消えます）。
残るものだけ: 最終的に残るのは、**「布の端（境界）」**だけになります。
結果: 計算機は「内側の線」を無視して、「端の長さ」だけを計算すればいいので、最短ルートを効率よく見つけることができます。

4. 現実世界での使い方：「地図の選び方」

この方法は、すべての三角形の組み合わせを試すと計算が膨大になりすぎて現実的ではありません（小さな問題なら完璧に解けます）。

そこで、**「必要な三角形だけを選ぶ」**という工夫をしています。

デラウナー三角分割: 街の地図を、無駄のない三角形の網目（デラウナー三角分割）に分割します。
布を編む: この網目の中から、最適な「布（表面）」を選び出します。
効果: これにより、複雑な計算を大幅に減らしつつ、非常に正確なルートを見つけることができます。特に、街が平面的に広がっている場合（ヨーロッパの都市など）に非常に強力です。

5. まとめ：なぜこれが重要なのか？

この論文は、**「問題を解く視点を変えるだけで、難問が簡単になる」**ことを示しました。

従来の方法: 「線」を一生懸命繋ぎ合わせて、ループを作ろうとする（大変）。
新しい方法: 「面（布）」を作って、その「端」が自然にルートになるのを待つ（賢い）。

まるで、「糸を一本ずつ結んで輪っかを作る」のが大変なら、「布を一枚作って、その端を切る」方が簡単なのと同じです。

この「布を作る（表面を構築する）」というアイデアは、今後、より複雑な物流やネットワーク設計の問題を解くための、新しい強力なツールになる可能性があります。

論文要約：表面ベースの巡回セールスマン問題（TSP）定式化

著者: Yılmaz Arslanoğlu (ハンブルク独立研究者)
概要: 本論文は、巡回セールスマン問題（TSP）に対する新しい**「表面ベース（Surface-Based）」**の定式化を提案しています。従来の「辺の選択」に基づくアプローチから脱却し、「三角形の集合（表面）の構築」というトポロジー的な視点に転換することで、部分巡回除去制約（Subtour Elimination Constraints）を不要にする混合整数線形計画（MILP）モデルを構築しました。

以下に、問題定義、手法、主要な貢献、結果、および意義について詳細をまとめます。

1. 問題の定義と背景

従来のアプローチ: TSP は通常、グラフ $G=(V, E)$ $G = (V, E)$ 上で最小重みのハミルトン閉路（サイクル）を辺の集合 $E'$ $E^{'}$ として選択する問題としてモデル化されます。
- 課題: 局所的な次数条件（各頂点に 2 本の辺が接続）を満たすだけでは、大域的な連結性（1 つのサイクルであること）が保証されません。これを保証するために、指数関数的な制約（部分巡回除去制約）や、弱いがコンパクトな制約（MTZ 制約やフローベース制約）が必要となり、計算コストや緩和の緩さが課題となっていました。
本論文のアプローチ: 1 次元の辺の列ではなく、**2 次元の表面（三角形の集合）**を構築し、その表面の境界（Boundary）がハミルトン閉路となるように定式化します。

2. 手法と理論的枠組み

2.1 双対グラフとインシデンスグラフ

提案手法は、三角形（面）と辺（エッジ）の双対性を活用した**二部グラフ（Incidence Graph）**上で問題を再定義します。

ノード: 三角形の集合 $U$ と、元のグラフの辺の集合 $W$ 。
アーク: 三角形 $t$ が辺 $e$ を含む場合、 $(t, e)$ の接続関係。
最適化対象: 連結した三角形のサブセットを選択し、その境界の総長を最小化します。

2.2 境界相殺（Boundary Cancellation）と目的関数

目的関数は、選択された三角形と辺の重み付けに基づき設計されています。

内部辺の相殺: 2 つの三角形に共有される内部辺は、正味の重み計算において互いに打ち消し合います（コスト $2L_e$ と利益 $L_e$ の組み合わせ）。
境界辺の残存: 表面の境界にのみ位置する辺のみが正味の重みとして残ります。
結果: 目的関数の最小化は、結果として得られる表面の境界の総長（＝巡回経路の長さ）の最小化と等価になります。

2.3 位相的制約（トポロジカル制約）

ハミルトン閉路を正しく導くために、以下の 4 つの構造制約を課します。

大域的木連結性（Global Tree Connectivity）: 選択された三角形と辺の集合が、双対グラフ上で単一の連結木（Tree）を形成することを保証します。これにより、表面が位相的に「円盤（Disk）」であることを保証します。
基数制約（Cardinality）: 頂点数 $N$ に対して、三角形が $N-2$ 個、辺が $2N-3$ 個となるように制約します（円盤の三角分割の性質）。
多様体規則性（Manifold Regularity）: 各辺が最大 2 つの三角形にしか接続できないように制限し、非多様体構造を排除します。
局所連結性（Euler Filter）: 各都市（頂点）の近傍が連結であることを保証するために、局所的なオイラー指標 $\chi(H_v) = 1$ を課します。これにより、「蝶結び（Bowtie）」のような特異点や、頂点周りで分断されたリンクを排除し、単一のパスを形成させます。

3. 主要な貢献

等価性の証明: 完全複体 $K_{All}$ における最小重みハミルトン閉路と、二部インシデンスグラフにおける最大重み双対木との等価性を示しました。
部分巡回除去の不要化: 従来の MTZ 制約やフロー制約に代わり、**「木制約＋オイラー指標フィルタ」**という組み合わせで、部分巡回を排除する新しい MILP 定式化を提案しました。
入力非依存性: 候補三角形集合 $T$ をブラックボックスとして扱います。完全集合（ $K_{All}$ ）でも、デラウナイ分割（Delaunay）や貪欲法による疎な集合（Sparse Set）でも、モデル構造を変えずに適用可能です。

4. 計算結果と検証

4.1 正確性と一般性

位相的検証: 重なり合う六角形などのトポロジカルなテストケースで、最適表面が正しく抽出されることを視覚的に確認しました。
非計量空間: 三角形不等式を満たさないランダムな非計量インスタンスでも、トポロジカルな連結性のみで最適解を導出できることを確認しました。

4.2 性能比較（TSPLIB ベンチマーク）

デラウナイ分割で疎化した入力に対して、従来の「Lifted-MTZ」モデルと比較しました。

小規模〜中規模（N=52〜130）: 表面ベースのモデル（特にフローベースの木制約）は、多くのケースでルートノード（分枝限定木の深さ 0）で最適解を求解しました。
- 例：st70 (N=70) で、Lifted-MTZ は 2,936 ノード必要だったのに対し、Surface-Based-Flow は 1 ノードで解決。
- 例：ch130 (N=130) で、Lifted-MTZ は 16,058 ノード必要だったのに対し、Surface-Based-Flow は 1 ノードで解決。
大規模（N=442）: pcb442 において、Surface-Based-Flow は 142 ノードで解決しましたが、Surface-Based-MTZ は 23,205 ノードを要しました。フローベースの連結性制約の方が、緩和が強く、分枝限定木が小さくなる傾向が確認されました。

4.3 難易度の高いインスタンスと入力依存性

Tnm199（難解なインスタンス）: デラウナイ分割では 6.17% のギャップでしたが、**貪欲三角分割（Greedy Triangulation）**を入力として用いることで、ギャップを 1.85% まで縮小し、Christofides ヒューリスティック（5.69%）を上回る結果を得ました。これは、モデルが入力幾何の質に敏感に反応し、より良い経路を発見できることを示しています。
p100（平行線退化）: 点が平行線上に配置された退化した幾何構造では、三角分割ベースの候補集合が機能しませんでした（ギャップ 14%〜119%）。これは、疎な候補集合の限界を示しており、入力幾何の性質が解の質に直結することを浮き彫りにしました。

5. 意義と結論

パラダイムシフト: TSP の最適化対象を「辺の選択」から「表面の構築」へと転換しました。これにより、辺ベースの定式化では扱いにくい幾何学的・位相的制約を、モデルの核心を変えずに統合できる可能性を示しました。
実用性: 完全集合を用いた厳密解法は計算的に困難ですが、デラウナイ分割などの疎な候補集合を用いたヒューリスティックとして非常に有効です。特に、フローベースの連結性制約を用いることで、コンパクトな静的 MILP として、既存の手法よりも強力な緩和と効率的な求解を実現しています。
今後の展望: 大規模インスタンスでの完全収束には課題が残りますが、この表面ベースの枠組みは、TSP の変種問題や、複雑な幾何的制約を持つ経路計画問題に対する強力な基礎となる可能性があります。

総評:
本論文は、TSP 解決に対するトポロジー的なアプローチの新たな可能性を提示した画期的な研究です。特に「部分巡回除去制約を不要にする」という点と、「入力幾何の質（候補集合）によって解の質が向上する」という特性は、従来のエッジベースの手法とは異なる洞察を提供しており、組合せ最適化と計算トポロジーの融合において重要な一歩と言えます。