Optimización computacional en problemas de bin-packing y su aplicación a redes de transporte y logística

Resumen

Existen numerosos ámbitos en los que resulta necesario resolver problemas de optimización complejos. Entre dichos ámbitos, la logística y el transporte constituyen dos ámbitos interrelacionados entre sí que ejercen una gran influencia económica y operativa en la mayoría de organizaciones, ya que la correcta planificación y coordinación de los procesos que en ellos se producen permiten, no sólo reducir costes, sino también aumentar la eficiencia de los recursos disponibles, incluyendo la mejora de las condiciones laborales de los empleados. Los procesos asociados a los ámbitos de la logística y transporte requieren habitualmente resolver problemas relacionados con la asignación de recursos, como pueden ser, por ejemplo, la selección de alternativas en proyectos y procedimientos, la planificación de la producción, almacenamiento eficiente de objetos en contenedores, gestión del agrupamiento de contenedores en barcos mercantes o trenes de mercancías, planificación y gestión eficiente de pedidos de clientes, asignación de rutas de reparto de mercancías, etc. Los problemas relacionados con dichas disciplinas, suelen clasificarse en tres grupos: problemas de planificación estratégica o a largo plazo, como, por ejemplo, diseñar la localización y estructura física de un almacén logístico; problemas de planificación táctica o a medio plazo, como, por ejemplo, planificar las rutas que han de seguir los vehículos para realizar un reparto en días posteriores; y problemas de planificación operativa o a corto plazo, como, por ejemplo, qué tareas particulares se asignan a los trabajadores en el centro logístico en caso de tener un pedido urgente u otra incidencia especial. De entre el amplio número de grupos de problemas de optimización existentes en dichos ámbitos, la familia de problemas de empaquetamiento en contenedores, conocido como Bin-Packing Problem (BPP), es una de las que mayor número de aplicaciones prácticas tiene. Así, y centrándonos en el caso particular de empresas y organizaciones productoras y distribuidoras, dicho problema se puede presentar en diferentes escalas físicas, como puede ser desde almacenar piezas de pequeño tamaño en cajas, almacenar cajas de frutas y hortalizas en palets, almacenar palets de frutas en camiones frigoríficos, o almacenar contenedores en barcos. Obviamente, el almacenamiento óptimo de este tipo de objetos o piezas en los contenedores puede suponer un ahorro importante, principalmente en lo referente al número de contenedores utilizados, aunque también en cuanto al tiempo requerido para su almacenamiento, costes indirectos, etc. El estudio de las diferentes variantes multi-dimensionales de los problemas agrupados bajo el acrónimo de BPP resulta interesante, no sólo desde el punto de vista de su influencia tangible en los resultados de empresas, sino también por el hecho de que se incluye dentro de la categoría de problemas NP-duros, lo que a efectos prácticos implica que no existe procedimiento conocido que permita obtener la solución óptima al problema en cuestión en un tiempo acotado. Dado que este problema, y sus múltiples variantes, es difícil de resolver, y dado que su complejidad crece exponencialmente con el número de objetos a almacenar, resulta necesario aplicar técnicas de optimización que permitan la organización de dichos elementos de forma automática. Gracias al avance de la computación, y a la disponibilidad de computadores de altas prestaciones, cada vez a más bajo coste, hoy día es posible tratar este tipo de problemas haciendo uso de técnicas de optimización computacional de forma efectiva. En concreto, el uso de meta-heurísticas permite obtener soluciones de calidad aceptable en tiempos de ejecución acotados, lo cual es particularmente interesante en este tipo de problemas que se encuentran a medio camino entre la planificación táctica y la planificación operativa, y por tanto, no pueden ser planificados de forma eficiente en tan corto plazo por un decisor humano. En esta tesis doctoral se han propuesto y analizado diferentes técnicas y estrategias de implementación de métodos de optimización computacional basados en heurísticas y meta-heurísticas para resolver problemas relacionados con la logística y el transporte. Como punto central se aborda el problema de Bin-Packing en una y dos dimensiones, tanto desde el punto de vista de formulaciones mono-objetivo como multi-objetivo con restricciones. Para su resolución se proponen estrategias basadas en algoritmos meméticos, y también estrategias de procesamiento paralelo que aprovechen las ventajas derivadas de los modernos procesadores multi-núcleo de bajo coste. Los métodos aquí presentados son evaluados en comparación con otras técnicas existentes en la literatura a la hora de resolver una gran variedad de problemas de test (benchmarks). Por otro lado, se trata una aplicación real consistente en el empaquetamiento de palets en camiones utilizando dimensiones y medidas estándar internacionales. Finalmente, se analiza la sinergia entre el BPP con otros problemas relacionados con la logística y transporte, en especial la relación existente entre el BPP y el problema de enrutado de vehículos (Vehicle Routing Problem, VRP), tratamiento combinado que abre una línea de investigación con muchas posibilidades de exploración futura.