El proceso de generar combinaciones de soluciones lineales de soluciones de referencia se puede ver como generar caminos entre soluciones que nos lleven a puntos entre o más alla de las soluciones.
Podemos llevar esto a un concepto un poco más general de creación de combinaciones de soluciones.
Un camino entre soluciones en un espacio vecino va a generar soluciones que compartan una serie de atributos con las soluciones originales. Estos atributos pueden ser ligas, nodos, valores de variables, etc.
La idea de path relinking es buscar soluciones que compartan atributos con antiguas soluciones con la esperanza de obtener mejores soluciones.
Path relinking construye nuevas soluciones explotando las trayectorias que conectan a las soluciones buenas, empezando con alguna de las soluciones, llamada la solución de iniciación (initiating solution), y generando un camino en la vecindad del espacio que lleva a otras soluciones, llamadas las soluciones guías (guiding solutions).
Muchas veces se introducen ideas de búsqueda Tabú para poder realizar estos caminos y no repetir caminos anteriores.
La figura 8.2 muestra un ejemplo de path relinking donde a partir de un camino inicial entre dos soluciones (A y B) en línea continua se construye un nuevo camino para unir estas dos soluciones. La idea es encontrar soluciones difíciles de obtener por búsqueda ``ciega'', al incorporar atributos de soluciones conocidas.
 |
También es posible generar caminos considerando la combinación de atributos de varias soluciones (multiparent path) o hacer ``tunelaje'' (tunneling) al tratar de unir dos soluciones en vecindades diferentes.
Path relinking se ha utilizado para mejorar los procedimientos de re-inicio, como por ejemplo, GRASP.
En GRASP la construcción de una solución es independiente de la construcción de la siguiente solución. No se guarda una historia.
Se han propuesto dos posibles aplicaciones de path relinking en combinación con GRASP:
Las dos estrategias mantienen un conjunto pequeño de soluciones ``elite'' seleccionadas después de cada proceso de búsqueda local.
Aplicar path relinking después de búsqueda local, en
general ha dado mejores resultados. En este caso se toma la
solución 
de búsqueda local y una solución 
seleccionada aleatoriamente de las soluciones ``elite''.
Se obtienen los conjuntos de movimientos que podrian aplicarse para llegar de una solución inicial a la solución guía.
Se toma la mejor solución en esta trayectoria y se considera como candidatra a ingresar a las soluciones ``elite''.
Existe en esta y en muchos otras estrategias para resolver problemas de optimización propuestas para paralilizar estos algoritmos.