Sociedad de la Información y el Conocimiento

Randomized Algorithms for Rich Vehicle Routing Problems: From a Specialized Approach to a Generic Methodology

Doctorado de Sociedad de la Información y el Conocimiento
22/11/2013

Autor: José de Jesús Cáceres Cruz
Programa: Doctorado de Sociedad de la Información y el Conocimiento
Idioma: inglés
Director: Dr. Ángel Alejandro Juan Pérez
Departamento / Instituto: Internet Interdisciplinary Institute (IN3), Departamento de Informática, Multimedia y Telecomunicación
Materias: Informática, Análisis, Teoría general del análisis combinatorio, Teoría de grafos, Ingeniería, Tecnología, Ingeniería del transporte terrestre, Ingeniería de los vehículos de transporte
Palabras clave: Problemas enriquecidos de rutas de vehículos, Heurísticas aleatorias y sesgadas, Metaheurísticas, Aplicaciones reales, Optimización, Logística
Área de conocimiento: Ciencia de la Computación e Inteligencia Artificial

+ Enlace al proyecto

Resumen

El problema de rutas de vehículos (VRP) y sus diferentes variantes básicas son un dominio ampliamente estudiado en la comunidad científica de optimización. Algunos estudios han utilizado combinaciones específicas de restricciones halladas en la vida real para definir los emergentes VRP enriquecidos. Este trabajo aborda la integración de heurísticas, probabilidad sesgada, simulación, técnicas de computación distribuida y paralela, y programación con restricciones. Los enfoques propuestos han solucionado algunas variantes del VRP: en primer lugar, las familias deterministas, como VRP con flotas heterogéneas (HVRP), VRP con flotas heterogéneas y costo variable (HVRP-V), VRP con flota heterogénea y múltiples viajes (HVRPM), VRP con matriz de costo asimétrica (AVRP), VRP con flota heterogénea y matriz de costo asimétrica (HAVRP), VRP con ventanas de tiempo (VRPTW) y VRP con distancia limitada (DCVRP); en segundo lugar, las familias de naturaleza estocástica, como VRP con demandas estocásticas (VRPSD), y problemas de inventario y rutas de vehículos con demandas estocásticas (IRPSD). Por otro lado, se ha llevado a cabo una extensa revisión bibliográfica para cada una de estas variantes. Un primer enfoque propone la combinación de una aleatorización sesgada con heurísticas clásicas para la solución de problemas deterministas. Un segundo enfoque se centra en la combinación de heurísticas aleatorias con simulación (simheuristics) para su aplicación en los problemas estocásticos comentados. Por último, se propone un tercer enfoque basado en el trabajo conjunto de heurísticas aleatorias con programación de restricciones para resolver varios tipos de problemas de rutas. Los algoritmos heurísticos desarrollados se han aplicado en diversos casos de referencia --entre ellos, dos estudios de casos reales de distribución en España-- y los resultados obtenidos son, en general, prometedores y útiles para los decisores.