Métodos y algoritmos para resolver problemas de transporte con múltiples usos de vehículos

Abstract

El objetivo de la tesis doctoral “MÉTODOS Y ALGORÍTMOS PARA RESOLVER PROBLEMAS DE TRANSPORTE CON MÚLTIPLES USOS DE VEHÍCULOS”, realizada por D. José López Fresno y dirigida por el Dr. D. Alberto Gómez Gómez, es el análisis, la investigación de las técnicas disponibles, y la propuesta de nuevos métodos de resolución para el tratamiento de una variante del Problema de Enrutamiento de Vehículos, el problema de Enrutamiento de Vehículos con Múltiples Viajes o Vehicle Routing Problem With Multiple Trips (VRPMT). En este caso, se dispone de una flota de vehículos limitada, y cada vehículo puede realizar más de una ruta en el mismo período de planificación, siempre que no exceda de su tiempo máximo de conducción. La inclusión de esta característica confiere a este problema relevancia práctica. Se busca obtener el conjunto de rutas de coste mínimo que visiten a todos los clientes solo una vez. La resolución de este tipo de problemas reviste un alto grado de complejidad, pues encontrar una solución factible es un problema NP-Hard. En esta tesis se describe y analiza el problema y se propone un algoritmo de resolución basado en metaheurísticas ILS (Iterated Local Search), utilizando una metaheurística VNS (Variable Neighborhood Search) embebida. El método propuesto tiene características diferenciales respecto a otros métodos propuestos anteriormente en la literatura. Se propone una arquitectura diferenciada para la configuración y comportamiento de los parámetros del algoritmo, con la idea fundamental de desarrollar una metodología que permita al algoritmo metaheurístico obtener el máximo desempeño en su función, tratando a su vez de disminuir el proceso de adaptación a cada tipo de problemas de tal forma que el algoritmo sea capaz de adaptarse a determinadas características del problema concreto a resolver en cada momento. El algoritmo propuesto fue evaluado y contrastado con los mejores algoritmos encontrados en la literatura, utilizando para ello un conjunto de instancias de prueba. La calidad de las soluciones encontradas, y el esfuerzo computacional empleado, hacen que el desempeño del algoritmo propuesto pueda considerarse como de buena calidad respecto al resto de los algoritmos contra los que ha sido contrastado. El algoritmo propuesto ha sido capaz de encontrar soluciones factibles para una instancia de prueba para la que los trabajos anteriores únicamente encontraban soluciones no factibles. Asimismo ha encontrado varias mejores soluciones para algunas de las instancias de prueba utilizadas para evaluar su comportamiento.