Como selecionamos carga para transportadoras

Boa tarde. Nosso nome é Ilya Bashtanov (desenvolvedor, Tochka-Tochka ) e Tatyana Voronova (analista de dados, 2M Center ). E queremos falar sobre a implementação técnica da tarefa de selecionar mercadorias para o transporte.

A essência do problema é a seguinte. Existem mercadorias no armazém que precisam ser transportadas da cidade A para a cidade B. Podemos supor que apenas o peso da mercadoria seja levado em consideração e que seus tamanhos sejam mais ou menos padrão (paletes de euro). Uma transportadora que deseja levar uma carga de passagem deseja transportar o máximo possível, mas é limitada pelo peso e número de pacotes. É necessário formar para ele várias variantes dos lotes das mercadorias disponíveis no armazém.

Tarefas resolvidas para os negócios neste caso:

1. Carregue os veículos da maneira mais eficiente possível e, assim, aumente a receita do transporte.
2. Resolver o problema de entrega em um tempo aceitável para o usuário (incluindo o princípio FIFO).

O projeto imediatamente pareceu atraente. Primeiro, do ponto de vista da matemática: foi proposto implementar um algoritmo para resolver o problema clássico de otimização combinatória. Em segundo lugar, o PostgreSQL foi proposto como um DBMS, cuja popularidade tem crescido constantemente nos últimos anos devido a um grande número de recursos, confiabilidade e boas características de desempenho. E, é claro, a importância da tarefa prática e a escala do projeto, que envolveu muitos participantes diferentes, também se tornaram um grande incentivo.

Algoritmo

Essa tarefa é uma variante do problema clássico de embalagem de mochila . O problema da mochila é NP-completo . Tais problemas não podem ser resolvidos no tempo polinomial, embora matematicamente isso ainda não tenha sido comprovado. Isso significa que algoritmos exatos, como busca exaustiva de variantes ou suas variedades otimizadas, não funcionam na prática, pois possuem complexidade$$$O(2^n)$. Métodos aproximados fornecem soluções para o melhor momento. Por exemplo, o algoritmo guloso assume que o peso máximo é colocado na mochila o maior tempo possível. Sua complexidade não excede a complexidade da classificação$$$(O(n * log n))$, mas o resultado pode estar longe de ser o ideal. Ainda existe uma classe de algoritmos genéticos que fornecem bons resultados em um tempo limitado, mas eles não são determinísticos, o que, no nosso caso, levaria a diferentes opções de emissão durante chamadas repetidas, seria difícil de explicar ao cliente e às operadoras. Como resultado, a escolha recaiu sobre métodos aproximados que fornecem o resultado com precisão garantida em tempo polinomial.

Então nós temos:

• Pesos com pesos $$$w_1,w_2,... , w_n$
• Limite do peso total das mercadorias $$$W_\max$
• Limite de carga $$$Q_\max$

É necessário encontrar um subconjunto de mercadorias com um peso total máximo que satisfaça as restrições.

A idéia é reduzir a variedade de mercadorias, aumentando o peso e aplicando o algoritmo ganancioso. Nesse caso, a solução aproximada é encontrada em um tempo completamente polinomial, ou seja, uma solução com precisão garantida$$$1- \varepsilon$ obtido com a complexidade sendo um polinômio em $$$n$e $$$\varepsilon$.

Na entrada do algoritmo, temos uma placa contendo os pesos arredondados das mercadorias e o número de assentos para cada peso. Usando um algoritmo guloso, tentamos obter opções de estilo para os pesos totais$$$W_\max,$ $$$W_\max-1,$$$$W_\max-2,$$$$…,$$$$0$. Para isso, após definir o peso total desejado, no ciclo, selecionamos o peso máximo da carga das cargas restantes para não exceder o peso total desejado. Se o valor máximo permitido for atingido$$$Q_\max$, o ciclo termina. As combinações resultantes são armazenadas em uma matriz temporária.

O número de combinações possíveis pode ser grande e é conveniente para o usuário escolher entre um pequeno número de opções, mas ao mesmo tempo ainda deve haver uma opção. Surge uma tarefa adicional de escolher combinações preferidas. Para não complicar, decidimos sempre oferecer duas opções, se possível. Para um armazém, é aconselhável, antes de tudo, enviar as cargas mais pesadas, por isso classificamos as combinações em ordem decrescente do maior peso da carga. Se as combinações com o peso máximo máximo forem superiores a dois, forneceremos dois: com a maior e a menor quantidade de mercadorias.

Testes

Para o teste, selecionamos duas implementações do algoritmo considerado, que diferem em detalhes insignificantes: um em Java e outro no PL / pgSQL, a linguagem processual do DBMS do PostgreSQL. Deve-se notar imediatamente que a escolha final foi influenciada não apenas pelos resultados dos testes, mas também por considerações arquitetônicas, usabilidade e outros fatores. Mas, primeiro, a tarefa era escolher uma das duas implementações.

Foram utilizados dois ambientes de teste: um desktop para testar o desenvolvimento e um servidor para testar em condições semelhantes às reais.

• dev: estação cliente HP Probook 4740s + CPU Pentium® de dois núcleos 2 x E5300 a 2,60GHz e 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

Uma tabela de teste foi preparada no banco de dados PostgreSQL contendo 7000 cargas com pesos aleatórios de 20 a 800 kg. Para o teste, usamos o utilitário pgBench padrão do PostgreSQL, que durante o teste executou 500 transações (10 conexões de 50 transações cada). Cada transação fazia uma chamada do algoritmo com parâmetros aleatórios (restrição de peso de 10 a 1000 kg e número de mercadorias de 1 a 50 peças). Todas as variáveis ​​aleatórias são distribuídas uniformemente.

Para o primeiro algoritmo, cada transação iniciou uma máquina Java e passou um arquivo JAR com o código do algoritmo para execução. A principal classe Java conectada ao banco de dados por meio do driver JDBC, recebeu dados de teste da tabela e aplicou o algoritmo a eles.

Para o segundo algoritmo, cada transação fez uma chamada para a função armazenada do banco de dados PostgreSQL, que leu os dados de teste da tabela e aplicou o algoritmo.

Tabela 1. Resultados do teste principal



Além do teste principal, cujos resultados são mostrados na tabela 1, foi realizado um teste adicional do algoritmo 2, no qual foram comparadas diferentes opções para obter os dados iniciais: de um banco de dados, de um arquivo, geração aleatória de array. Descobriu-se que, para 7000 cargas, a transferência de dados de um DBMS para uma matriz local requer mais tempo do que o algoritmo de empilhamento real.

Constatações.

1. Em nossa tarefa, o desempenho dependia mais da arquitetura do sistema e da velocidade de interação com o banco de dados do que do algoritmo usado. Isso é confirmado por um teste adicional do algoritmo 1, no qual a seleção de dados do banco de dados demorava a maior parte do tempo.
2. A opção 2 é um pouco melhor, aparentemente devido a requisitos de RAM mais modestos (tabelas temporárias de banco de dados são usadas para armazenar resultados intermediários).

Como resultado, foi escolhido o segundo algoritmo, que, com pequenas alterações, foi utilizado pelo segundo ano. Como resultado, é procurada uma solução com precisão aceitável, com um tempo médio de transação inferior a 1 segundo.

Exploração

Como sempre, a vida fez ajustes e eu tive que ajustar a implementação.

Na realidade, a transportadora reserva a remessa em um leilão ianque com um preço flutuante. A rigor, essa opção de venda em leilão não é, mas esse é o tópico de uma conversa em outro site. Além do peso máximo da carga e da quantidade máxima, a transportadora define duas cidades (início e fim do percurso) e o tempo de carregamento desejado. Depois disso, o procedimento de seleção para cada par de armazéns (na cidade de partida e de destino) filtra as cargas de acordo com vários critérios, em particular, levando em consideração o horário de trabalho do armazém e o custo máximo de transporte, em que os custos ainda são cobertos pelo pagamento do remetente e transfere seus pesos para o algoritmo de empilhamento. Na saída do algoritmo, é obtida uma lista de pesos, de acordo com quais conjuntos de mercadorias específicas são selecionados, que são emitidos como ofertas de leilão.

Inicialmente, os pesos foram arredondados para valores múltiplos de 10 kg. Durante a operação, ficou claro que a precisão sofre visivelmente e os resultados começam a contradizer o senso comum, por exemplo, na presença de mercadorias com peso entre 12 e 19 kg, o sistema pode escolher o primeiro. As balanças de armazém fornecem dados com precisão de 1 kg e, para os volumes e cargas atuais, o desempenho do algoritmo para valores inteiros das balanças mostrou-se bastante aceitável; portanto, eles recusaram o arredondamento. No futuro, com um aumento no número de remessas, está planejado usar arredondamentos para valores múltiplos de 5 kg.

A sobrecarga para a operação do algoritmo de empilhamento com o volume de dados atual e a intensidade da consulta não é crítica. Significativamente mais recursos são necessários no estágio de seleção de carga, bem como para outros processos de operação do sistema.

Resultados de negócios

A missão do Point-Point é um processo logístico eficaz, em particular o uso ideal do veículo em termos de congestionamento: ao transportar um mínimo de vazios.

Os objetivos globais de resolver problemas de otimização no transporte de mercadorias: economizar recursos contribui para o crescimento econômico, cria oportunidades adicionais para pequenas e médias empresas e melhora o meio ambiente.

Os especialistas do Center 2M e Tochka-Tochki encontraram uma solução matemática de software adequada para todos os participantes no processo de transporte. Pode ser utilizado na rede federal, em cada ponto dos quais 7 mil paletes (correspondentes ao tamanho do campo de futebol) são solicitados por 500 transportadoras e com o resultado obtido em menos de 1 segundo.

Autores do artigo: Ilya Bashtanov (i-bash), Tatyana Voronova (tvoronova)