Una metaheurística para el problema de planificación de ruta más corta multipunto.

Abstract

La presente memoria de título tiene como objetivo presentar el problema de la ruta más corta múltiple con restricción de capacidades compartidas (SRMSPP), y usar una metaheurística para resolver dicho problema. Este problema fue recientemente publicado como una extensión del problema de ruta más corta con restricción de recursos (RCSPP). Esta variante presenta restricciones de consumo de recursos que son compartidos por arcos de una colección de grafos. Para resolver el SRMSPP se plantea un algoritmo de dos fases, la primera genera una solución inicial y la segunda busca mejorar la solución mediante una destrucción y reconstrucción de los grafos. Los resultados muestran la obtención de soluciones factibles en la gran mayoría de casos con tiempos elevados debido al tamaño y dificultad del problema.