Optimización de rutas de transporte de carga de muchos orígenes a muchos destinos mediante colonias de hormigas

Résumé

El envío de carga de muchos orígenes a muchos destinos es un problema habitual del sector del transporte de paquetería. En estos problemas se intenta consolidar la carga en vehículos para reducir costes, controlando el tiempo de servicio y los retornos en vacío para balancear flujos. La optimización es compleja, pero el análisis del sistema puede descomponerse. (aproximadamente) en el estudio de las relaciones origen-destino. Para cada relación O-D hay varias estrategias para consolidar la carga, pero las más usuales son las paradas múltiples cerca del origen o cerca del destino o la clasificación de cargas en terminales hub que incrementan las expectativas de consolidación. La tesis modeliza el sistema suponiendo un conjunto de terminales hub dadas. Para cada par O-D se minimiza el coste total de transporte cumpliendo un nivel de servicio determinado en plazo de entrega que se expresa como porcentaje mínimo de la carga (o expediciones) que debe servirse en ese plazo. Tras una formulación como programa matemático entero, el problema se resuelve mediante el metaheurístico de las colonias de hormigas. Este bio-heurístico se basa en la elección probabilística de alternativas en función del nivel de feromonas de cada alternativa, rastro éste que depende del número de hormigas que han optado por tal alternativa previamente y que se desvanece al cabo de un tiempo. Se utiliza un parámetro de información heurística para cada uno de los subproblemas de análisis (envíos directos y envíos a través de unos o dos hubs, y paradas múltiples en origen o en destino). El algoritmo implementado se ha contrastado con soluciones exactas en diversos ejemplos de tamaño reducido mostrando una complejidad polinómica de grado bajo con el tamaño del problema. Las aceptables correlaciones obtenidas entre las predicciones del modelo y los datos de base permiten calificar el modelo global de robusto. Cuando se ha aplicado (de