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

• Autores: José de Jesús Cáceres Cruz
• Directores de la Tesis: Ángel Alejandro Juan Pérez (dir. tes.) , Daniel Riera i Terrén (dir. tes.)
• Lectura: En la Universitat Oberta de Catalunya ( España ) en 2013
• Idioma: inglés
• Tribunal Calificador de la Tesis: Djamila Ouelhadj (presid.) , Eva Vallada Regalado (secret.) , Patrick Hirsch (voc.)
• Enlaces
  • Tesis en acceso abierto en: TDX
• Resumen

  • El Problema de Enrutamiento 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 encontradas 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 & paralelas, y programación con restricciones. Los enfoques propuestos han solucionado algunas variantes del VRP: en primer lugar, las familias deterministas: 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 Distancia limitada (DCVRP); en segundo lugar, las familias de naturaleza estocástica: VRP con Demandas estocásticas (VRPSD), y Problemas de Inventario y Enrutamiento de Vehículos con Demandas estocásticas (IRPSD). Una extensa revisión bibliográfica se ha realizado 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 ser aplicados sobre 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 enrutamiento. Los algoritmos heurísticos desarrollados han sido aplicados en varios 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.