Matemáticas discretas para WMS: algoritmo de compresión de productos en celdas (parte 1)

En este artículo, hablaremos sobre cómo resolvimos el problema de la falta de espacios libres en el almacén y sobre el desarrollo de un algoritmo de optimización discreta para abordar esta tarea. Comentaremos cómo 'construimos' el modelo matemático del problema de optimización y sobre las dificultades inesperadas que enfrentamos al procesar los datos de entrada para el algoritmo.

Si te interesan las aplicaciones de la matemática en los negocios y no temes a las rigurosas transformaciones algebraicas en el nivel de quinto grado, ¡bienvenido a leer más!

El artículo será útil para aquellos que implementan WMS-sistemas, trabajan en la industria de la logística de almacenes o producción, así como para programadores que se interesan por las aplicaciones de la matemática en los negocios y la optimización de procesos en la empresa.

Parte introductoria

Esta publicación continúa 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.

En artículo anterior se describe la especificidad del almacén en el que implementamos WMS-sistema, así como se explica por qué necesitábamos resolver el problema de clustering de lotes de productos restantes al implementar WMS-sistema, 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 sobre cómo 'construimos' el modelo matemático del problema y sobre las grandes dificultades que inesperadamente encontramos al procesar y transformar los datos de entrada para el algoritmo.
• En la segunda parte, analizaremos en detalle la implementación del algoritmo en el lenguaje C++, realizaremos un experimento computacional y resumiremos la experiencia que obtuvimos al implementar estas 'tecnologías inteligentes' en los procesos comerciales del cliente.

Cómo leer el artículo. Si has leído el artículo anterior, puedes pasar directamente al capítulo 'Revisión de soluciones existentes', si no lo has hecho, la descripción del problema a resolver está en el spoiler a continuación.

Descripción del problema a resolver en el almacén del cliente.

Cuello de botella en los procesos.

En 2018, realizamos un proyecto para implementar WMS-sistema en el almacén 'Casa Comercial LD' en Chelyabinsk. Implementamos el producto '1C-Logística: Gestión de almacenes 3' en 20 puestos de trabajo: operadores. WMS, operadores de montacargas. El almacén tiene un tamaño medio de alrededor de 4,000 m2, con 5000 ubicaciones y 4500 SKU. En el almacén se almacenan válvulas esféricas de producción propia en diferentes tamaños, desde 1 kg hasta 400 kg. Las existencias en el almacén se mantienen en lotes, ya que hay necesidad de seleccionar productos según FIFO.

Durante el diseño de los esquemas de automatización de los procesos de almacén, nos encontramos con el problema existente del almacenamiento no óptimo de las existencias. La especificidad del almacenamiento y apilamiento de las válvulas es tal que en una ubicación de almacenamiento unitario puede haber solo un tipo de lote (ver figura 1). Los productos llegan al almacén a diario y cada llegada representa un lote separado. En total, como resultado de un mes de operación del almacén, se generan 30 lotes individuales, y cada uno debe almacenarse en una ubicación separada. Los productos a menudo se seleccionan no en palets completos, sino por unidades, y como resultado, en la zona de selección de unidades, en muchas ubicaciones se observa la siguiente situación: en una ubicación de más de 1m3 hay varias válvulas que ocupan menos del 5-10% del volumen de la ubicación.

Fig. 1. Foto de varias unidades en una ubicación

Se observa un uso no óptimo de las capacidades del almacén. Para ilustrar la magnitud del problema, puedo proporcionar cifras: en promedio, hay entre 100 y 300 de estas ubicaciones de más de 1m3 con "mínimas" existencias en diferentes períodos de operación del almacén. Dado que el almacén es relativamente pequeño, durante las temporadas de carga este factor se convierte en un "cuello de botella" que ralentiza significativamente los procesos de recepción y despacho del almacén.

Idea para solucionar el problema

Surgió la idea: agrupar los lotes con las fechas más cercanas en un solo lote unificado y almacenar estos lotes con una partida estandarizada de manera compacta en una ubicación, o en varias si no hay suficiente espacio en una para almacenar toda la cantidad de existencias. Un ejemplo de esta "compresión" se ilustra en la figura 2.

Fig. 2. Esquema de compresión de existencias en las ubicaciones

Esto permite reducir significativamente el espacio de almacenamiento requerido, que será utilizado para el nuevo producto que se va a colocar. En una situación de sobrecarga de capacidad de almacenamiento, esta medida es absolutamente necesaria; de lo contrario, podría simplemente no haber espacio disponible para alojar el nuevo producto, lo que llevará a un estancamiento en los procesos de almacenamiento y suministro, y, como consecuencia, a un estancamiento en la recepción y el envío. Antes, antes de implementar el sistema WMS, esta operación se realizaba manualmente, lo cual era ineficiente, ya que el proceso de búsqueda de existencias adecuadas en las ubicaciones era bastante largo. Ahora, con la implementación del sistema WMS, hemos decidido automatizar, acelerar y hacer más inteligente el proceso.

El proceso de resolver esta tarea se divide en 2 etapas:

• en la primera etapa, encontramos grupos de partidas que son cercanas en fecha para comprimir (a esta tarea se dedica el artículo anterior);
• en la segunda etapa, calculamos para cada grupo de partidas la ubicación más compacta de las existencias en las ubicaciones.

En este artículo, nos detendremos en la segunda etapa del algoritmo.

Revisión de soluciones existentes

Antes de pasar a la descripción de los algoritmos que hemos desarrollado, es conveniente realizar una breve revisión de los sistemas que ya existen en el mercado WMS, en los que se implementa una funcionalidad similar de compresión óptima.

En primer lugar, es necesario señalar el producto "1C: Enterprise 8. WMS Logística. Gestión de Almacenes 4", que pertenece y es distribuido por la empresa 1C y se refiere a la cuarta generación WMS-de sistemas, desarrollados por la compañía AXELOT. En este sistema se declara una funcionalidad de compresión que está destinada a unificar existencias dispares de productos en una única ubicación común. Cabe mencionar que la funcionalidad de compresión en este sistema también incluye otras capacidades, como la corrección del posicionamiento de productos en las ubicaciones de acuerdo con sus clases ABC, pero no nos detendremos en ellas.

Al analizar el código del sistema «1C: Empresa 8. WMS Logística. Gestión de Almacenes 4» (que en esta parte del funcionalidad es abierto), se puede concluir lo siguiente. El algoritmo de compresión de existencias implementa una lógica lineal bastante primitiva y no se puede hablar de una compresión «óptima». Naturalmente, no prevé la agrupación de lotes. Varios clientes que han implementado este sistema se han quejado de los resultados de la planificación de compresión. Por ejemplo, a menudo, en la práctica, al comprimir, ocurría la siguiente situación: 100 unidades de existencias de un artículo se planifican para mover a otra ubicación, donde hay 1 unidad del artículo, aunque lo óptimo desde el punto de vista de los costos de tiempo sería hacer lo contrario.

La funcionalidad de compresión de existencias de productos en ubicaciones también se ha declarado en muchos sistemas extranjeros, WMSpero, desafortunadamente, no tenemos ni opiniones reales sobre la efectividad de los algoritmos (eso es un secreto comercial), ni tampoco una idea de la profundidad de su lógica (software propietario con código cerrado), por lo que no podemos juzgar.

Búsqueda de un modelo matemático del problema

Para diseñar algoritmos de calidad para resolver el problema, es necesario primero formularlo claramente desde una perspectiva matemática, lo que haremos.

Hay muchas ubicaciones , donde hay existencias de algún producto. A continuación, llamaremos a estas ubicaciones celdas donantes. Denotemos el volumen de producto que se encuentra en la ubicación $.

Es importante decir que en el procedimiento de compresión solo puede participar un producto de un lote, o varios lotes, previamente agrupados en un clúster (lee el artículo anterior), lo que se debe a la especificidad del almacenamiento y la colocación de productos. Para diferentes productos o diferentes clústeres de lotes, debe iniciarse un procedimiento de compresión separado.

Hay muchas ubicaciones , en los que potencialmente pueden colocarse las existencias de las celdas donantes. Estas celdas las llamaremos celdas contenedoras. Pueden ser tanto celdas libres en el almacén como celdas donantes de un conjunto de . Siempre un conjunto es un subconjunto de .

Para cada celda del conjunto se establecen restricciones sobre la capacidad , medidos en dm3. Un dm3 representa un cubo con lados de 10 cm. La mercancía almacenada en el almacén es bastante grande, por lo que en este caso tal discretización es suficiente.

Se ha establecido una matriz de distancias más cortas en metros entre cada par de celdas , donde y pertenecen a conjuntos y correspondientemente.

Denotemos los «costos» de mover mercancía de una celda a otra celda . Denotemos los «costos» de elegir un contenedor para mover restos de otras celdas. Cómo y en qué unidades se calcularán los valores y lo veremos más adelante (ver sección preparación de datos de entrada), por ahora es suficiente decir que tales magnitudes serán directamente proporcionales a las magnitudes y correspondientemente.

Denotemos por una variable que toma el valor 1 si los restos de la celda se trasladan al contenedor , y 0 en caso contrario. Denotemos por una variable que toma el valor 1 si el contenedor contiene restos de mercancía, y 0 en caso contrario.

El problema se plantea así: es necesario encontrar un conjunto de contenedores y de esta manera «acoplar» las celdas donantes a las celdas contenedoras, de modo que se minimice la función

sujeta a restricciones

En resumen, durante el cálculo de la solución del problema, buscamos:

• en primer lugar, ahorrar espacio de almacenamiento;
• en segundo lugar, ahorrar tiempo a los almacenistas.

La última restricción significa que no podemos mover mercancías a un contenedor que no hemos elegido, y por lo tanto no hemos «incurrido en costos» por su elección. También, esta restricción significa que el volumen de mercancías trasladadas de las celdas al contenedor no debe exceder la capacidad del contenedor. La solución del problema se entenderá como el conjunto de contenedores y las formas de acoplar las celdas donantes a los contenedores.

Esta formulación del problema de optimización no es nueva y ha sido investigada por muchos matemáticos desde principios de los años 80 del siglo pasado. En la literatura extranjera hay 2 problemas de optimización con un modelo matemático adecuado: Problema de Localización de Instalaciones Capacitado de Fuente Única y Problema de Localización de Instalaciones Capacitado de Múltiples Fuentes (hablemos más adelante sobre las diferencias de las tareas). Vale la pena mencionar que en la literatura matemática, la formulación de estas dos tareas de optimización se presenta en términos de la ubicación de instalaciones en el territorio, de ahí el nombre «Facility Location». En su mayor parte, esto es una cuestión de tradición, ya que la necesidad de resolver tales problemas combinatorios surgió por primera vez en el ámbito de la logística, mayormente en la industria militar en la década de 1950. En términos de ubicación de instalaciones, estas tareas se formulan así:

• Hay un conjunto finito de ciudades donde potencialmente se pueden ubicar instalaciones de producción (en adelante, ciudades-productoras). Para cada ciudad-productora, se han determinado los costos de apertura de una instalación en ella, así como las restricciones sobre la capacidad de producción de la instalación que se abrirá.
• Hay un conjunto finito de ciudades donde están ubicados los clientes (en adelante, ciudades-clientes). Para cada una de estas ciudades-clientes se ha establecido el volumen de demanda de productos. Para simplificar, consideraremos que el producto que producen las instalaciones y que consumen los clientes es el mismo.
• Para cada par ciudad-productora y ciudad-cliente se ha determinado el costo de transporte para entregar el volumen requerido de productos desde el productor al cliente.

Es necesario encontrar en qué ciudades abrir instalaciones y cómo asignar a los clientes a tales instalaciones, de modo que:

• Los costos totales de apertura de instalaciones y los costos de transporte sean mínimos;
• El volumen de demanda de los clientes asignados a alguna instalación abierta no supere la capacidad de producción de esta instalación.

Ahora vale la pena mencionar la única diferencia entre estas dos tareas clásicas:

• Single-Source Capacitated Facility Location Problem – el cliente es suministrado solo desde una instalación abierta;
• Multi-Source Capacitated Facility Location Problem – el cliente puede ser suministrado desde varias instalaciones abiertas simultáneamente.

Esta diferencia entre las dos tareas, a primera vista, parece insignificante, pero en realidad conduce a una estructura combinatoria completamente diferente de tales tareas y, como consecuencia, a algoritmos de solución muy distintos. La diferencia entre las tareas se ilustra en la imagen a continuación.

Fig. 3. a) Multi-Source Capacitated Facility Location Problem

Fig. 3. b) Single-Source Capacitated Facility Location Problem

Ambas tareas -dificil, es decir, no existe un algoritmo exacto que pueda resolver tal problema en tiempo polinómico respecto al tamaño de los datos de entrada. En otras palabras, todos los algoritmos exactos para resolver el problema funcionarán en tiempo exponencial, aunque pueden ser más rápidos que un agotador método de prueba y error. Dado que el problema -es complicado, solo consideraremos heurísticas aproximadas, es decir, algoritmos que calculen soluciones que sean consistentemente muy cercanas a las óptimas y que funcionen lo suficientemente rápido. Si hay interés en tales problemas, aquí se puede encontrar una buena revisión en ruso.

Si trasladamos a la terminología de nuestra tarea de compresión óptima de productos en celdas, entonces:

• las ciudades-clientes son las celdas donantes con los remanentes de productos,
• las ciudades-productoras son las celdas contenedoras , en las que se espera colocar los remanentes de otras celdas,
• los costos de transporte son el tiempo del almacenero para mover el volumen de productos desde la celda donante a la celda contenedora ;
• los costos de apertura de la empresa son los costos de selección del contenedor , que son iguales al volumen de la celda contenedora , multiplicado por un cierto coeficiente de ahorro de volúmenes libres (el valor del coeficiente siempre es > 1) (ver sección preparación de los datos de entrada).

Después de haber trazado la analogía con los conocidos problemas clásicos de suministro, es necesario responder a una pregunta importante, de la cual depende la elección de la arquitectura del algoritmo de solución: ¿es posible mover los remanentes desde la celda donante solo a un único contenedor (Single-Source), o es posible mover los remanentes a varias celdas contenedoras (Multi-Source)?

Cabe destacar que en la práctica, ambas formulaciones del problema son relevantes. A continuación, enumeraremos todos los 'pros' y 'contras' de cada una de estas formulaciones:

Tabla 1. Pros y contras de las variantes Single-Source y Multi-Source.

Dado que el número de ventajas de la variante Single-Source es mayor, y considerando también que cuanto menor es la cantidad de existencias en las celdas donadoras, menor es la diferencia en el grado de compactación de la compresión calculada para ambas variantes del problema, hemos optado por la variante Single-Source.

Cabe decir que la solución de la variante Multi-Source también es válida. Existen numerosos algoritmos efectivos para su solución, la mayoría de los cuales se reducen a resolver una serie de problemas de transporte. También hay algoritmos no solo eficaces, sino también elegantes, por ejemplo, aquí.

Preparación de los datos de entrada

Antes de comenzar el análisis y desarrollo de un algoritmo para resolver el problema, es necesario definir qué datos y en qué formato se le proporcionarán. No hay problema con los volúmenes de existencias de productos en las celdas donadoras ni con la capacidad de las celdas contenedoras, ya que esto es trivial: esas cantidades se medirán en m3. Pero los costos asociados al uso de la celda contenedora y la matriz de costos de traslado no son tan simples.

Primero consideraremos el cálculo costos de movimiento de mercancías de la celda donante a la celda contenedora. Primero, es necesario decidir en qué unidades de medida calcularemos los costos de movimiento. Las dos opciones más evidentes son metros y segundos. Contar los costos de movimiento en «metros puros» no tiene sentido. Mostremos esto con un ejemplo. Supongamos que la celda está ubicada en el primer nivel, la celda se encuentra a 30 metros y está en el segundo nivel:

• Mover desde en es más costoso que mover desde en , ya que bajar desde el segundo nivel (1.5-2 metros del suelo) es más fácil que subir al segundo, aunque la distancia recorrida será la misma;
• Mover 1 unidad de mercancía de la celda en será más fácil que mover 10 unidades de la misma mercancía, aunque la distancia será la misma.

Los costos de movimiento se deben considerar mejor en segundos, ya que esto permite tener en cuenta tanto la diferencia en los niveles como la diferencia en la cantidad de mercancía movida. Para contabilizar los costos de movimiento en segundos, debemos descomponer la operación de movimiento en componentes elementales y medir el tiempo para realizar cada componente elemental.

Supongamos que desde la celda se mueven unidades de mercancía al contenedor . Supongamos que es la velocidad promedio de un trabajador en el almacén, medida en m/s. Supongamos que y son las velocidades promedio para realizar operaciones de tomar y colocar respectivamente para un volumen de mercancía de 4 dm3 (el volumen promedio que un empleado toma en una vez al realizar operaciones en el almacén). Supongamos que y son las alturas de las celdas desde las cuales se realizan las operaciones de tomar y colocar respectivamente. Por ejemplo, la altura promedio del primer nivel (suelo) es 1 m, el segundo nivel es 2 m, etc. Entonces, la fórmula para calcular el tiempo total para realizar la operación de movimiento es la siguiente:

La tabla 2 muestra las estadísticas del tiempo de ejecución de cada operación elemental, recopiladas por los empleados del almacén teniendo en cuenta la especificidad de la mercancía almacenada.

Nombre de la operación	Designación	Valor promedio
Velocidad promedio de movimiento del trabajador en el almacén		1.5 m/s
Velocidad promedio para realizar una operación de colocar (para un volumen de mercancía de 4 dm3)		2.4 s

Tabla 2. Tiempo promedio de ejecución de operaciones en el almacén

Hemos definido el método de cálculo de los costos de movimiento. Ahora es necesario averiguar cómo calcular los costos de selección de la celda contenedoraAquí todo es mucho, mucho más complejo que con los costos de traslado, ya que:

• en primer lugar, los costos deben depender directamente del volumen de la celda; el mismo volumen de existencias trasladadas desde las celdas donantes es mejor colocar en un contenedor de menor volumen que en uno grande, siempre que dicho volumen quepa completamente en ambos contenedores. Así, minimizando los costos totales de selección de contenedores, buscamos ahorrar en capacidades de almacenamiento 'deficitarias' en la zona de selección, para llevar a cabo las operaciones posteriores de colocación de productos en las celdas. En la figura 4 se muestran las opciones para mover existencias a contenedores grandes y pequeños y las consecuencias de tales opciones de movimiento al ejecutar las operaciones de almacén posteriores.
• en segundo lugar, dado que en la solución del problema inicial necesitamos minimizar los costos totales, que son la suma de los costos de traslado y los costos de selección de contenedores, los volúmenes de las celdas en metros cúbicos deben de alguna manera relacionarse con los segundos, lo cual no es nada trivial.

Fig. 4. Opciones para mover existencias a contenedores de diferente capacidad.

En la figura 4, en color rojo, se representa el volumen de existencias que ya no cabe en el contenedor en la segunda etapa de colocación de productos posteriores.

Ayudarán a relacionar los metros cúbicos de costos de selección de contenedores con los segundos de costos de traslado los siguientes requisitos para las soluciones calculadas del problema:

• Es necesario que las existencias de la celda donante se trasladen a la celda contenedor en cualquier caso si esto reduce el número total de celdas contenedoras en las que se encuentra el producto.
• Es necesario mantener un equilibrio entre los volúmenes de los contenedores y los costos de tiempo de traslado: por ejemplo, si en la nueva opción de solución del problema, en comparación con la opción anterior, hay una ganancia significativa en volumen, pero una pérdida pequeña en costos de tiempo, entonces se debe elegir la nueva opción.

Comencemos con el último requisito. Para concretar la polisemia de la palabra 'equilibrio', llevamos a cabo una encuesta entre el personal del almacén con el fin de averiguar lo siguiente. Supongamos que hay una celda contenedor de volumen , a la que se ha asignado el traslado de existencias de productos desde celdas donantes y el tiempo total de dicho traslado es igual a . Supongamos que hay varias opciones alternativas para ubicar la misma cantidad de mercancía de las mismas celdas donantes en otros contenedores, donde cada ubicación tiene sus propias evaluaciones. , donde < y , donde >.

Surge la pregunta: ¿cuánto es el mínimo beneficio en volumen aceptable, dado un determinado valor de pérdida de tiempo? ? Поясним на примере. Изначально остатки полагалось размещать в контейнер объема 1000 дм3 (1 м3) и время на перемещение составило 70 секунд. Есть вариант размещения остатков в другой контейнер объема 500 дм3 и временем 130 секунд. Вопрос: готовы ли мы тратить еще дополнительные 60 секунд времени кладовщика на выполнение перемещения для того, чтобы сэкономить 500 дм3 свободного объема? По результатам опроса сотрудников склада была составлена следующая диаграмма.

Fig. 5. Diagrama de la relación entre el ahorro mínimo de volumen permitido y el aumento de la diferencia en el tiempo de ejecución de la operación.

Es decir, si el costo adicional en tiempo es de 40 segundos, solo estamos dispuestos a gastarlo cuando el ahorro en volumen sea de al menos 500 dm3. A pesar de que la relación muestra una pequeña no linealidad, para simplificar los cálculos posteriores, asumiremos que la relación entre las cantidades es lineal y se describe mediante una desigualdad.

En la figura a continuación, consideraremos las siguientes maneras de ubicar la mercancía en los contenedores.

Fig. 6. Opción (a): 2 contenedores, volumen total 400 dm3, tiempo total 150 seg.

Fig. 6. Opción (b): 2 contenedores, volumen total 600 dm3, tiempo total 190 seg.

Fig. 6. Opción (c): 1 contenedor, volumen total 400 dm3, tiempo total 200 seg.

La opción (a) de selección de contenedores es más preferible que la opción inicial, dado que se cumple la desigualdad: (800-400)/10 >= 150-120, de lo cual se deduce que 40 >= 30. La opción (b) es menos preferible que la opción inicial, ya que la desigualdad no se cumple: (800-600)/10 >= 190-150, de lo cual se deduce que 20 >= 40. Sin embargo, la opción (c) no se ajusta a tal lógica. Veamos esta opción con más detalle. Por un lado, la desigualdad (800-400)/10 >= 200-120 no se cumple, lo que indica que el ahorro de volumen no justifica tal gran pérdida de tiempo.

Pero por otro lado, en tal opción (c) no solo estamos reduciendo el volumen total ocupado, sino también disminuyendo la cantidad de celdas ocupadas, lo cual es el primero de dos requisitos importantes para las soluciones de las tareas mencionadas anteriormente. Es obvio que, para que se comience a cumplir este requisito, es necesario añadir una constante positiva en el lado izquierdo de la desigualdad. , además, esta constante debe añadirse solo cuando se reduce la cantidad de contenedores. Recordemos que — es una variable que es igual a 1 cuando se selecciona un contenedor, y 0 cuando no se selecciona. выбран, и 0 когда контейнер no seleccionado. Definimos, – múltiples contenedores en la solución original y – múltiples contenedores en la nueva solución. En términos generales, la nueva desigualdad se verá así:

Transformando la desigualdad anterior, obtenemos

A partir de esto, tenemos una fórmula para calcular el costo total de alguna variante de la solución del problema:

Pero ahora surge la pregunta: ¿qué valor debe tener tal constante? ? Очевидно, что ее значение должно быть достаточно большим, для того, чтобы всегда выполнялось первое требование к решениям задачи. Можно конечно взять значение константы равное 103 или 106, но хотелось бы избежать таких «magic numbers». Если будем рассматривать специфику выполнения складских операций, мы можем вычислить несколько вполне обоснованных числовых оценок величины такой константы.

Sea – la distancia máxima entre las celdas del almacén de una zona ABC, que es de 100 m en nuestro caso. Sea – el volumen máximo de la celda-contenedor en el almacén, que es de 1000 dm3 en nuestro caso.

El primer método para calcular el tamaño . Consideremos la situación en la que hay 2 contenedores en la primera capa, en los que ya hay físicamente mercancía, es decir, ellos mismos son celdas donantes, y los costos de mover la mercancía a esas mismas celdas son, por supuesto, 0. Es necesario encontrar un valor para la constante , para el cual sería ventajoso siempre trasladar los residuos del contenedor 1 al contenedor 2. Sustituyendo los valores y en la desigualdad mencionada anteriormente, obtenemos:

de lo que se sigue

Sustituyendo los valores del tiempo medio para realizar operaciones elementales en la fórmula anterior obtenemos

El segundo método para calcular el tamaño . Consideremos la situación en la que hay celdas donantes desde las cuales se planea trasladar mercancía al contenedor 1. Denotemos – la distancia desde la celda donante hasta el contenedor 1. También hay un contenedor 2, en el que ya hay mercancías, y cuyo volumen permite contener los restos de todas las celdas. Para simplificar, supongamos que el volumen de la mercancía que se traslada de las celdas donantes a los contenedores es igual a . Se requiere encontrar un valor para la constante , para el cual colocar todos los restos de las celdas en el contenedor 2 siempre sería más ventajoso que colocarlos en diferentes contenedores:

Transformando la desigualdad, obtenemos

Para "reforzar" el valor de la cantidad , asumiremos que = 0. El número medio de celdas que normalmente participan en el procedimiento de compactación de residuos en el almacén es de 10. Sustituyendo los valores conocidos, tenemos el siguiente valor para la constante

Tomamos el mayor valor calculado para cada variante, este será el valor de la cantidad para los parámetros dados del almacén. Ahora, para completar, escribamos la fórmula para el cálculo de los costos totales para alguna solución aceptable :

Ahora, después de todos los titánicos esfuerzos para transformar los datos de entrada, podemos decir que todos los datos de entrada han sido transformados a la forma necesaria y están listos para su uso en el algoritmo de optimización.

Conclusión

Como muestra la práctica, la complejidad y la importancia de la etapa de preparación y transformación de los datos de entrada para el algoritmo a menudo se subestiman. En este artículo, hemos dedicado mucho tiempo a esta etapa para demostrar que solo los datos de entrada preparados de manera cualitativa e inteligente pueden hacer que las decisiones calculadas por el algoritmo sean realmente valiosas para el cliente. Sí, hubo muchas formulaciones de conclusiones, pero ya lo advertimos antes del corte 🙂

En el próximo artículo, finalmente llegaremos a lo que motivó las 2 publicaciones anteriores: al algoritmo de optimización discreta.

El artículo fue preparado por
Roman Shanguin, programador del departamento de proyectos,
compañía Primer Bit, ciudad de Cheliábinsk

Fuente: habr.com