Models and algorithms for solving packing problems in logistics

Zusammenfassung

El propósito de la tesis es contribuir a una solución eficiente a varios problemas de empaquetado que tienen las empresas de logística, en el proceso de enviar productos desde los centros de distribución hasta el cliente final. Las soluciones a estos problemas se alcanzan mediante modelos y algoritmos exactos cuando es posible o mediante metaheuristicos, los cuales no garantizan la optimalidad pero producen soluciones de calidad en un breve periodo de tiempo. Para ser más precisos los problemas que trata esta tesis son como determinar el tamaño de las cajas utilizadas para empaquetar los productos a enviar, cómo cargar las cajas en contenedores maximizando su carga y cómo cargar pallets en camiones. En todos los problemas que se trata en la tesis se incluye restricciones reales. El campo de la tesis es la investigación operativa, una disciplina que trata de aplicar métodos analíticos avanzados para ayudar a tomar decisiones [1]. El propósito de la tesis es la contribuir a la investigación en los problemas de empaquetado a través de un análisis de los problemas reales en el campo de la logística, encontrando soluciones que se puedan aplicar en la industria. Contenido de la investigación En el capítulo 2 de la tesis se trata un problema real de los centros de distribución. Cada semana los clientes (tiendas) le envían al centro de distribución una serie de pedidos consistente en una lista de productos que el centro de distribución debe servirles. EL centro de distribución debe empaquetar los productos usando un embalaje apropiado. La elección del embalaje es importante porque protege el contenido de ser dañado y tiene una influencia en el coste del trasporte. Los centros de distribución se enfrentan a dos problemas, cuantos tipos de cajas para embalar deben de tener y de qué dimensiones cada una, para minimizar el coste del trasporte de los productos hasta la tienda. Las cajas se han diseñado usando una formulación lineal entera basada en un modelo de patrones de corte adaptados a la demanda. La demanda no es conocida a priori y por tanto se modela usando una distribución de probabilidades. Se toma una muestra de la distribución de probabilidad, el problema se resuelve con esa muestra y la solución se aplica a una muestra mayor, la cual representa a los pedidos futuros permitiéndonos evaluar el rendimiento de las soluciones obtenidas. Se ha desarrollado una nueva formulación basada en el modelo de patrones de corte de Beasley [2]. Este modelo se ha utilizado para obtener buenas soluciones en proceso de tres pasos. Primero se aplica un método de reducción para elegir un subconjunto de tamaños de cajas prometedoras y se utilizan algunos heurísticos para obtener un conjunto de patrones de empaquetamiento para los diferentes tamaños de cajas. En el segundo paso, el modelo entero se resuelve utilizando solo los patrones obtenidos en la primera fase. Finalmente las soluciones obtenidas por el modelo se mejoran usando algunos movimientos que buscan mejores tamaños y patrones de empaquetamiento. En el capítulo 3 hemos estudiado el problema del contenedor, donde un conjunto de cajas tiene que enviarse en un contenedor de dimensiones fijas. El problema incluye alguna restricción como la carga que puede soportar cada caja encima de ella. Para resolver el problema hemos desarrollado un Greedy randomized adaptative search procedure (GRASP) con un proceso constructivo y algunos movimientos para mejorar las soluciones. La principal contribución es el uso simultáneo de diferentes criterios para la elección del bloque y para el rellenado del contenedor. Cada estrategia se elige al azar en cada iteración del algoritmo, proporcionando una nueva solución. A cada solución se le aplica una serie de movimientos como eliminar pilas, rellenar la parte superior de una solución parcial, intercambiar bloques o rellenar una solución parcial. El algoritmo consigue mejores resultados que otros algoritmos existentes para todas las clases de los problemas test. En el capítulo 4, tratamos el problema de una empresa de distribución que tiene que decidir cómo poner los productos en pallets de acuerdo a la demanda de sus clientes y como distribuir eficientemente los pallets en camiones para minimizar el número de camones que se le debe enviar a cada cliente. Para resolverlo se han introducido dos enfoques un heurístico y un modelo matemático. En el enfoque heurístico, se ha desarrollado un algoritmo multi-arranque con una fase constructiva en la cual las soluciones se construyen añadiendo un pallet cada paso en función de la información recolectada, manteniendo el flujo de información entre la fase de construcción del pallet y la de la carga del camión. En el modelo matemático se estudia el problema modelizando las diferentes características y evaluando sus efectos en las soluciones. Primero se ha modelizado las características básicas del problema, como excederse ene le peso máximo del camión ni en la altura máxima. Luego, se ha estudiado la formación de pallets, añadiendo uno y dos pallets en cada posición. Por razones de seguridad el centro de gravedad de la carga tiene que estar en la posición central del camión. Se ha añadido esta restricción en el modelo. Por último hemos intentado reducir el número de pallets requeridos, mediante un nuevo modelo que toma los camiones que da como solución el modelo previo y minimizamos el número de pallets. Conclusiones Las principales contribuciones de la tesis son: Tratamos problemas reales en el campo de la logística. Todos los problemas tratados son problemas reales en centros de distribución. En el capítulo 2 tratamos el problema de determinar el tamaño de las cajas de embalaje, en el capítulo 3 el problema de empaquetar cajas en contenedores, en el capítulo 4 tratamos el problema de servir productos a clientes mediante pallets en camiones. Todos ellos son problemas en el campo de la logística. Hemos estudiado y analizado los datos, el contexto y las restricciones. En cada problema se ha analizado su contexto y los datos relevantes, restricciones y objetivos para obtener información para el desarrollo de los algoritmos y modelos. Hemos aplicado diferentes técnicas de resolución de problemas, modelos y metaheuristicos. o Se ha desarrollado una nueva formulación para resolver el problema de los tamaños de las cajas, aplicando heurísticos para obtener el conjunto de patrones para cada tamaño. La estrategia de solución combina modelos y heurísticos para obtener soluciones de calidad. o Un algoritmo GRASP para resolver el problema del contenedor con restricción de soporte de carga en cada caja. El constructivo utiliza diferentes criterios para la elección del bloque y diferentes estrategias para rellenar el contenedor. o Un constructivo aleatorizado para resolver el problema de cargar productos en pallets y pallets en camiones. Luego se ha estudiado el problema mediante modelos lineales enteros que progresivamente van introduciendo las restricciones.