容量制約付き最小全域木

初期解は、Esau-Williams法のランダム化バージョンを使用して見つけられます。ランダム化は、最良の結果から一様ランダムな結合を実行することによって実現されます。${\displaystyle p}$各ステップで最良のものを選ぶのではなく、複数のものを選ぶ。

させて${\displaystyle T}$根を持つ初期解とする${\displaystyle r}$近傍は、単一のノードまたはサブツリー（この記事の序論にあるような一般的なサブツリーではなく）の任意の組み合わせで構成され、別のコンポーネントで 1 つを置き換える${\displaystyle T\setminus r}$変位した構造が次の変位体であり、最後の変位体が最初の変位体を変位させ、元のコンポーネントは1つ以上の変位体を持ち、結果として生じるコンポーネントの容量が超過しない。

改善グラフは、非常に大きな近傍を効率的に探索するためのツールです。改善グラフ内のパスは解の変更に対応し、パスのコストは変更を適用したときの解のコストの変化です。ここで、改善グラフは2つのコピーを使用して構築された有向多重グラフです。${\displaystyle i',i''}$各ノードの${\displaystyle i\in V(T)}$また、任意のノードから別のコンポーネント内の任意のノードへの最大 4 つのエッジがあります。${\displaystyle T\setminus r}$端${\displaystyle i',j''}$ノードの削除による変更に対応します${\displaystyle i}$元のコンポーネントから、根が${\displaystyle j}$ターゲットコンポーネント内。ノードの結合${\displaystyle i'}$およびサブツリー${\displaystyle i''}$これにより、4つの可能なエッジが得られます。対応する変更によって対象コンポーネントの容量が上限を超えない場合、エッジが存在します。エッジのコストは、対象コンポーネントの頂点における最小全域木のコストの、移動前と移動後の差です。したがって、局所探索における近傍は、各コンポーネントから最大1つのノードを含む改善グラフ内のサイクルに対応します。

ローカル探索ステップでは、動的計画法を用いて改善グラフ内の最小コストサイクルを見つけます。改善グラフを通るパスは長さが増加するにつれて生成され、開始パスと終了パス、および関連するコンポーネントが同じ最も好ましいパスのみが格納されます。この目的のために、これら3つのプロパティのタプルをキーとするハッシュテーブルを使用してパスを保持します。各負のサイクルには、そのサイクル内のすべてのパスが負のコストを持つノードが存在するため、負のコストを持つパスのみを考慮すれば十分です。パス間の関連コンポーネントのセットの比較は、アルゴリズムで最も一般的な操作の1つであるため、速度のために整数として格納されたインジケータビット配列の比較として実装されています。ただし、これは明らかに多くのハッシュ衝突に起因しており、ハッシュ関数とテーブル構造の特定の選択、およびスペース制限による高い負荷率の結果である可能性があります（2003年の論文）。

この論文が執筆された当時（2003年）、このアルゴリズムは標準的なオペレーションズリサーチのベンチマークにおいて最先端の性能を誇っていました。実行時間の大部分は、改善グラフの構築（または更新）に費やされました。改善グラフのエッジ数は、入力グラフのサイズに対して経験的に2乗に比例して増加し、これが比較的複雑な最小全域木探索ステップの実行回数を決定するため、最も重要な要素となります。したがって、入力グラフの密度が低いほど改善グラフのエッジ数が減少するため、実行時間が大幅に短縮されると結論づけることができます。