En este artículo te contamos cómo resolvimos el problema de la falta de celdas libres en un almacén y el desarrollo de un algoritmo de optimización discreto para solucionar dicho problema. Hablemos de cómo "construimos" el modelo matemático del problema de optimización y de las dificultades que encontramos inesperadamente al procesar los datos de entrada para el algoritmo.
Si está interesado en las aplicaciones de las matemáticas en los negocios y no le temen las rígidas transformaciones de identidad de las fórmulas en el nivel de quinto grado, ¡bienvenido al gato!
El artículo será útil para quienes implementen. Almacenaje-sistemas, trabajos en la industria de logística de producción o almacén, así como programadores interesados en aplicaciones de las matemáticas en los negocios y optimización de procesos en una empresa.
Parte introductoria
Esta publicación continúa la 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.
В describe los detalles del almacén donde implementamos Almacenaje-sistema, y también explica por qué necesitábamos resolver el problema de agrupar lotes de productos restantes durante la implementación Almacenaje-sistemas, y cómo lo hicimos.
Cuando terminamos de escribir el artículo sobre algoritmos de optimización, resultó ser muy extenso, por lo que decidimos dividir el material acumulado en 2 partes:
- En la primera parte (este artículo) hablaremos de cómo “construimos” el modelo matemático del problema y de las grandes dificultades que encontramos inesperadamente al procesar y transformar los datos de entrada para el algoritmo.
- En la segunda parte consideraremos en detalle la implementación del algoritmo en el lenguaje. C + +, realizaremos un experimento computacional y resumiremos la experiencia que adquirimos durante la implementación de dichas "tecnologías inteligentes" en los procesos comerciales del cliente.
Cómo leer un artículo. Si leyó el artículo anterior, puede ir inmediatamente al capítulo "Resumen de las soluciones existentes", si no, la descripción del problema que se está resolviendo se encuentra en el spoiler a continuación.
Descripción del problema que se está resolviendo en el almacén del cliente.
Cuello de botella en los procesos
En 2018, completamos un proyecto para implementar Almacenaje-sistemas en el almacén “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.
Durante el diseño de esquemas de automatización de procesos de almacén, nos enfrentamos al problema existente de almacenamiento de inventario no óptimo. Las particularidades del almacenamiento y la colocación de grúas son tales que en una celda unitaria de almacenamiento sólo pueden contener artículos de un lote (ver Fig. 1). 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 piezas 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 de mayor actividad del almacén, este factor se convierte en un "cuello de botella" y ralentiza en gran medida los procesos de aceptación y envío 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. En la Figura 2 se muestra un ejemplo de dicha “compresión”.
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 mercancías nuevas, lo que provocará una parada en los procesos de colocación y reposición del almacén y, como consecuencia, a detener la aceptación y el envío. Anteriormente, antes de la implementación del sistema WMS, esta operación se realizaba manualmente, lo que resultaba ineficaz, ya que el proceso de búsqueda de saldos adecuados en las celdas era 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 (dedicados a esta tarea );
- 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 segunda etapa del algoritmo.
Revisión de soluciones existentes.
Antes de pasar a la descripción de los algoritmos que hemos desarrollado, conviene hacer un breve repaso de los sistemas ya existentes en el mercado. Almacenaje, que implementan una funcionalidad de compresión óptima similar.
En primer lugar, cabe destacar el producto “1C: Enterprise 8. WMS Logistics. Gestión de almacén 4", propiedad de 1C y replicada por ella y que pertenece a la cuarta generación. Almacenaje-sistemas desarrollados por AXELOT. Este sistema afirma tener funcionalidad de compresión, que está diseñada para unir restos de productos dispares en una celda común. Vale la pena mencionar que la funcionalidad de compresión en dicho sistema también incluye otras posibilidades, por ejemplo, corregir la ubicación de mercancías en celdas según sus clases ABC, pero no nos detendremos en ellas.
Si analizamos el código del sistema 1C: Enterprise 8. WMS Logistics. Gestión de almacén 4" (que está abierta en esta parte de la funcionalidad), podemos concluir lo siguiente. El algoritmo de compresión residual implementa una lógica lineal bastante primitiva y no se puede hablar de ninguna compresión "óptima". Naturalmente, no prevé la agrupación de partidos. Varios clientes que implementaron un sistema de este tipo se quejaron de los resultados de la planificación de la compresión. Por ejemplo, en la práctica a menudo se producía la siguiente situación durante la compresión: 100 uds. Está previsto trasladar los bienes restantes de una celda a otra celda, donde se encuentra 1 pieza. bienes, aunque lo óptimo desde el punto de vista del consumo de tiempo es hacer lo contrario.
Además, en muchos países extranjeros se declara la funcionalidad de comprimir los productos restantes en celdas. Almacenaje-sistemas, pero, desafortunadamente, no tenemos información real sobre la efectividad de los algoritmos (esto es un secreto comercial), y mucho menos una idea sobre la profundidad de su lógica (software propietario de código cerrado), por lo que no podemos juzgar.
Buscar un modelo matemático del problema.
Para diseñar algoritmos de alta calidad para resolver un problema, primero es necesario formular claramente este problema matemáticamente, que es lo que haremos.
hay muchas celulas , que contienen restos de algunos bienes. En lo que sigue, llamaremos a estas células células donantes. denotemos volumen de mercancías en la celda $.
Es importante decir que solo un producto de un lote, o varios lotes previamente combinados en un grupo (léase: ), lo que se debe a las particularidades del almacenamiento y almacenamiento de mercancías. Diferentes productos o diferentes grupos de lotes deben ejecutar su propio procedimiento de compresión por separado.
hay muchas celulas , en el que potencialmente se pueden colocar residuos de células de donantes. A estas células las llamaremos además células contenedoras. Pueden ser células libres en el almacén o células donadas de una variedad de . siempre mucho es un subconjunto .
Para cada celda desde muchos Se han establecido restricciones de capacidad , medido en dm3. Un dm3 es un cubo de 10 cm de lado, los productos almacenados en el almacén son bastante grandes, por lo que en este caso dicha discretización es suficiente.
Dada una matriz de distancias más cortas en metros entre cada par de celdas Donde и pertenecen a conjuntos и respectivamente.
denotemos “Costos” de mover bienes desde la celda. en una celda . denotemos “Costos” de elegir un contenedor. para mover residuos de otras células hacia él. Cómo exactamente y en qué unidades de medida se calcularán los valores и Lo consideraremos más a fondo (consulte la sección sobre preparación de datos de entrada), por ahora basta con decir que dichos valores serán directamente proporcionales a los valores. и respectivamente.
Denotamos por una variable que toma el valor 1 si el resto es de la celda movido al contenedor y 0 en caso contrario. Denotemos por una variable que toma el valor 1 si el contenedor contiene los bienes restantes y 0 en caso contrario.
La tarea se expresa de la siguiente manera.: necesitas encontrar tantos contenedores y así "unir" las células del donante a las células del contenedor para minimizar la función
bajo restricciones
En total, al calcular la solución al problema, nos esforzamos por:
- en primer lugar, ahorrar capacidad de almacenamiento;
- en segundo lugar, ahorrar tiempo a los tenderos.
La última restricción significa que no podemos mover mercancías a un contenedor que no elegimos y, por lo tanto, no “incurrimos en costos” por elegirlo. Esta restricción también significa que el volumen de mercancías trasladadas desde las celdas al contenedor no debe exceder la capacidad del contenedor. Al resolver un problema nos referimos a un conjunto de contenedores. y métodos para unir células de donantes a contenedores.
Esta formulación del problema de optimización no es nueva y ha sido estudiada por muchos matemáticos desde principios de los años 80 del siglo pasado. En la literatura extranjera existen 2 problemas de optimización con un modelo matemático adecuado: и (hablaremos de las diferencias en las tareas más adelante). Vale la pena decir que en la literatura matemática, la formulación de estos dos problemas de optimización se formula en términos de la ubicación de las empresas en el terreno, de ahí el nombre "Ubicación de las instalaciones". En su mayor parte, se trata de un homenaje a la tradición, ya que por primera vez la necesidad de resolver este tipo de problemas combinatorios surgió del campo de la logística, principalmente del sector militar-industrial en los años 50 del siglo pasado. En términos de ubicación de la empresa, dichas tareas se formulan de la siguiente manera:
- Hay un número finito de ciudades donde es potencialmente posible ubicar empresas manufactureras (en adelante, ciudades manufactureras). Para cada ciudad manufacturera, se especifican los costos de abrir una empresa en ella, así como una limitación en la capacidad de producción de la empresa abierta en ella.
- Existe un conjunto finito de ciudades donde realmente se encuentran los clientes (en adelante, ciudades clientes). Para cada una de estas ciudades clientes, se especifica el volumen de demanda de productos. Para simplificar, supondremos que sólo hay un producto producido por las empresas y consumido por los clientes.
- Para cada par de ciudad-fabricante y ciudad-cliente, se especifica el valor de los costos de transporte para entregar el volumen requerido de productos del fabricante al cliente.
Necesita encontrar en qué ciudades abrir negocios y cómo vincular clientes a dichos negocios para:
- Los costos totales de apertura de empresas y los costos de transporte fueron mínimos;
- El volumen de demanda de los clientes asignados a cualquier empresa abierta no excedía la capacidad de producción de esa empresa.
Ahora vale la pena mencionar la única diferencia entre estos dos problemas clásicos:
- Problema de ubicación de instalaciones capacitadas de fuente única: el cliente recibe suministro desde una sola instalación abierta;
- Problema de ubicación de instalaciones capacitadas de múltiples fuentes: el cliente puede recibir suministro desde varias instalaciones abiertas al mismo tiempo.
Esta diferencia entre los dos problemas es insignificante a primera vista, pero, de hecho, conduce a una estructura combinatoria completamente diferente de tales problemas y, como consecuencia, a algoritmos completamente diferentes para resolverlos. Las diferencias entre las tareas se demuestran en la siguiente figura.
Fig. 3. a) Problema de ubicación de instalaciones capacitadas de múltiples fuentes
Fig. 3. b) Problema de ubicación de instalaciones capacitadas de fuente única
Ambas tareas -difícil, es decir, no existe un algoritmo exacto que resuelva tal problema en un polinomio de tiempo en el tamaño de los datos de entrada. En palabras más simples, todos los algoritmos exactos para resolver un problema funcionarán en un tiempo exponencial, aunque quizás más rápido que una búsqueda completa de opciones. Desde la tarea -difícil, entonces consideraremos solo heurísticas aproximadas, es decir, algoritmos que calcularán consistentemente soluciones muy cercanas a las óptimas y funcionarán con bastante rapidez. Si está interesado en una tarea de este tipo, puede encontrar una buena descripción general en ruso aquí.
Si pasamos a la terminología de nuestro problema de compresión óptima de bienes en celdas, entonces:
- Las ciudades clientes son células donantes. con los bienes restantes,
- ciudades manufactureras – células de contenedores , en el que se supone que se depositarán los restos de otras celdas,
- costos de transporte - costos de tiempo tendero para mover el volumen de mercancías de la célula donante en una celda contenedora ;
- costos de abrir un negocio - costos de elegir un contenedor , igual al volumen de la celda contenedora , multiplicado por un determinado coeficiente para ahorrar volúmenes libres (el valor del coeficiente es siempre > 1) (consulte la sección de preparación de datos de entrada).
Una vez establecida la analogía con las conocidas soluciones clásicas del problema, es necesario responder a una pregunta importante de la que depende la elección de la arquitectura del algoritmo de solución: mover los restos de la célula donante sólo es posible a una y solo un contenedor (fuente única), o ¿es posible mover los restos a varias celdas de contenedor (fuente múltiple)?
Vale la pena señalar que en la práctica se dan ambas formulaciones del problema. A continuación presentamos todos los pros y los contras de cada una de estas configuraciones:
| Variante del problema | Ventajas de la opción | Contras de la opción |
|---|---|---|
| Única fuente | Operaciones de movimiento de mercancías calculadas utilizando esta variante del problema:
|
|
| Múltiples fuentes | Las compresiones calculadas con esta versión del problema suelen ser entre un 10 y un 15 % más compactas en comparación con las compresiones calculadas con la opción "Fuente única". Pero también observamos que cuanto menor es el número de residuos en las células del donante, menor es la diferencia en la compacidad. | Operaciones de movimiento de mercancías calculadas utilizando esta variante del problema:
|
Tabla 1. Pros y contras de las opciones de fuente única y fuente múltiple.
Dado que la opción de fuente única tiene más ventajas, y teniendo en cuenta también el hecho de que cuanto menor es el número de residuos en las células del donante, menor es la diferencia en el grado de compacidad de compresión calculado para ambas variantes del problema, nuestra elección recayó en la opción de Fuente única.
Vale decir que también se produce la solución a la opción Multi-Source. Existe una gran cantidad de algoritmos efectivos para resolverlo, la mayoría de los cuales se reducen a resolver una serie de problemas de transporte. Además, no sólo existen algoritmos eficientes, sino también elegantes, por ejemplo,
Preparar datos de entrada
Antes de comenzar a analizar y desarrollar un algoritmo para resolver un problema, es necesario decidir qué datos y de qué forma los alimentaremos como entrada. No hay problemas con el volumen de mercancías restantes en las celdas donantes y la capacidad de las celdas contenedoras, ya que esto es trivial: tales cantidades se medirán en m3, pero con los costos de usar una celda contenedora y la matriz de costos de movimiento, no todo ¡Es tan simple!
Veamos primero el cálculo. costos de mover mercancías desde la célula donante a la célula contenedora. En primer lugar, es necesario decidir en qué unidades de medida calcularemos los costes de movimiento. Las dos opciones más obvias son los metros y los segundos. No tiene sentido calcular los costes de viaje en metros “puros”. Demostremos esto con un ejemplo. deja que la celda ubicado en el primer nivel, celda eliminado por 30 metros y ubicado en el segundo nivel:
- Moviendo desde в más caro que mudarse de в , ya que bajar del segundo nivel (a 1,5-2 metros del suelo) es más fácil que subir al segundo, aunque la distancia será la misma;
- Mover 1 ud. bienes de la celda в Será más fácil que mover 10 piezas. el mismo producto, aunque la distancia será la misma.
Es mejor considerar los costos de mudanza en segundos, ya que esto le permite tener en cuenta tanto la diferencia en los niveles como la diferencia en la cantidad de bienes transportados. Para contabilizar el costo del movimiento en segundos, debemos descomponer la operación de movimiento en componentes elementales y tomar medidas de tiempo para la ejecución de cada componente elemental.
dejar desde la celda se mueve ORDENADOR PERSONAL. mercancías en contenedor . dejar – la velocidad media de movimiento de un trabajador en el almacén, medida en m/seg. Dejar и – velocidades medias de operaciones puntuales de toma y colocación, respectivamente, para un volumen de mercancías igual a 4 dm3 (el volumen medio que un empleado toma a la vez en un almacén cuando realiza operaciones). Dejar и la altura de las celdas desde las que se realizan las operaciones de toma y venta, respectivamente. Por ejemplo, la altura promedio del primer nivel (piso) es de 1 m, el segundo nivel es de 2 m, etc. Entonces la fórmula para calcular el tiempo total para completar una operación de movimiento es siguiente:
La Tabla 2 muestra estadísticas sobre el tiempo de ejecución de cada operación elemental, recopiladas por los empleados del almacén, teniendo en cuenta las particularidades de la mercancía almacenada.
| Nombre de la operación | designación | promedio |
|---|---|---|
| Velocidad media de un trabajador moviéndose por el almacén | |
1,5 m / s |
| Velocidad media de una operación a poner (para un volumen de producto de 4 dm3) | |
2,4 sec |
Tabla 2. Tiempo promedio para completar las operaciones de almacén
Hemos decidido el método para calcular los costes de mudanza. Ahora tenemos que descubrir cómo calcular Costos de elegir una celda contenedora.. Aquí todo es mucho, mucho más complicado que con los costes de mudanza, porque:
- En primer lugar, los costos deben depender directamente del volumen de la célula: es mejor colocar el mismo volumen de residuos transferidos de las células del donante en un recipiente de menor volumen que en uno grande, siempre que dicho volumen quepa completamente en ambos contenedores. Así, minimizando los costes totales de selección de contenedores, se procura ahorrar la “escasa” capacidad de almacenamiento libre en la zona de selección para realizar posteriores operaciones de colocación de mercancías en las celdas. La Figura 4 demuestra las opciones para transferir residuos a contenedores grandes y pequeños y las consecuencias de estas opciones de transferencia en operaciones de almacén posteriores.
- en segundo lugar, dado que para resolver el problema original necesitamos minimizar exactamente los costos totales, y esta es la suma de los costos de mudanza y los costos de elegir contenedores, entonces los volúmenes de las celdas en metros cúbicos deben estar de alguna manera vinculados a segundos, lo cual está lejos de ser trivial.
Arroz. 4. Opciones para trasladar las sobras a contenedores de diferentes capacidades.
La figura 4 muestra en rojo el volumen de sobras que ya no cabe en el contenedor en la segunda etapa de colocación de mercancías posteriores.
Ayudará a vincular los metros cúbicos de costos para elegir un contenedor con los segundos de costos para mover los siguientes requisitos para soluciones calculadas al problema:
- Es necesario que los saldos del contenedor donante se trasladen al contenedor contenedor en cualquier caso si esto reduce el número total de contenedores que contienen el producto.
- Es necesario mantener un equilibrio entre el volumen de contenedores y el tiempo empleado en su traslado: por ejemplo, si en una nueva solución a un problema en comparación con la solución anterior, la ganancia de volumen es grande, pero la pérdida de tiempo es pequeña. , entonces es necesario elegir una nueva opción.
Comencemos con el último requisito. Para aclarar la ambigua palabra "saldo", realizamos una encuesta entre los empleados del almacén para descubrir lo siguiente. Sea una celda contenedora de volumen. , al que se le asigna el movimiento de los bienes restantes de las células del donante y el tiempo total de dicho movimiento es igual a . Que haya varias opciones alternativas para colocar la misma cantidad de productos de las mismas células del donante en otros contenedores, donde cada colocación tiene sus propias estimaciones. Donde < и Donde >.
Se plantea la pregunta: ¿cuál es la ganancia mínima de volumen? aceptable, para un valor de pérdida de tiempo determinado ? Expliquemos con un ejemplo. Inicialmente, los restos debían ser colocados en un contenedor con un volumen de 1000 dm3 (1 m3) y el tiempo de traslado fue de 70 segundos. Existe la opción de colocar los residuos en otro contenedor con un volumen de 500 dm3 y un tiempo de 130 segundos. Pregunta: ¿estamos dispuestos a dedicar 60 segundos adicionales del tiempo del tendero a mover la mercancía para ahorrar 500 dm3 de volumen libre? Con base en los resultados de una encuesta a los empleados del almacén, se compiló el siguiente diagrama.
Arroz. 5. Diagrama de la dependencia del ahorro de volumen mínimo permitido del aumento en la diferencia en el tiempo de operación.
Es decir, si los costes de tiempo adicionales son de 40 segundos, entonces estamos dispuestos a gastarlos sólo cuando la ganancia de volumen sea de al menos 500 dm3. A pesar de que existe una ligera no linealidad en la dependencia, para simplificar cálculos posteriores asumiremos que la dependencia entre las cantidades es lineal y se describe mediante la desigualdad
En la siguiente figura, consideramos los siguientes métodos para colocar mercancías en contenedores.
Arroz. 6. Opción (a): 2 contenedores, volumen total 400 dm3, tiempo total 150 seg.
Arroz. 6. Opción (b): 2 contenedores, volumen total 600 dm3, tiempo total 190 seg.
Arroz. 6. Opción (c): 1 contenedor, volumen total 400 dm3, tiempo total 200 seg.
La opción (a) para elegir contenedores es más preferible que la opción original, ya que la desigualdad se cumple: (800-400)/10>=150-120, lo que implica 40 >= 30. La opción (b) es menos preferible que la original opción, ya que la desigualdad no se cumple: (800-600)/10>=190-150 lo que implica 20 >= 40. ¡Pero la opción (c) no encaja en esa lógica! Consideremos esta opción con más detalle. Por un lado, la desigualdad (800-400)/10>=200-120, lo que significa que la desigualdad 40 >= 80 no se satisface, lo que sugiere que la ganancia en volumen no compensa una pérdida tan grande en el tiempo.
Pero, por otro lado, en esta opción (c) no sólo reducimos el volumen total ocupado, sino que también reducimos el número de celdas ocupadas, que es el primero de dos requisitos importantes para soluciones computables a los problemas enumerados anteriormente. Obviamente, para que este requisito comience a cumplirse es necesario sumar alguna constante positiva al lado izquierdo de la desigualdad , y dicha constante debe agregarse solo cuando la cantidad de contenedores disminuye. Recordemos que es una variable igual a 1 cuando el contenedor seleccionado, y 0 cuando el contenedor no seleccionado. denotemos – muchos contenedores en la solución inicial y – muchos contenedores en la nueva solución. En general, la nueva desigualdad se verá así:
Transformando la desigualdad anterior, obtenemos
En base a esto, tenemos una fórmula para calcular el costo total. alguna solución al problema:
Pero ahora surge la pregunta.: ¿Qué valor debería tener tal constante? ? Obviamente, su valor debe ser lo suficientemente grande como para que siempre se cumpla el primer requisito de solución al problema. Por supuesto, se puede tomar el valor de la constante igual a 103 o 106, pero me gustaría evitar esos "números mágicos". Si consideramos las características específicas de las operaciones de almacén, podemos calcular varias estimaciones numéricas bien fundamentadas del valor de dicha constante.
Dejar – la distancia máxima entre las celdas del almacén de una zona ABC, igual en nuestro caso a 100 m. – el volumen máximo de una celda contenedora en un almacén, equivalente en nuestro caso a 1000 dm3.
La primera forma de calcular el valor. . Consideremos una situación en la que hay 2 contenedores en el primer nivel, en los que los bienes ya están ubicados físicamente, es decir, ellos mismos son células donantes, y el costo de mover los bienes a las mismas celdas es naturalmente igual a 0. es necesario encontrar tal valor para la constante , en el que sería ventajoso mover siempre los restos del contenedor 1 al contenedor 2. Sustituyendo los valores и En la desigualdad dada arriba obtenemos:
que sigue
Sustituyendo los valores del tiempo promedio para realizar operaciones elementales en la fórmula anterior obtenemos
La segunda forma de calcular el valor. . Consideremos una situación en la que hay células donantes desde las cuales se planea mover la mercancía al contenedor 1. Denotemos – distancia de la célula donante al contenedor 1. También está el contenedor 2, que ya contiene mercancías y cuyo volumen permite acomodar el resto de todos. células. Para simplificar, asumiremos que el volumen de bienes trasladados desde las células del donante a los contenedores es el mismo e igual a . Se requiere encontrar tal valor de la constante. , en el que la colocación de todos los restos de celdas en el contenedor 2 siempre sería más rentable que colocarlas en contenedores diferentes:
Transformando la desigualdad que obtenemos
Para “fortalecer” el valor de la cantidad , supongamos que = 0. El número medio de celdas que suelen intervenir en el procedimiento de compresión de saldos de almacén es 10. Sustituyendo los valores conocidos de las cantidades, tenemos el siguiente valor de la constante
Tomamos el valor mayor calculado para cada opción, este será el valor de la cantidad para los parámetros de almacén dados. Ahora, para completar, escribamos la fórmula para calcular los costos totales. para alguna solución factible :
Ahora, después de todo esfuerzos titánicos Al transformar los datos de entrada, podemos decir que todos los datos de entrada se han convertido a la forma deseada y están listos para usarse en el algoritmo de optimización.
Conclusión
Como muestra la práctica, a menudo se subestima la complejidad y la importancia de la etapa de preparación y transformación de los datos de entrada para un algoritmo. En este artículo, prestamos mucha atención específicamente a esta etapa para mostrar que solo los datos de entrada preparados inteligentemente y de alta calidad pueden hacer que las decisiones calculadas por el algoritmo sean realmente valiosas para el cliente. Sí, hubo muchas derivaciones de fórmulas, pero te lo advertimos incluso antes del kata :)
En el próximo artículo, finalmente llegaremos al propósito de las 2 publicaciones anteriores: un algoritmo de optimización discreto.
preparó el artículo
Roman Shangin, programador del departamento de proyectos,
Compañía First Bit, Chelyabinsk
Fuente: habr.com