Árbol de expansión mínima con capacidad

La solución inicial se encuentra utilizando una versión aleatoria de Esau-Williams. La aleatorización se logra ejecutando una unión aleatoria uniforme de los mejores${\displaystyle p}$en lugar de la mejor en cada paso.

Dejar${\displaystyle T}$ser la solución inicial con raíz${\displaystyle r}$. El vecindario consiste en cualquier combinación de un solo nodo o subárbol (subárboles generales, no como en la introducción de este artículo) que desplaza a uno en un componente diferente de${\displaystyle T\setminus r}$de tal manera que la estructura desplazada sea el siguiente desplazador, el último desplazador desplace al primer desplazador, ningún componente original tenga más de un desplazador y la capacidad no se exceda en ningún componente resultante.

Un grafo de mejora es una herramienta para explorar un vecindario muy grande de manera eficiente. Los caminos a través de un grafo de mejora corresponden a cambios en una solución y el costo del camino es el cambio en el costo de la solución al aplicar el cambio. Aquí, el grafo de mejora es un multigrafo dirigido construido usando 2 copias${\displaystyle i',i''}$de cada nodo${\displaystyle i\in V(T)}$y hasta 4 aristas desde cualquier nodo a cualquier nodo en un componente diferente de${\displaystyle T\setminus r}$El borde${\displaystyle i',j''}$corresponde al cambio de eliminar el nodo${\displaystyle i}$de su componente original y reemplazando el subárbol enraizado en${\displaystyle j}$en el componente de destino. Combinando nodos${\displaystyle i'}$y subárboles${\displaystyle i''}$Esto genera las 4 posibles aristas. Una arista existe si el cambio correspondiente no provoca que el componente objetivo supere la capacidad. El costo de una arista es la diferencia en el costo de los árboles de expansión mínima en los vértices del componente objetivo antes y después del desplazamiento. Por lo tanto, los vecinos en la búsqueda local corresponden a ciclos en el grafo de mejora que contienen como máximo un nodo de cada componente.

El paso de búsqueda local utiliza un enfoque de programación dinámica para encontrar un ciclo de costo mínimo en el grafo de mejora. Se generan rutas a través del grafo de mejora con longitud creciente y solo se almacena la más favorable con el mismo inicio y fin, así como los mismos componentes involucrados. Para ello, se utiliza una tabla hash con la tupla de esas tres propiedades como clave para almacenar las rutas. Dado que en cada ciclo negativo existe un nodo tal que todas las rutas dentro de ese ciclo que contienen este nodo tienen costo negativo, solo es necesario considerar las rutas con costo negativo. Como la comparación de conjuntos de componentes involucrados entre rutas es una de las operaciones más comunes en el algoritmo, se implementa como una comparación de matrices de bits indicadores almacenadas como enteros para mayor velocidad. Sin embargo, esto claramente se debe a una gran cantidad de colisiones de hash, que podrían ser consecuencia de la elección particular de la función hash y la estructura de la tabla, así como del alto factor de carga debido a las restricciones de espacio (artículo de 2003).

En el momento de redactar este artículo (2003), este algoritmo representaba la vanguardia en un conjunto de datos de referencia estándar para la investigación operativa. La ejecución dependía principalmente de la construcción (o actualización) del grafo de mejora. El número de aristas en el grafo de mejora aumentaba empíricamente de forma cuadrática con el tamaño del grafo de entrada, y dado que esto determina la cantidad de veces que debe ejecutarse el paso, relativamente complejo, de encontrar un árbol de expansión mínima, este es el factor más crítico. Por lo tanto, se puede concluir que los grafos de entrada menos densos mejoran considerablemente el tiempo de ejecución, ya que esto reduce el número de aristas en el grafo de mejora.