「クラーク・ライト法」の版間の差分
ナビゲーションに移動
検索に移動
Sakasegawa (トーク | 投稿記録) |
Albeit-Kun (トーク | 投稿記録) |
||
| 2行目: | 2行目: | ||
運搬経路問題に対する古典的な近似解法で,セービング法ともいう. 2点 <math>i,j \,</math> 間の距離を <math>d_{ij} \,</math> , デポ(depot)を点 <math>0 \,</math> と記す. 点 <math>0 \,</math> 以外の点 のペア <math>i,j \,</math> に対して, セービング値 <math>s_{ij} \,</math> を <math>s_{ij} = d_{i0}+d_{0j}-d_{ij} \,</math> と定義する. すべての点を通過する前に閉路ができたり, 点の次数が <math>2 \,</math> を超えないように, <math>s_{ij} \,</math> の大きい順に枝 <math>(i,j) \,</math> を加えていくことによって運搬経路を構築する.巡回セールスマン問題に対しても適用できる | 運搬経路問題に対する古典的な近似解法で,セービング法ともいう. 2点 <math>i,j \,</math> 間の距離を <math>d_{ij} \,</math> , デポ(depot)を点 <math>0 \,</math> と記す. 点 <math>0 \,</math> 以外の点 のペア <math>i,j \,</math> に対して, セービング値 <math>s_{ij} \,</math> を <math>s_{ij} = d_{i0}+d_{0j}-d_{ij} \,</math> と定義する. すべての点を通過する前に閉路ができたり, 点の次数が <math>2 \,</math> を超えないように, <math>s_{ij} \,</math> の大きい順に枝 <math>(i,j) \,</math> を加えていくことによって運搬経路を構築する.巡回セールスマン問題に対しても適用できる | ||
| + | |||
| + | [[category:生産・在庫・ロジスティクス|くらーくらいとほう]] | ||
2008年11月8日 (土) 19:35時点における最新版
【くらーくらいとほう (Clarke-Wright method)】
運搬経路問題に対する古典的な近似解法で,セービング法ともいう. 2点 間の距離を , デポ(depot)を点 と記す. 点 以外の点 のペア に対して, セービング値 を と定義する. すべての点を通過する前に閉路ができたり, 点の次数が を超えないように, の大きい順に枝 を加えていくことによって運搬経路を構築する.巡回セールスマン問題に対しても適用できる
