セービング法

【せーびんぐほう (saving method)】

運搬経路問題に対する古典的な近似解法であるが, 巡回セールスマン問題に対しても適用できる. 前者の場合, 2点 $i,j\,$ 間の距離を $d_{ij}\,$ , デポ(depot)を点 $0\,$ と記す. 点 $0\,$ 以外の点 のペア 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i,j \,} に対して, セービング値 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle s_{ij} \,} を 構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle s_{ij}=d_{i0}+d_{0j}-d_{ij}\,} と定義する. すべての点を通過する前に閉路ができたり, 点の次数が $2\,$ を超えないように, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle s_{ij} \,} の大きい順に枝 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (i,j) \,} を加えていくことによって運搬経路を構築する.