Desarrollo de un algoritmo basado en técnicas heurísticas de cálculo para la resolución de problemas de gestión de transporte de mercancías en tiempo real

• Autores: David Escuín Finol
• Directores de la Tesis: Carlos Millán (dir. tes.) , Emilio Larrodé Pellicer (dir. tes.)
• Lectura: En la Universidad de Zaragoza ( España ) en 2010
• Idioma: español
• Tribunal Calificador de la Tesis: Francesc Robusté Antón (presid.) , José María Moreno Jiménez (secret.) , Ángel Ibeas Portilla (voc.) , Francisco de Asis García Benitez (voc.) , Víctor Yepes Piqueras (voc.)
• Texto completo no disponible (Saber más ...)
• Resumen

  • Esta tesis presenta un nuevo algoritmo para la resolución de los problemas de cálculo de rutas en tiempo real y con ventanas temporales. El modelo resuelto corresponde al caso de recogidas y entregas, más conocido por sus siglas DPDVRPTW (Dynamic Pickup and Delivery Vehicle Routing Problem with Time Windows). El objetivo es el empleo del menor número posible de vehículos y la reducción de la distancia, siempre cumpliendo con las restricciones de las ventanas temporales y la no denegación del servicio. El modelo es resuelto en dos etapas: el cálculo de rutas (routing) y la planificación de tiempos (scheduling).

    La primera de las etapas tiene como objetivo la inserción de nuevas órdenes en la actual configuración de rutas en función de una determinada función de coste. Esta función de coste ha sido parametrizada para analizar la sensibilidad de sus parámetros ante diferentes situaciones dinámicas y contempla la optimización del problema a corto plazo, a medio plazo y penaliza el uso de vehículos. Además, se ha implementado una estrategia de buffering que almacena aquellas órdenes no urgentes y que son insertadas en las rutas más adelante. Por otra parte, se ha generalizado la técnica de desvío de vehículos para permitir múltiples desvíos en cascada antes situaciones altamente dinámicas. La optimización de la distancia es un proceso posterior aplicándose una búsqueda en entorno variable descendente y una búsqueda tabú basada en atributo con memoria adaptativa.

    Se han implementado tres nuevas estrategias de scheduling. La primera de ellas, wait-first (WF), obliga la espera de un vehículo en un determinado nodo de tal forma que la llegada al siguiente nodo se produzca justo a la apertura de su ventana. La segunda, denominada salida ponderada (SP), regula la salida de un vehículo en virtud de su primer y último momento de salida. Finalmente, se ha diseñado un scheduling global que, a diferencia de las técnicas habituales de scheduling ruta a ruta, calcula una asignación de tiempos en el conjunto de todas las rutas. El objetivo es el de maximizar el área elíptica abarcada por los tiempos de espera de los vehículos. El problema ha sido resuelto mediante un algoritmo genético.

    La ejecución del algoritmo se ha realizado sobre el soporte de un simulador diseñado para dar cabida a todo el tiempo real disponible y realizar los análisis de sensibilidad de las variables principales. El algoritmo ha sido testeado sobre el conjunto de los 30 problemas reales de 100 órdenes de Mitrovic-Minic et al. (2004). Se consiguen reducciones de hasta un 25% en el número de vehículos. Además del grado de dinamismo, se ha definido el concepto IEM, índice espera media, como medida de la separación de las ventanas entre la recogida y entrega de una orden y se han generado nuevos problemas para la evaluación de las técnicas de scheduling. Los resultados revelan que el empleo estrategias a corto plazo son más positivas que a largo y se muestran los beneficios conseguidos con el scheduling global frente al resto de estrategias especialmente para valores de IEM superiores al 50%.

    Los problemas en tiempo real han sido resueltos también con sus correspondientes versiones estáticas para analizar el valor de la información. Además de la simulación estática clásica, se ha implementado una técnica híbrida de simulación estática en dinámico con obtención de mejores resultados. El procedimiento consiste en lanzar el algoritmo dinámicamente con todas las órdenes conocidas por adelantado.