TSP経路最適化

全地点を訪問して出発地に戻る最短経路を探索. ヒューリスティックアルゴリズム（最近傍法、Clarke-Wright節約法）を使用して巡回セールスマン問題を解きます。位置座標を入力して最適化された経路を見つけましょう。

ヒューリスティックアルゴリズム（最近傍法、Clarke-Wright節約法）を使用して巡回セールスマン問題を解きます。位置座標を入力して最適化された経路を見つけましょう。

巡回セールスマン問題（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)。最近傍法: (3,4) d=5.0、次に (2,7) d=3.2、(8,5) d=6.3、(6,1) d=4.5、帰着 d=6.1。合計 = 25.04 (丸めた区間の和は 25.1)。立ち寄り先が 4 か所ならこれが既に最短経路で (24 通りの順序のどれも短くならない)、セービング法も同じ 25.04 を返します。

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

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

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

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

結果の解釈方法

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

よくある質問

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

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

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

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