Contenedor: La cuadratura del círculo
Contenedor. Rafael Torres de la Facultad de Ingeniería nos comparte un artículo sobre matemáticas, heurística y monos para resolver dilemas de empaquetamiento.
El doctor Rafael Torres Escobar, investigador de la Facultad de Ingeniería de la Universidad Anáhuac México y miembro del Sistema Nacional de Investigadores (SNI), nos comparte un artículo sobre contenedores y optimización de espacios.
La cuadratura del círculo
¿Cómo hacer más eficiente el espacio al colocar objetos circulares en contenedores rectangulares? Este tipo de cuestionamientos que plantean la necesidad de acomodar objetos en áreas delimitadas (contenedores) se conocen en el campo de la optimización como Problemas de Corte y Empaquetamiento.
La colocación de objetos en un contenedor se denomina patrón de colocación y debe satisfacer las limitaciones tecnológicas para cumplir con los objetivos del negocio. Las restricciones tecnológicas comúnmente utilizadas en problemas de empaquetamiento son de traslape y de dominio, para garantizar que ningún objeto quede superpuesto con otro y, además, que ningún objeto quede fuera del contenedor.
Se trata de problemas difíciles de resolver debido a su naturaleza combinatoria en la forma de colocar los objetos. Por ello se consideran problemas de optimización combinatoria NP-hard, es decir, que ningún procedimiento puede resolverlos de forma exacta en un tiempo razonable (de 30 minutos a 2 horas como máximo), pudiendo demorarse años en resolverse de manera exhaustiva.
Este es el contexto del trabajo de investigación Monkey algorithm for packing circles with binary variables, publicado en el libro Intelligent computing & optimization, de la editorial Springer. Para el desarrollo de dicho trabajo, se utilizó un modelo matemático y un método heurístico (aproximado) para la solución. En ambos casos, la forma rectangular del contenedor se aproxima mediante la generación de puntos que representan coordenadas en un plano de dos dimensiones para decidir si se coloca un objeto o no en ese punto.
Al usar un conjunto de puntos como posibles coordenadas de colocación de los objetos, ayudamos a reducir la complejidad del problema y resolverlo en menos tiempo, sin embargo, aún existen retos que se deben enfrentar con esta estrategia porque se debe usar un número adecuado de puntos. Por ejemplo, si usamos una cantidad de puntos muy grande el modelo puede demorar mucho tiempo en resolverse; por otro lado, si la cantidad de puntos no es suficiente vamos a desperdiciar espacio en el contenedor.
Aunque la estrategia de puntos como posibles coordenadas de colocación en un principio resulta satisfactoria, también se decidió trabajar con una estrategia de solución aproximada. Para ello, se programó un algoritmo en el lenguaje Python con uso de librerías para cómputo científico. El algoritmo tuvo como inspiración el área de cómputo evolutivo emulando el comportamiento de los monos y la forma en la que buscan alimentarse.
Se hizo una representación abstracta de una población inicial de monos que se mueven en manada buscando alimentarse. Un componente importante en este algoritmo es la cooperación entre cada mono de la manada para indicar si alguno de ellos ha encontrado un mejor lugar para alimentarse y que de esta manera todos los demás miembros de la manda acudan al lugar.
Un mono dentro de la manada se representó como un conjunto de objetos en el contenedor sin importar si ocupaba o no toda el área, de esta manera dos monos representan dos patrones de colocación diferentes. Mediante la aplicación de reglas probabilísticas dentro de un esquema iterativo, se decidía si se intercambiaban patrones de acomodo para evaluar posteriormente una función de adaptación que representaba el área ocupada dentro del contenedor, de la misma forma en que se hacía en el modelo matemático.
Los resultados de la aplicación de un enfoque exacto y aproximado para resolver un problema de empaquetamiento en un contenedor rectangular nos permitieron comparar la practicidad y calidad de las soluciones. El modelo matemático da mejores resultados, pero demora más tiempo en la obtención de una solución, por otro lado, el modelo aproximado converge a una solución en menor tiempo. Aunque esta solución no es la mejor, resulta buena en términos prácticos. De estas dos propuestas, quedó abierta la posible combinación de las estrategias para obtener la mejor solución en el menor tiempo posible.
Referencia del capítulo de libro: Torres, R., Marmolejo, J.A., Litvinchev, I., & Vasant, P. (2019). Monkey Algorithm for Packing Circles with Binary Variables. En P. Vasant, I. Zelinka & G.W. Weber (Eds.), Intelligent Computing & Optimization (pp. 547-559). doi: https://doi.org/10.1007/978-3-030-00979-3_58
