【要約】巡回セールスマン問題をいろいろな手法で解いてみる①：厳密解法 [Zenn_Python] | Summary by TechDistill
> Source: Zenn_Python
Execute Primary Source
// Problem
TSPはNP困難な組合せ最適化問題であり、都市数が増大するにつれて計算量が爆発的に増加する。実務において、単に全探索を行うことは不可能であり、数学的な定式化によって探索空間を適切に制約し、効率的に最適解を導き出す手法の確立が不可欠である。
// Approach
混合整数計画法に基づき、都市間の移動をバイナリ決定変数として定義。各都市への訪問回数を1回に制限する制約に加え、MTZ制約を導入することで、巡回路が複数の独立したループに分かれる「部分巡回路」の発生を数学的に排除するモデルを構築した。
// Result
都市数30のユークリッド距離に基づく問題に対し、PuLP（CBCソルバー）を用いて厳密解を導出した。目的関数値432.0を得て、NetworkXによる経路の可視化も実施した。本稿は厳密解法の基礎を扱っており、次回のメタヒューリスティクスによる近似解法への布石となっている。
Senior Engineer Insight
> 厳密解法は「最適性」を保証する点で極めて強力だが、実務におけるスケーラビリティには致命的な課題がある。都市数30程度であれば許容できるが、物流最適化のようにノード数が数百を超える現場では、計算時間の指数関数的な増大がシステム全体のレイテンシを破壊する。本稿で採用されているMTZ制約は実装が簡便である反面、大規模問題では緩和が弱く、ソルバーの性能を十分に引き出せない可能性がある。実戦投入においては、問題の規模と要求される精度に基づき、メタヒューリスティクスや、より強力な制約を用いたアプローチを適切に選択する判断力が求められる。