4.2.3.2 Búsqueda local guiada en TSP

Para GLS: (i) El costo de la solución es la suma de las distancias de los arcos en el ciclo, (ii) los atributos son todos los posibles arcos, (iii) el costo de cada atributo es su distancia, y (iv) a cada arco se le asocia una penalización (inicialmente = 0).

La nueva función de evaluación es: $D' = D + \lambda P$, donde $D$ es la distancia, $\lambda$ es un parámetro y $P$ es una matríz de penalización.

Lo que quiere decir es que cada vez que hagamos un cambio, usando algún $k-Opt$, tenemos que calcular la distancia total usando $\lambda$ y la penalización asociada a cada arco involucrado en el cambio.

$$util(tour,e_{i,j}) = I_{e_{i,j}}(tour) \cdot \frac{d_{i,j}}{1+p_{i,j}}$$

donde $I_{e_{i,j}}(tour) = 1$ si $e_{i,j} \in tour$ y es 0 si no está.

Lo único que falta definir es el parámetro $\lambda$, que generalmente depende del problema que se quiera resolver.

Se ha encontrado que buenos valores de $\lambda$ son: $\lambda = \alpha \times \frac{g(\mbox{m\'{\i}nimo local})}{\mbox{no.\ atrib. en m\'{\i}n. local})}$.

En ese caso $\alpha$ es más fácil de sintonizar. Para el agente viajero se encontró que un rango de $\frac{1}{8} \leq \alpha \leq \frac{1}{2}$ da buenos resultados.

GLS se puede usar en combinación con otras estrategias.

En particular, la combinación de fast local search con GLS es relativamente directa, solo se tienen que asociar atributos con sub-vecindad.

Por ejemplo, en el TSP se podría tener un bit de activación por ciudad, indicando que ciudades conviene considerar en la vecindad.