Caminos nodo-disjuntos, acotados y de menor costo entre dos nodos

Abstract

Este trabajo presenta una heurística capaz de resolver el problema de hallar k caminos nodo-disjuntos entre dos nodos de un grafo de aristas de costos reales no negativos, con la restricción de que todos los caminos deben tener a lo sumo d aristas, minimizando el costo total de la solución. La motivación del diseño de una heurística reside en el hecho de que el problema que se intenta resolver no tiene una solución polinomial conocida. Existen diversos artículos que estudian problemas relacionados con este trabajo. En particular, la variante en donde no se restringen los largos de los caminos puede ser resuelta por algoritmos exactos y polinomiales, como son los de Suurballe y Bhandari. Algunos artículos tratan problemas similares, pero con hipótesis adicionales, como la de requerir ue el grafo sea dirigido y acíclico, o que el grafo sea plano, o el caso donde la cantidad de caminos a hallar es solamente 2. De estos trabajos se extraen ideas que se aplican al nuestro; en particular del algoritmo de Bhandari y del algoritmo DIMCRA, donde este último estudia el problema de hallar 2 caminos arista-disjuntos en un grafo donde los costos de las aristas son multidimensionales y existe un vector de restricciones que ambos caminos deben cumplir. El diseño de la heurística se basa la metaheurística GRASP (Greedy Randomized Adaptive Search Procedure), centrándose en la definición de los algoritmos necesarios para su implementación: la fase de construcción de soluciones factibles y la fase de búsqueda local. La fase de construcción se inspira en el algoritmo de Bhandari, con la diferencia de que el proceso de generación de caminos es aleatorio y también incluye elementos del algoritmo DIMCRA. El algoritmo de búsqueda local utiliza una estrategia de sustitución de subcaminos para explorar el espacio de búsqueda. Al algoritmo resultante lo denominamos CADILAC. También se desarrolla una heurística simple, denominada Greedy, para compararla con el algoritmo propuesto durante el análisis de resultados. La implementación de ambos algoritmos fue realizada en C++, utilizando la biblioteca LEMON para la manipulación de grafos. El trabajo concluye con la presentación de las pruebas realizadas que comparan a los algoritmos CADILAC y Greedy. Mostramos cómo el algoritmo que proponemos no es comparable con los tiempos de ejecución de la heurística Greedy, sin embargo, logra obtener mejores costos en la mayoría de los casos.