El artículo describe cómo implementar Almacenaje-system, nos enfrentamos a la necesidad de resolver un problema de agrupación en clústeres no estándar y qué algoritmos utilizamos para resolverlo. Le diremos cómo aplicamos un enfoque científico sistemático para resolver el problema, qué dificultades encontramos y qué lecciones aprendimos.
Esta publicación inicia una serie de artículos en los que compartimos nuestra exitosa experiencia en la implementación de algoritmos de optimización en procesos de almacén. El propósito de la serie de artículos es familiarizar a la audiencia con los tipos de problemas de optimización de las operaciones de almacén que surgen en casi cualquier almacén mediano y grande, así como contar nuestra experiencia en la resolución de dichos problemas y los obstáculos encontrados en el camino. . Los artículos serán de utilidad para quienes trabajan en la industria de logística de almacenes, implementan Almacenaje-sistemas, así como programadores interesados en aplicaciones de las matemáticas en los negocios y optimización de procesos en una empresa.
Cuello de botella en los procesos
En 2018, completamos un proyecto para implementar Almacenaje-sistemas en el almacén de la empresa “Trading House “LD” en Chelyabinsk. Implementamos el producto “1C-Logistics: Warehouse Management 3” para 20 lugares de trabajo: operadores Almacenaje, tenderos, conductores de montacargas. El almacén medio tiene una superficie de unos 4 mil m2, el número de celdas es de 5000 y el número de referencias es de 4500. En el almacén se almacenan válvulas de bola de producción propia de varios tamaños, desde 1 kg hasta 400 kg. El inventario en el almacén se almacena en lotes, ya que es necesario seleccionar mercancías según FIFO.
Al diseñar esquemas de automatización de procesos de almacén, nos enfrentamos al problema existente de un almacenamiento de inventario no óptimo. Las particularidades de las grúas de almacenamiento y estiba son tales que en una celda de almacenamiento unitaria sólo se pueden contener artículos de un lote. Los productos llegan al almacén diariamente y cada llegada es un lote separado. En total, como resultado de 1 mes de funcionamiento del almacén, se crean 30 lotes separados, a pesar de que cada uno debe almacenarse en una celda separada. Los productos a menudo se seleccionan no en paletas enteras, sino en piezas, y como resultado, en la zona de selección de piezas en muchas celdas se observa la siguiente imagen: en una celda con un volumen de más de 1 m3 hay varias piezas de grúas que Ocupan menos del 5-10% del volumen celular.
Fig 1. Foto de varias mercancías en una celda.
Está claro que la capacidad de almacenamiento no se está utilizando de forma óptima. Para imaginar la magnitud del desastre, puedo dar cifras: en promedio, hay de 1 a 3 celdas de este tipo con un volumen de más de 100 m300 con saldos "minúsculos" durante los diferentes períodos de funcionamiento del almacén. Dado que el almacén es relativamente pequeño, durante las temporadas en las que el almacén está lleno, este factor se convierte en un “cuello de botella” y ralentiza mucho los procesos del almacén.
idea de solución de problema
Surgió una idea: los lotes de sobras con las fechas más cercanas deberían reducirse a un solo lote, y los sobrantes con un lote unificado deberían colocarse de forma compacta en una celda, o en varias, si no hay suficiente espacio en una para acomodar las cantidad total de sobras.
Figura 2. Esquema para comprimir residuos en células.
Esto le permite reducir significativamente el espacio ocupado del almacén que se utilizará para colocar nuevas mercancías. En una situación en la que la capacidad del almacén está sobrecargada, esta medida es extremadamente necesaria; de lo contrario, es posible que simplemente no haya suficiente espacio libre para acomodar nuevos productos, lo que provocará una parada en los procesos de colocación y reabastecimiento del almacén. Anteriormente antes de la implementación Almacenaje-Los sistemas realizaron esta operación manualmente, lo que resultó ineficaz, ya que el proceso de búsqueda de residuos adecuados en las células fue bastante largo. Ahora, con la introducción de un sistema WMS, decidimos automatizar el proceso, acelerarlo y hacerlo inteligente.
El proceso de resolución de dicho problema se divide en 2 etapas:
- en la primera etapa encontramos grupos de lotes cercanos en fecha de compresión;
- en la segunda etapa, para cada grupo de lotes calculamos la ubicación más compacta de los productos restantes en las celdas.
En el artículo actual nos centraremos en la primera etapa del algoritmo y dejaremos la cobertura de la segunda etapa para el próximo artículo.
Buscar un modelo matemático del problema.
Antes de sentarnos a escribir código y reinventar nuestra rueda, decidimos abordar este problema científicamente, es decir: formularlo matemáticamente, reducirlo a un conocido problema de optimización discreta y utilizar algoritmos efectivos existentes para resolverlo, o tomar estos algoritmos existentes. como base y modificarlos según las particularidades del problema práctico que se está resolviendo.
Dado que de la formulación empresarial del problema se desprende claramente que estamos tratando con conjuntos, formularemos dicho problema en términos de teoría de conjuntos.
Dejar – el conjunto de todos los lotes del resto de un determinado producto en un almacén. Dejar – dada la constante de días. Dejar – un subconjunto de lotes, donde la diferencia de fechas para todos los pares de lotes del subconjunto no excede una constante . Necesitamos encontrar el número mínimo de subconjuntos disjuntos. , tal que todos los subconjuntos en conjunto darían muchos .
En otras palabras, necesitamos encontrar grupos o clusters de partidos similares, donde el criterio de similitud esté determinado por la constante . Esta tarea nos recuerda el conocido problema de agrupación. Es importante decir que el problema considerado se diferencia del problema de agrupamiento en que nuestro problema tiene una condición estrictamente definida para el criterio de similitud de los elementos del grupo, determinada por la constante , pero en el problema de agrupamiento no existe tal condición. El enunciado del problema de agrupamiento y la información sobre este problema se pueden encontrar
Entonces logramos formular el problema y encontrar un problema clásico con una formulación similar. Ahora es necesario considerar algoritmos conocidos para resolverlo, para no reinventar la rueda, sino tomar las mejores prácticas y aplicarlas. Para resolver el problema de la agrupación, consideramos los algoritmos más populares, a saber: -medio, -medios, algoritmo para identificar componentes conectados, algoritmo de árbol de expansión mínimo. Se puede encontrar una descripción y análisis de dichos algoritmos.
Para resolver nuestro problema, algoritmos de agrupamiento. -medios y -los medios no son aplicables en absoluto, ya que el número de conglomerados nunca se conoce de antemano y dichos algoritmos no tienen en cuenta la restricción de días constantes. Inicialmente, estos algoritmos fueron descartados.
Para resolver nuestro problema, el algoritmo para identificar componentes conectados y el algoritmo de árbol de expansión mínima son más adecuados, pero resultó que no se pueden aplicar "de frente" al problema que se está resolviendo y obtener una buena solución. Para explicar esto, consideremos la lógica de funcionamiento de tales algoritmos en relación con nuestro problema.
Considere el gráfico , en el que los vértices son el conjunto de partidos , y el borde entre los vértices и tiene un peso igual a la diferencia de días entre lotes и . En el algoritmo para identificar componentes conectados, se especifica el parámetro de entrada. Donde , y en el gráfico Se eliminan todos los bordes en los que el peso es mayor. . Sólo los pares de objetos más cercanos permanecen conectados. El objetivo del algoritmo es seleccionar dicho valor. , en el que el gráfico “se desmorona” en varios componentes conectados, donde las partes pertenecientes a estos componentes satisfarán nuestro criterio de similitud, determinado por la constante . Los componentes resultantes son clusters.
El algoritmo del árbol de expansión mínima se basa primero en un gráfico. árbol de expansión mínimo, y luego elimina secuencialmente los bordes con el peso más alto hasta que el gráfico "se desmorona" en varios componentes conectados, donde las partes que pertenecen a estos componentes también satisfarán nuestro criterio de similitud. Los componentes resultantes serán grupos.
Cuando se utilizan tales algoritmos para resolver el problema en consideración, puede surgir una situación como la de la Figura 3.
Fig 3. Aplicación de algoritmos de agrupamiento al problema que se está resolviendo
Digamos que nuestra constante para la diferencia entre los días del lote es 20 días. Grafico se representó en forma espacial para facilitar la percepción visual. Ambos algoritmos produjeron una solución de 3 grupos, que se puede mejorar fácilmente combinando los lotes colocados en grupos separados entre sí. Es obvio que dichos algoritmos deben modificarse para adaptarse a las características específicas del problema que se está resolviendo, y su aplicación en su forma pura a la solución de nuestro problema dará malos resultados.
Entonces, antes de comenzar a escribir código para algoritmos gráficos modificados para nuestra tarea y reinventar nuestra propia bicicleta (en cuyas siluetas ya podíamos distinguir los contornos de ruedas cuadradas), decidimos nuevamente abordar científicamente este problema, a saber: Intente reducirlo a otra optimización de problema discreto, con la esperanza de que los algoritmos existentes para resolverlo puedan aplicarse sin modificaciones.
¡Otra búsqueda de un problema clásico similar ha tenido éxito! Logramos encontrar un problema de optimización discreto, cuya formulación coincide 1 en 1 con la formulación de nuestro problema. Esta tarea resultó ser establecer problema de cobertura. Presentemos la formulación del problema en relación con nuestras especificidades.
Hay un conjunto finito y familia de todos sus subconjuntos disjuntos de partidos, de modo que la diferencia en fechas para todos los pares de partidos de cada subconjunto de la familia no excede las constantes . Una cubierta se llama familia. de menor potencia, cuyos elementos pertenecen a , tal que la unión de conjuntos de la familia debe dar el conjunto de todas las partes .
Un análisis detallado de este problema se puede encontrar и Se pueden encontrar otras opciones para la aplicación práctica del problema de cobertura y sus modificaciones.
Algoritmo para resolver el problema.
Hemos decidido el modelo matemático del problema a resolver. Ahora veamos el algoritmo para resolverlo. Subconjuntos de la familia se puede encontrar fácilmente mediante el siguiente procedimiento.
- Organizar lotes de un conjunto en orden descendente de sus fechas.
- Encuentre las fechas mínimas y máximas de los lotes.
- Para cada dia desde la fecha mínima hasta la máxima, busque todos los lotes cuyas fechas difieren de no más que (entonces el valor Es mejor tomar el número par).
Lógica del procedimiento para formar una familia de conjuntos. en días se presenta en la Figura 4.
Fig.4. Formación de subconjuntos de partidos.
Este procedimiento no es necesario para todos. revise todos los demás lotes y verifique la diferencia en sus fechas o con el valor actual Muévase hacia la izquierda o hacia la derecha hasta encontrar un lote cuya fecha sea diferente a la en más de la mitad del valor de la constante. Todos los elementos posteriores, al moverse tanto hacia la derecha como hacia la izquierda, no nos interesarán, ya que para ellos la diferencia en días solo aumentará, ya que los elementos de la matriz estaban inicialmente ordenados. Este enfoque ahorrará mucho tiempo cuando el número de fiestas y la distribución de sus fechas sean significativamente grandes.
El problema de cobertura del conjunto es -difícil, lo que significa que no existe un algoritmo rápido (con un tiempo de operación igual a un polinomio de los datos de entrada) y preciso para resolverlo. Por lo tanto, para resolver el problema de cobertura de conjuntos, se eligió un algoritmo codicioso rápido, que, por supuesto, no es preciso, pero tiene las siguientes ventajas:
- Para problemas de tamaño pequeño (y este es exactamente nuestro caso), calcula soluciones bastante cercanas al óptimo. A medida que aumenta el tamaño del problema, la calidad de la solución se deteriora, pero todavía con bastante lentitud;
- Muy fácil de implementar;
- Rápido, ya que su tiempo de ejecución estimado es .
El algoritmo codicioso selecciona conjuntos según la siguiente regla: en cada etapa, se selecciona un conjunto que cubre el número máximo de elementos aún no cubiertos. Puede encontrar una descripción detallada del algoritmo y su pseudocódigo.
No se ha realizado una comparación de la precisión de dicho algoritmo codicioso en datos de prueba del problema que se está resolviendo con otros algoritmos conocidos, tales como el algoritmo probabilístico codicioso, el algoritmo de colonia de hormigas, etc. Los resultados de comparar dichos algoritmos con datos aleatorios generados se pueden encontrar
Implementación e implementación del algoritmo.
Este algoritmo fue implementado en el lenguaje. 1S y fue incluido en un procesamiento externo llamado "Compresión de Residuos" que estaba conectado a Almacenaje-sistema. No implementamos el algoritmo en el lenguaje. C ++ y usarlo desde un componente Nativo externo, lo cual sería más correcto, ya que la velocidad del código es menor C + + veces y en algunos ejemplos incluso decenas de veces más rápido que la velocidad de un código similar en 1S. en la lengua 1S El algoritmo se implementó para ahorrar tiempo de desarrollo y facilitar la depuración en la base de producción del cliente. El resultado del algoritmo se presenta en la Figura 5.
Fig.5. Procesamiento para “comprimir” residuos
La Figura 5 muestra que en el almacén especificado, los saldos actuales de mercancías en las celdas de almacenamiento se dividen en grupos, dentro de los cuales las fechas de los lotes de mercancías difieren entre sí en no más de 30 días. Dado que el cliente fabrica y almacena válvulas de bola metálicas en su almacén, cuya vida útil se calcula en años, esta diferencia de fechas puede despreciarse. Tenga en cuenta que este tipo de procesamiento se utiliza actualmente de manera sistemática en la producción, y los operadores Almacenaje confirman la buena calidad de la agrupación de partidos.
Conclusiones y continuación
La principal experiencia que obtuvimos al resolver un problema tan práctico es la confirmación de la efectividad del uso del paradigma: las matemáticas. planteamiento del problema estera famosa. modelo algoritmo famoso algoritmo teniendo en cuenta las características específicas del problema. La optimización discreta existe desde hace más de 300 años y durante este tiempo la gente ha logrado considerar muchos problemas y acumular mucha experiencia en su solución. En primer lugar, es más recomendable recurrir a esta experiencia, y sólo entonces empezar a reinventar tu rueda.
En el próximo artículo continuaremos la historia sobre los algoritmos de optimización y veremos el más interesante y mucho más complejo: un algoritmo para la "compresión" óptima de residuos celulares, que utiliza como entrada los datos recibidos del algoritmo de agrupamiento por lotes.
preparó el artículo
Roman Shangin, programador del departamento de proyectos,
Primera empresa TBI, Chelyabinsk
Fuente: habr.com