Cómo seleccionamos carga para transportistas

Buenas tardes. Nuestro nombre es Ilya Bashtanov (desarrollador, Tochka-Tochka ) y Tatyana Voronova (analista de datos, Centro 2M ). Y queremos hablar sobre la implementación técnica de la tarea de seleccionar mercancías para el transporte.

La esencia del problema es la siguiente. Hay mercancías en el almacén que deben transportarse de la ciudad A a la ciudad B. Podemos suponer que solo se tiene en cuenta el peso de las mercancías y que sus tamaños son más o menos estándar (euro paletas). Un transportista que quiere tomar una carga de paso quiere transportar tanto como sea posible, pero está limitado por el peso y la cantidad de paquetes. Es necesario formar para él varias variantes de los lotes a partir de los productos disponibles en el almacén.

Tareas resueltas para empresas en este caso:

1. Cargue los vehículos de la manera más eficiente posible y, por lo tanto, aumente los ingresos por transporte.
2. Resolver el problema de entrega en un tiempo aceptable para el usuario (incluido el principio FIFO).

El proyecto inmediatamente pareció atractivo. Primero, desde el punto de vista de las matemáticas: se propuso implementar un algoritmo para resolver el problema clásico de optimización combinatoria. En segundo lugar, PostgreSQL se propuso como un DBMS, cuya popularidad ha estado en constante crecimiento en los últimos años debido a una gran cantidad de características, confiabilidad y buenas características de rendimiento. Y, por supuesto, la importancia de la tarea práctica y la escala del proyecto, que involucró a muchos participantes diferentes, también se convirtió en un gran incentivo.

Algoritmo

Esta tarea es una variante del clásico problema de embalaje de la mochila . El problema de la mochila es NP-completo . Tales problemas no pueden resolverse en tiempo polinómico, aunque matemáticamente esto aún no se ha probado. Esto significa que los algoritmos exactos, como la búsqueda exhaustiva de variantes o sus variedades optimizadas, no funcionan en la práctica, ya que tienen complejidad$$$O(2^n)$. Los métodos aproximados brindan soluciones para el mejor momento. Por ejemplo, el algoritmo codicioso supone que el peso máximo se coloca en la mochila el mayor tiempo posible. Su complejidad no excede la complejidad de la clasificación.$$$(O(n * log n))$, pero el resultado puede estar lejos de ser óptimo. Todavía hay una clase de algoritmos genéticos que dan buenos resultados en un tiempo limitado, pero no son deterministas, lo que en nuestro caso daría lugar a diferentes opciones de emisión durante llamadas repetidas, sería difícil explicarlo al cliente y a los operadores. Como resultado, la elección recayó en métodos aproximados que dan el resultado con precisión garantizada en el tiempo polinómico.

Entonces tenemos:

• Pesas con pesas $$$w_1,w_2,... , w_n$
• Límite sobre el peso total de los bienes. $$$W_\max$
• Límite de carga $$$Q_\max$

Se requiere encontrar un subconjunto de productos con un peso total máximo que satisfaga las restricciones.

La idea es reducir la variedad de productos al engrosar sus pesos y aplicar el algoritmo codicioso. En este caso, la solución aproximada se encuentra en un tiempo completamente polinómico, es decir, una solución con precisión garantizada.$$$1- \varepsilon$ obtenido con complejidad siendo un polinomio en $$$n$y $$$\varepsilon$.

En la entrada del algoritmo, tenemos una placa que contiene los pesos redondeados de los productos y el número de asientos para cada peso. Usando un algoritmo codicioso, intentamos obtener opciones de estilo para los pesos totales$$$W_\max,$ $$$W_\max-1,$$$$W_\max-2,$$$$…,$$$$0$. Para hacer esto, después de establecer el peso total objetivo, en el ciclo seleccionamos la carga de peso máximo de las cargas restantes para no exceder el peso total objetivo. Si se alcanza la cantidad máxima permitida$$$Q_\max$, el ciclo termina. Las combinaciones resultantes se almacenan en una matriz temporal.

El número de combinaciones posibles puede ser grande, y es conveniente para el usuario elegir entre un pequeño número de opciones, pero al mismo tiempo aún debe haber una opción. Surge una tarea adicional de elegir las combinaciones preferidas. Para no complicarnos, decidimos ofrecer siempre dos opciones, si es posible. Para un almacén, es recomendable en primer lugar enviar las cargas más pesadas, por lo que clasificamos las combinaciones en orden descendente del mayor peso de la carga. Si las combinaciones con el peso máximo máximo son más de dos, damos dos: con la mayor y menor cantidad de bienes.

Pruebas

Para las pruebas, seleccionamos dos implementaciones del algoritmo considerado, que difieren en detalles insignificantes: uno en Java, el otro en PL / pgSQL, el lenguaje de procedimiento del DBMS PostgreSQL. Cabe señalar de inmediato que la elección final estuvo influenciada no solo por los resultados de la prueba, sino también por consideraciones arquitectónicas, usabilidad y otros factores. Pero primero, la tarea era elegir una de las dos implementaciones.

Se utilizaron dos entornos de prueba: un escritorio para probar el desarrollo y un servidor para probar en condiciones similares a las reales.

• dev: estación de cliente HP Probook 4740s + CPU de doble núcleo Pentium® de 32 bits E5300 @ 2.60GHz y 4 GB de RAM, Ubuntu Linux 16.04, PostgreSQL 10.3.
• test: 64-bit 2 x Intel Xeon CPU E5-2673 v4 @ 2.30GHz 14 , CentOS Linux 7.4, PostgreSQL 10.3

Se preparó una tabla de prueba en la base de datos PostgreSQL que contiene 7000 cargas con pesos aleatorios de 20 a 800 kg. Para las pruebas, utilizamos la utilidad estándar pgBench de PostgreSQL, que durante la prueba realizó 500 transacciones (10 conexiones de 50 transacciones cada una). Cada transacción realizó una llamada del algoritmo con parámetros aleatorios (restricción en el peso de 10 a 1000 kg y en el número de productos de 1 a 50 piezas). Todas las variables aleatorias se distribuyen de manera uniforme.

Para el primer algoritmo, cada transacción inició una máquina Java y pasó un archivo JAR con el código del algoritmo para su ejecución. La clase Java principal conectada a la base de datos a través del controlador JDBC, recibió datos de prueba de la tabla y les aplicó el algoritmo.

Para el segundo algoritmo, cada transacción realizó una llamada a la función almacenada de la base de datos PostgreSQL, que leyó los datos de prueba de la tabla y aplicó el algoritmo.

Tabla 1. Resultados de la prueba principal



Además de la prueba principal, cuyos resultados se muestran en la tabla 1, se realizó una prueba adicional del algoritmo 2, en la que se compararon diferentes opciones para obtener los datos iniciales: desde una base de datos, desde un archivo, generación aleatoria de matrices. Resultó que para 7000 cargas, la transferencia de datos desde un DBMS a una matriz local requiere más tiempo que el algoritmo de apilamiento real.

Recomendaciones.

1. En nuestra tarea, el rendimiento dependía más de la arquitectura del sistema y la velocidad de interacción con la base de datos que del algoritmo utilizado. Esto se confirma mediante una prueba adicional del algoritmo 1, en la que la selección de datos de la base de datos tomó la mayor parte del tiempo.
2. La opción 2 escala un poco mejor, aparentemente debido a requisitos de RAM más modestos (las tablas de bases de datos temporales se utilizan para almacenar resultados intermedios).

Como resultado, se eligió el segundo algoritmo, que, con pequeñas modificaciones, se utilizó para el segundo año. Como resultado, se busca una solución con una precisión aceptable con un tiempo de transacción promedio de menos de 1 segundo.

Explotación

Como siempre, la vida hizo ajustes, y tuve que modificar la implementación.

En realidad, el transportista se reserva el envío en una subasta yanqui con un precio variable. Estrictamente hablando, esta opción de vender en subasta no lo es, pero este es el tema de una conversación separada en otro sitio. Además del peso máximo de la carga y la cantidad máxima, el transportista establece dos ciudades (principio y final de la ruta) y el tiempo de carga deseado. Después de eso, el procedimiento de selección para cada par de almacenes (en las ciudades de envío y destino) filtra la carga de acuerdo con varios criterios, en particular, teniendo en cuenta las horas de trabajo del almacén y el costo máximo de transporte en el que los gastos aún están cubiertos por el pago del remitente, y transfiere sus pesos al algoritmo de apilamiento. En la salida del algoritmo, se obtiene una lista de pesos, según los conjuntos de productos específicos que se seleccionan, que se emiten como ofertas de subasta.

Inicialmente, los pesos se redondearon a valores que son múltiplos de 10 kg. Durante la operación, se hizo evidente que la precisión sufre notablemente, y los resultados comienzan a contradecir el sentido común, por ejemplo, en presencia de productos que pesan 12 y 19 kg, el sistema puede elegir el primero. Las básculas de almacén proporcionan datos con una precisión de 1 kg, y para los volúmenes y la carga actuales, el rendimiento del algoritmo para valores enteros de las básculas resultó ser bastante aceptable, por lo que se han negado al redondeo. En el futuro, con un aumento en el número de envíos, se planea utilizar el redondeo a valores que son múltiplos de 5 kg.

La sobrecarga para el funcionamiento del algoritmo de apilamiento con el volumen de datos actual y la intensidad de la consulta no es crítica. Se requieren significativamente más recursos en la etapa de selección de carga, así como para otros procesos de operación del sistema.

Hallazgos comerciales

La misión del Point-Point es un proceso logístico efectivo, en particular, el uso óptimo del vehículo en términos de congestión: al transportar un mínimo de vacíos.

Los objetivos globales de resolver problemas de optimización en el transporte de carga: el ahorro de recursos contribuye al crecimiento económico, crea oportunidades adicionales para las pequeñas y medianas empresas y mejora el medio ambiente.

Los especialistas de Center 2M y Tochka-Tochki encontraron una solución matemática de software adecuada para todos los participantes en el proceso de transporte. Se puede usar para la red federal, en cada punto de los cuales 500 operadores solicitan 7 mil paletas (correspondientes al tamaño del campo de fútbol) y el resultado se obtiene en menos de 1 segundo.

Autores del artículo: Ilya Bashtanov (i-bash), Tatyana Voronova (tvoronova)