TSP経路最適化

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

TSPは一連の地点と距離が与えられたとき、各地点を1回訪問して出発点に戻る最短経路を求める問題です。組合せ最適化で最も研究されている問題の一つです。

TSPはNP困難であり、大規模インスタンスを多項式時間で解くアルゴリズムは存在しません。n地点で(n-1)!/2の可能な経路があります。実用的解法はヒューリスティックに依存：最近傍法（高速だが最適より約25%長い）、Clarke-Wright節約法、2-opt等のメタヒューリスティック。

TSPはラストマイル配送、フィールドサービス、PCBドリリング、倉庫ピック経路最適化に直接応用されます。10-15%の経路改善でも大幅な燃料・時間節約になります。

Formula: 目標: Σ d(route[i], route[i+1])を最小化 (i = 0..n) 最近傍法: 最も近い未訪問地点を貪欲に訪問 節約法: s(i,j) = d(depot,i) + d(depot,j) − d(i,j)

計算例

出発地(0,0)、4停車(3,4),(6,1),(8,5),(2,7)。最近傍：合計25.1。Clarke-Wrightは23.4のより短い経路を見つけ得ます。

この計算機を使用すべき場面

• 配送ディスパッチャーが10-30箇所の顧客を訪問する1台のドライバーの日次ルートを計画する場合
• フィールドサービスマネージャーがサービスコール間の移動時間を最小化するテクニシャンルートを最適化する場合
• 倉庫エンジニアが複数の通路位置を通る最適なピックパスを設計する場合
• 営業担当者が最小走行距離でクライアントを訪問するマルチシティ出張を計画する場合

避けるべき一般的な間違い

• 最近傍解が最適であると仮定 — 貪欲ヒューリスティックであり最適ルートより20-25%長くなることがあります；常に複数のアルゴリズムを試して比較してください
• 道路ベースのルーティングに直線（ユークリッド）距離を使用 — 実際の走行距離は道路網のために20-40%長くなることがあります；道路ルーティングには可能な限り実際の距離を使用してください
• デポへの復帰旅行を含めるのを忘れる — TSPは出発点に戻ることを要求します；復帰を省略すると総ルート距離が過小評価されます
• 実際にはVRPである問題にTSPを適用 — 容量制約、時間枠、複数車両がある場合は、より良い結果のためにVRPツールを使用してください

結果の解釈方法

• Nearest NeighborとClarke-Wrightの結果を比較：大きく異なる場合、より高度な方法でさらなる最適化の余地があります
• ミリ秒単位の計算時間は、問題規模に対してリアルタイム再ルーティングが実現可能かを評価するのに役立ちます
• ルートマップの視覚化は、ヒューリスティックが生成する交差ルートや不必要なバックトラッキングなどの明白な非効率を特定するのに役立ちます

関連規格・参考資料

• Nearest Neighbor および Clarke-Wright savings (1964) — 本ツールでベンチマークする構築ヒューリスティック
• Lin-Kernighan 局所探索 — 高品質なTSP経路のための事実上の標準ヒューリスティック
• TSPLIB — TSPソルバーの品質比較に使用される標準的な公開ベンチマークライブラリ

よくある質問

どのアルゴリズムを使うべきですか？

15停車未満なら最近傍法が最適の20-25%以内で高速。15-50停車ならClarke-Wright後に2-opt改善で5-10%以内。50+停車ならメタヒューリスティックやGoogle OR-Toolsを使用してください。

TSPと実際の配送ルーティングの違いは？

実際には時間枠、車両容量、交通、一方通行、複数車両が加わります。TSPは基礎ですが実用ソフトウェアはこれらの制約を追加します。TSP解は距離下限のベンチマークを提供します。