Metaheurística aplicada a un problema de packing con ruteo.

Abstract

En el presente trabajo se estudio un problema de ruteo de vehículos con packing de tres dimensiones, con cajas no homogéneas, en un solo vehículo de carga, haciendo que los productos sean ordenados en relación al orden de visita a los clientes a los cuales pertenecen dichos productos, que en general, tienen dimensiones diferentes. Se considera un orden de entrega de arriba hacia abajo, de derecha a izquierda y de adelante hacia atrás, respecto a la puerta del contenedor. El objetivo de este estudio es cumplir la ruta optima, entregando todos los productos a los clientes de dicha ruta, con un layout de carga que permita ordenar, de manera optima, las cajas en el camión de carga según el orden de entrega mencionado anteriormente, utilizando una función objetivo, ´ de tal forma, que da una mayor puntuación a los objetos que deben ser entregados últimos y que minimice la distancia entre la posición del objeto y el punto 0,0,0 del contenedor, considerando el factor de entrega. Se propone utilizar la metaheurística Harmony search, para ordenar las cajas según el orden de visita de los clientes (problema de packing). Por otra parte se propone realizar un modelo matemático, para obtener la ruta ´ optima de ´ entrega, la cual sirve como input de la metaheurística planteada para el problema de packing. Se realizaron 20 pruebas realistas (las cuales son con datos proporcionados por empresas locales de distribución de productos), para la calibración de los parámetros, con valores para los parámetros recomendados en la literatura y la comparación con estudios realizados anteriormente. También se consideraron las restricciones naturales del problema para el layout de las cajas. Para programar la metaheurística mencionada, se utilizo el lenguaje 2 de programacion Python 3.7 en el IDE Spider y el solver comercial CPLEX 12.7.1 para calcular la ruta utilizada. Finalmente, se representa el layout de la posición de las cajas según su orden de entrega y las soluciones entregadas por la metaheurística, resaltando las mejores soluciones encontradas. Se comparan los resultados obtenidos por la mejor solución de la metaheurística, con un estudio realizado anteriormente, que analiza un problema similar, pero solucionandolo mediante un modelo matemático. En términos de programación, se lograron buenos resultados con la metaheurística trabajada, considerando la complejidad del problema. Se puede ver, un aproximado de la posición que deberían tener las cajas en cada iteracion, además de conseguir un buen tiempo de ejecución para cada instancia. En este estudio no se consideraron factores como el peso de las cajas, perecibilidad, rotación, centro de gravedad, entre otros, por lo que si agregamos ´ estos factores se podrían obtener soluciones mas reales, aunque posiblemente en peores tiempos de ejecución.