Source: https://scielo.conicyt.cl/scielo.php?script=sci_arttext&pid=S0718-07642004000400010&lng=es&nrm=iso&tlng=es
Timestamp: 2018-01-18 22:13:46+00:00

Document:
Modelado del Llenado de Vehículos con Cargas de Distintos Tamaños Mediante Programación Matemática Entera
Inf. tecnol. v.15 n.4 La Serena 2004
http://dx.doi.org/10.4067/S0718-07642004000400010
Información Tecnológica-Vol. 15 N°4-2004, págs.: 71-75
Integer Mathematical Models for Loading of Vehicles with Items of Different Sizes
L. Ferrer1, M.A. de los Santos1 y A.M. Coves2
Univ. Politécnica de Cataluña, (1) Dpto. de Ingeniería Mecánica, (2) Inst. de Organización y Control, Diagonal N°647, 08028 Barcelona-España
Este artículo presenta un modelo para optimizar el llenado de los vehículos considerando cargas palletizadas con elementos de distintas dimensiones. Para resolver el problema se han realizado tres modelos de programación matemática, con el fin de identificar los más eficientes en cada experimento. Los modelos se diferencian en el tipo de variables utilizadas y en las restricciones empleadas. Estas últimas dan el comportamiento lineal o no lineal del sistema. Se ha aplicado el modelado a una empresa del sector textil con el fin de determinar el número mínimo de vehículos necesario para realizar el transporte. Se concluye que el modelo permite obtener un porcentaje de resolución importante en poco tiempo para el tamaño y tipología de pedidos de la empresa.
This article presents a model for optimizing the loading of vehicles considering palletized loads of different sized elements. Three different mathematical programming models were applied in solving the problem in order to experimentally identify the most efficient one in real case situations. The models differ in the kinds of variables and the kinds of restrictions used, the latter providing the linear or non-linear behavior of the system. The modeling was applied to a textile sector company in order to determine the minimum number of vehicles necessary to carry out the transport. It is concluded that the model permits obtaining an important percentage of resolution in a short time based on the size and typology of orders of the company.
Keywords: vehicle loading, linear programming, palletized loads, mathematical modeling
Los costes asociados al transporte constituyen una parte muy importante de los costes de distribución de una empresa. El coste de transporte depende, entre otros aspectos, del número de viajes necesarios para transportar una determinada cantidad de producto y reducir este número supone un ahorro significativo.
La complejidad del cálculo del mínimo número de vehículos necesarios para transportar una determinada cantidad de producto depende de las variables consideradas. El cálculo resulta sencillo si la restricción de la capacidad se modela mediante una variable unidimensional. Este seria el caso de considerar como parámetros el peso o el número de paletas iguales que caben en un vehículo.
En el caso de tener cargas con elementos de distintas dimensiones, la capacidad del vehículo ya no puede modelarse con una variable unidimensional debido a que las paletas que cabrán dependen de la posición en que se coloquen. En este caso la limitación de capacidad pasa a ser una restricción 2D y la complejidad del problema aumenta de forma considerable.
Los problemas que consideran limitaciones de capacidad en 2D o 3D se denominan usual-mente problemas de corte o de empaquetado, en los que una serie de "objetos pequeños " se deben colocar en una serie de "objetos grandes" (Dyckhoff y Finke, 1992; Lodi et al., 2002). Se agrupan en este tipo de problemas, entre otros, los casos particulares de fabricación de piezas a partir del corte de material, la paletización de producto o el llenado de cajas con productos de diferentes dimensiones.
Chen et al. 1991, realizan estudios de pale-tización del producto y de llenado de cajas mediante modelos de programación lineal consiguiendo buenos resultados para proble-mas de dimensiones moderadas. En el caso de considerarse la tercera dimensión diversos autores desarrollan algoritmos heurísticos para obtener una solución del problema (Bortfeldt y Gehring , 2001).
Este trabajo se presentan dos modelos para minimizar el número de viajes realizados en el transporte mediante la optimización del llenado de los vehículos considerando cargas con elementos de distintos tamaños. Para ello se ha tratado como un caso particular del problema de corte y empaquetado. La evaluación y la comparación de los modelos se realiza aplicándolos a ejemplos de la bibliografía.
Se presenta así mismo la aplicación del modelo más adecuado a un caso real de una empresa del sector textil con el fin de optimizar el llenado de vehículos con los elementos de los pedidos de la empresa. Los experimentos se generan , en este caso de forma aleatoria a partir de los datos proporcionados por la empresa.
El llenado de vehículos mediante cargas de diferentes tamaños se ha modelado mediante programación matemática entera. Se han planteado dos modelos distintos para identificar el más eficientes para cada experimento. En estas modelos se varían, básicamente el tipo de variables utilizadas para determinar la colocación de las paletas. las variables pueden ser binarias o enteras.
El conjunto de parámetros que se utilizan en los tres modelos para caracterizar el sistema son los siguientes: NV: Vehículos disponibles; L: Longitud del vehículo; W: Anchura del vehículo; N: Número de paletas; Li: Longitud de la paleta i; Wi: Ancho de la paleta i; m: Constante auxiliar de valor
Modelización lineal con variables binarias
Las variables y la formulación matemática del modelo son las siguientes:
Xilwv: Variable binaria: La paleta i se sitúa (o no) en el punto (l,w) en el vehículo v
Vv: Variable binaria: El vehículo v se utiliza (o no).
La restricción (1) asegura que todas las paletas se asignan a algún vehículo, la (2) fuerza que los vehículos que tengan paletas asignadas consten como utilizados y la (3) evita la superposición de paletas.
Modelización lineal con variables enteras
Las variables y la formulación matemática del modelo es la siguiente:
Xi: Variable entera: coordenada longitudinal donde se sitúa la paleta i.
Yi: Variable entera: coordenada de anchura donde se sitúa la paleta i.
Vi: Variable entera: vehículo donde se sitúa la paleta i.
NV: Variable entera: número de vehículos utilizados.
a1ij, a2ij, a3ij, a4ij, a5ij, a6ij: Variables binarias auxiliares
Las restricciones (4) y (5) aseguran que las paletas se sitúen dentro de los vehículos de forma que éstos contengan toda su superficie, la (6) fuerza a que consten todos los vehículos utilizados y el conjunto de restricciones (7) evita la superposición de paletas.
Los dos modelos presentados se complementan con restricciones adicionales que per-miten simplificar el proceso de resolución: como cota mínima: el número mínimo de vehículos se calcula a partir del área necesaria para disponer todas las paletas.
Los diversos modelos se implementan con el paquete de resolución de programas mate-máticos enteros OPL Studio 3.7 de ILOG que ejecuta el programa CPLEX 9.0 en un ordenador Pentium IV a 1,7 GHz y con 1Gb de RAM.
La evaluación de los modelos presentados y de los métodos de resolución se basa, por una parte, en experimentos encontrados en la bibliografía y, por otra parte, en experimentos generados de forma aleatoria a partir de los datos proporcionados por una empresa del sector textil. Concretamente, el caso de es-tudio de esta empresa consiste en minimizar el número de vehículos necesarios para transportar cierta cantidad de producto en paletas.
En cuanto a la experimentación con ejemplares encontrados en la bibliografía, ha sido necesario reproducir exactamente los pro-blemas de estudio y adaptar los modelos, presentados en el apartado 2, en relación con el número de dimensiones consideradas en la restricción de la capacidad o la función obje-tivo. Se han reproducido los experimentos de tres artículos (Beasley, 1982; Chen et al., 1991; Chen et al.,1995). A continuación se resumen los ejemplares de estudio y el método de resolución utilizado, en estos tres trabajos:
1-Maximización del valor (función del área) de las piezas de distintos tipos colocadas en un contenedor. Problema 2D resuelto mediante programación lineal entera
2-Minimización del número de vehículos necesarios para colocar cierto número de paletas de distintos tipos. Problema 2D resuelto mediante programación lineal entera y mixta.
3-Minimización de la longitud necesaria para colocar cierto número de piezas de distintos tipos en un contenedor de base fijada. Problema 3D resuelto mediante programación lineal entera y mixta.
Los resultados muestran que un modelo será más o menos eficaz que el otro en función de la relación que exista entre el número de paletas que deben situarse y el número de tamaños diferentes de paletas En el modelo de variables enteras el número de variables es proporcional al número de paletas mientras que en el de variables binarias, el número de variables es proporcional al número de tipos de paletas diferentes
El modelo con variables enteras se muestra más eficaz cuando el número de paletas diferentes es importante y hay poca cantidad de cada una de ellas que es el caso de los ejemplos probados de la literatura. El modelo de variables binarias es más adecuado en el caso que el número de paletas diferentes sea pequeño y haya un número mayor de cada una de ellas. Este es el caso de la empresa del sector textil que desea estudiarse ya que disponen de pocos tipos de paletas y un número considerable de cada uno de los tipos. A continuación se presentan los resultados obtenidos para la empresa estudiada.
Los experimentos se han realizado considerando vehículos de dimensiones 12mx2,4m (contenedores de 40 pies) y seis tipos de paletas de las siguientes dimensiones:1200 x 800 mm, 1200 x 1200 mm, 2400 x 400 mm, 400 x 1200 mm, 400 x 400 mm, 800 x 800 mm.
Se han simulado tres experimentaciones diferentes considerando que cada tipo de paleta aparece en los ejemplares con probabilidades del 40%, 70% o del 100%., El número de paletas de cada tipo se genera de forma alea-toria en grupos de diez. Se han resuelto 100 ejemplares para los diferentes números de paletas considerados. Se ha fijado un tiempo máximo de resolución de 100s que se ha aumentado a 200 s en los casos en los que no se ha obtenido solución óptima con el primero.
La Figura 1 muestra el porcentaje de ejemplares resueltos en cada uno de los tres experimentos en función de la cantidad de paletas de cada tipo con un tiempo máximo de 100 s.
Fig. 1: Porcentaje de ejemplares resueltos función de la cantidad de paletas de cada tipo con un tiempo máximo de resolución de 100s.
Se observa que en el caso del experimento en el que la probabilidad de aparición de cada tipo es del 40%, el porcentaje de resolución de los ejemplares es superior al 90% independientemente del número de paletas de cada tipo. Para los otros porcentajes el número de ejemplares resueltos disminuye con el número de tipos y con el número de paletas de cada tipo, siendo el caso de que todos los tipos estén presentes, el más desfavorable. En este último se observa una disminución del porcentaje de resolución muy importante cuando el número total de paletas es de 150 o superior. El aumento del tiempo máximo de resolución a 200s no ha incrementado de forma significativa el número de ejemplares resueltos.
La Figura 2 muestra el tiempo medio de resolución para los ejemplares que se ha obtenido la solución óptima. Se observa crece con el número de tipos diferentes y con el número de paletas. En los casos resueltos no sobrepasa los 60 s.
Fig. 2: Tiempo medio de resolución de los ejemplares que se obtiene solución.
La Figura 3 muestra el tiempo de resolución y la Figura 4 el porcentaje de ejemplares resueltos en función del número total de paletas de diferentes tamaños. En ellas se observa la influencia del número de tipos y del número total de paletas, en el tiempo de resolución y en el porcentaje de resolución de los ejemplares.
Fig. 3: Tiempo de resolución en función del número total de paletas de diferentes tamaños
Fig. 4: Porcentaje de ejemplares resueltos en función del número total de paletas de diferentes tamaños
En las dos gráficas anteriores se observa que el tiempo de resolución y el porcentaje de resolución, para un mismo número de paletas, es siempre menor en el caso que el número de tipos sea menor.
La optimización del llenado de vehículos con cargas de diferentes tamaños y cantidades se puede realizar mediante la programación matemática entera. Si las variables son enteras el modelo es adecuado para el caso en que se disponga de muchos tipos de carga y pocas cantidades de cada tipo. Si las variables son binarias, el modelo es adecuado en el caso en que el número de tipos de carga sea pequeño y el número de elementos de cada tipo elevado.
El modelo binario se ha aplicado al caso de una compañía real del sector textil. Los resultados muestran que el número de elementos diferentes que se combinan tienen una gran influencia en la resolución.
El modelo permite obtener un porcentaje de resolución importante en poco tiempo para el tamaño y tipología de pedidos de la empresa.
Beasley, J.E., An exact two-dimensional non-guillotine cutting tree search procedure, Operational Research, 33(1), p. 49 (1982). [ Links ]
Bortfeldt, A y H. Gehring, A hybrid genetic algorithm for the container loading problem. European Journal of Operational Research, Theory and Methodology. 131, 143-161 (2001). [ Links ]
Chen, C.S., S.M. Lee, y Q.S. Shen, An analytical model for the container loading problem. European Journal of Operational Research, 80, pag. 68 (1995) [ Links ]
Chen, C. S., S. Sarin y B. Ram, The palet loading problem with non-uniform box sizes. International Journal of Operational Research. 29 (10), 1963-1968 (1991). [ Links ]
Dyckhoff, H y U. Finke. Cutting and Packing in Production and Distribution. Physical-Verlag, Heidelberg (1992). [ Links ]
Lodi, A., S. Martello, M. Monaci, Two-dimensional packing problems: A survey. European Journal of Operations Research 141, 241-252 (2002). [ Links ]
Correspondencia a: (e-mail: laia.ferrer@upc.es)

References: resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución