クラーク・ライト法

提供: ORWiki
2008年11月8日 (土) 19:35時点におけるAlbeit-Kun (トーク | 投稿記録)による版
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
ナビゲーションに移動 検索に移動

【くらーくらいとほう (Clarke-Wright method)】

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