Diseño e implementación de una meta-heurística multi-poblacional de optimización combinatoria enfocada a la resolución de problemas de asignación de rutas a vehículos

• Autores: Eneko Osaba
• Directores de la Tesis: José Fernando Díaz Martín (dir. tes.)
• Lectura: En la Universidad de Deusto ( España ) en 2015
• Idioma: español
• Tribunal Calificador de la Tesis: Mario G. Piattini Velthuis (presid.) , Esther Álvarez de los Mozos (secret.) , Xin-She Yang (voc.)
• Enlaces
  • Tesis en acceso abierto en: TESEO
• Resumen

  • El transporte es un factor crucial para la sociedad actual, tanto para la ciudadanía como para el sector empresarial. Existe una gran variedad de sistemas de transporte, cada uno con sus ventajas e inconvenientes. Del mismo modo, diversas áreas de conocimiento están capacitadas para hacer frente a la planificación eficiente del transporte, ya sea de carácter empresarial, o urbano. En este trabajo se centrará la atención en una de esas áreas: la inteligencia artificial y los problemas de optimización.

    La gran mayoría de los problemas surgidos en el área del transporte y la logística tienen características comunes, lo que hace que puedan modelizarse como problemas de optimización y que puedan ser vistos como casos particulares de otros problemas genéricos. Estos problemas se encuadran en el ámbito de la optimización combinatoria. Gran parte de los problemas de este tipo cuentan con una complejidad excepcional, haciendo necesaria la utilización de técnicas para su tratamiento. Existen diferentes métodos de esta índole, aunque este trabajo se centrará en las meta-heurísticas.

    Puede encontrarse un vasto número de meta-heurísticas en la literatura actual, cada una con sus propias características. Debido a la alta complejidad de los problemas a tratar, no hay una técnica definitiva que consiga resolver de forma óptima todos los problemas de optimización. Este hecho hace que el campo tanto de la optimización combinatoria, como el de los problemas de asignación de rutas de transporte, sea un tema de investigación candente.

    Con todo esto, el presente trabajo de tesis doctoral centrará su esfuerzo en la creación de una nueva meta-heurística que ayude a la resolución de problemas de asignación de rutas a vehículos. La técnica presentada ofrece un valor añadido frente a los métodos existentes, ya sea en relación al rendimiento, o a la aportación de originalidades conceptuales.

    Con la intención de validar el modelo, se han comparado los resultados de la meta-heurística propuesta con los obtenidos por otros cuatro algoritmos de filosofía similar. Para esta experimentación se han utilizado cuatro famosos problemas de asignación de rutas a vehículos, y dos problemas clásicos de la optimización combinatoria. En la comparativa se ha realizado un completo análisis estadístico sobre la calidad de las soluciones obtenidas y la convergencia temporal de cada técnica, utilizando para ello pruebas estadísticas parámetricas, como el test normal z, y pruebas no paramétricas, como el test de Friedman. Gracias a estos tests se ha podido afirmar de forma rigurosa que la técnica propuesta es competitiva en cuanto a rendimiento se refiere, y original conceptualmente hablando.