【要約】巡回セールスマン問題をいろいろな手法で解いてみる②：山登り法 [Zenn_Python] | Summary by TechDistill
> Source: Zenn_Python
Execute Primary Source
// Problem
TSPは都市数が増大するにつれ計算量が爆発的に増加するNP困難な問題である。実用的な時間内で解を得るには近似解法が不可欠だが、単純な局所探索では局所最適解に陥りやすく、また近傍操作の選択次第で解の精度が著しく低下するという課題がある。
// Approach
局所探索法の一種である山登り法をPythonで実装。解の表現には順列表現を採用し、現在の解からランダムに近傍解をサンプリングして評価する。近傍操作として、2要素を交換する手法と、2-optアルゴリズムに基づく区間反転手法の2パターンを実装し、それぞれの性能を比較した。
// Result
交換近傍による近似解（526）に対し、2-opt近傍による近似解（450）は厳密解（432）に近い良好な結果を得た。これにより、近傍操作の定義が近似解の精度を決定付ける重要な要素であることが実証された。今後はタブーサーチによる探索範囲の拡張が課題となる。
Senior Engineer Insight
> 本記事の実装は、アルゴリズムの基礎的な理解と近傍設計の重要性を端的に示している。しかし、実戦のプロダクション環境、特に大規模な配送最適化やスケジューリングに投入する場合、単純な山登り法では局所最適解へのトラップを回避できず、解の品質が不安定になるリスクが高い。2-optの導入で精度が向上した点は評価できるが、スケーラビリティと精度の両立には、タブーサーチや焼きなまし法（SA）のような、探索の多様性を確保するメタヒューリスティクスの実装が必須である。また、計算コストを抑えつつ精度を上げるための近傍サンプリング戦略の最適化も、低レイテンシが求められる現場では重要な検討事項となる。