セービング法

出典: ORWiki

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

運搬経路問題に対する古典的な近似解法. 2点 $i,j \,$ 間の距離を $d_{ij} \,$ , デポ(depot)を点 $0 \,$ と記す. 点 $0 \,$ 以外の点のペア $i,j \,$ に対して, セービング値 $s_{ij} \,$ を $s_{ij} = d_{i0}+d_{0j}-d_{ij} \,$ と定義する. すべての点を通過する前に閉路ができたり, 点の次数が $2 \,$ を超えないように, $s_{ij} \,$ の大きい順に枝 $(i,j) \,$ を加えていくことによって運搬経路を構築する.巡回セールスマン問題に対しても適用できる