Logística fácil de fazer você mesmo

Quero compartilhar com você a experiência de criar um sistema de logística em uma empresa comercial.

Em um belo dia, no próximo ano de 2012, o chefe estabeleceu a tarefa: pensar no problema de otimizar os custos de logística de transporte da organização.
O principal campo de atividade da empresa é o atacado e a entrega de produtos, onde os custos de transporte ocupam uma parcela significativa dos custos.

A gerência considerou que havia chegado a hora de colocar as coisas em ordem para gastar dinheiro em combustível, e também havia suspeitas de que os motoristas estavam envolvidos adicionalmente na entrega "à esquerda" entre os vôos. Nas pequenas e médias empresas, muito se baseia na confiança, uma vez que manter os indivíduos sob controle não é lucrativo e nem sempre aconselhável. Quando os custos aumentam e a eficiência cai, você só precisa fazer alguma coisa.

Para começar, tentamos resolver o problema por métodos de gerenciamento: medição contínua do nível de combustível, leituras do tacômetro, medição do tempo de entrega com acompanhamento pessoal da carga. O efeito foi sobre nada além de negatividade, suspeita e movimentos desnecessários (medir isso também é um trabalho para alguém). Se ainda era possível determinar um escopo aproximado com uma única rota, então, com um vôo de 25 a 35 instalações de varejo, tudo mudou muito, o spread foi muito grande, tanto a tempo quanto em combustível.

Objetivo: enviar veículos ocupados às empresas comerciais, reduzindo a quilometragem e, portanto, os custos. Se possível, evite o desvio da rota. O objetivo é reduzir custos com um investimento mínimo em finanças e tempo de implementação, por assim dizer ontem. Durante as discussões, eles concordaram em várias alternativas:

1. use um dos serviços para calcular rotas e contabilizar combustíveis e lubrificantes;
2. colocar nos módulos de rastreamento / rastreamento de frotas;
3. projetar algo você mesmo;

Decidimos tentar as três soluções e escolher a melhor:

1. Naquela época, não encontramos uma boa solução turnkey. Seja um projeto chave na mão, mas caro, ou leve-o como está e além disso, mediante acordo. Já tentou vários serviços online. No geral, não é ruim, mas basicamente a dificuldade era duplicar as informações do sistema contábil, o número de ações para obter o resultado (clique aqui, vá aqui, atualize o diretório), tudo está online (na época, era crítico). Mas a maior desvantagem é a dificuldade de criar rotas com muitos pontos e escolher a melhor rota. Geralmente, tudo tinha que ser selecionado manualmente, ajustando os valores, que eram longos e nem sempre bem-sucedidos como resultado.

Depois de alguns meses de trabalho, eles recusaram essa decisão.

2. Como um experimento, eles instalaram módulos de rastreamento GSM em uma dúzia de carros.
O resultado é mais bem sucedido. Você sempre sabe onde estava o carro. Mas o custo é mais caro que a primeira opção. No entanto, depois de identificar alguns casos de desvio da rota (um shabbat de motorista, o segundo visitou a dama do coração, durante o horário de trabalho), os funcionários começaram a se livrar desses dispositivos intensivamente. Embora eles não tivessem aceitado com entusiasmo essa inovação antes. O terminal de energia piscou acidentalmente ou quando o motor estava sendo reparado, o dispositivo falhou ou os componentes eletrônicos "superaqueceram" ao sol. Então, por três anos, perdemos 9 dispositivos. Em geral, a decisão acabou sendo positiva, mas dos pontos negativos - eu tive que examinar as rotas percorridas por um longo tempo para identificar atividades suspeitas, o que não é muito conveniente. Uma vantagem no sistema de rastreamento foi o item de exportação da pista, que permitiu acumular certas estatísticas nas rotas.

Posteriormente, usamos outro sistema de uma das principais operadoras móveis para comunicações corporativas e rastreamos a atividade dos agentes de vendas, o resultado foi semelhante: cartões SIM foram quebrados, telefones foram perdidos, eles foram esquecidos em casa, a bateria estava esgotada, as pessoas sempre encontravam uma saída.

3. Paralelamente às duas primeiras abordagens, decidimos inventar uma bicicleta , para perceber em nosso sistema contábil a capacidade de construir rotas por nós mesmos.

Primeiro, trouxemos todos os locais de visita e inserimos suas coordenadas geográficas no banco de dados. Obtivemos as coordenadas de acordo com o rastreador GPS durante a visita, bem como visualmente nos mapas OSM , encontrando o lugar certo com o mouse e copiando as coordenadas.

Na segunda etapa, foi necessário obter mapas vetoriais da região em um formato conveniente.
A escolha recaiu no mesmo OSM, pois os cartões têm um formato aberto. Como não dominamos o despejo do planeta, inicialmente carregamos os dados em pedaços em XML, exportando a partir do próprio OSM e conectando os territórios. Mais tarde, deparei com um projeto GIS-LAB . Essas pessoas dignas, durante muitos anos, fizeram um despejo diário de territórios, discriminados por região. Mas todo mundo quer comer, o projeto recentemente parou e os caras mudaram , e eles estão fazendo o mesmo trabalho por um preço razoável.

Tendo recebido o mapa em formato XML, extraímos a camada responsável pelas estradas de acordo com a especificação . Como o volume de cartões de várias regiões vizinhas ocupava dez gigabytes, o analisador SAX foi escrito em RUBY, ele selecionou apenas as tags necessárias e mesclou as regiões vizinhas nas quais as atividades eram realizadas em uma única estrutura.

O projeto em si é escrito como uma DLL externa para o sistema de contabilidade escrito em Pascal. A frota de dispositivos nos quais o sistema deveria funcionar era, para dizer o mínimo, obsoleta, então havia um limite de 1 GB de RAM (Sim, também existem empresas que usam essa técnica, trabalham há 10 anos e trabalham na mesma quantidade). Inicialmente, havia um desejo de quebrar o cartão em pedaços e carregá-lo na RAM, conforme necessário (como nos navegadores), mas era extremamente lento. Como resultado, conseguimos compor até cinquenta MB razoáveis.

No OSM, os mapas de estradas são representados como seções vetoriais da estrada com atributos adicionais. Em nossa decisão, usamos listas de adjacência . Onde o pico é um ponto no mapa e as bordas são os caminhos para um ponto vizinho. Para otimização, acreditamos que pode haver no máximo quatro caminhos (interseção) de um vértice. Se houver mais de 4 caminhos, você precisará dividir a aresta em duas adicionais, para que sempre tenhamos um número fixo de arestas = 4 para cada ponto do mapa.Esta abordagem nos permite alinhar os dados na memória, embora isso seja um pouco redundante.

Vale a pena notar que a Terra não é uma bola (inesperadamente), mas um geóide , mas, para fins de cartografia, é simplificada para um esferóide ou elipsóide .

Para nossos propósitos, encontrei uma fórmula para calcular as distâncias entre dois pontos na superfície de um elipsóide, da qual eu não conseguia entender o significado mais profundo, mas isso não nos impede de usá-lo.


Depois de criar a base da estrada, era necessária uma camada visual para exibir a área circundante. O projeto maperitive ajudou aqui , nos permitiu analisar o mapa OSM de regiões em seções de blocos por camadas de aproximação, assim como 10 ^ 100 ou Yandex. Houve uma tentativa de trabalhar com os mapas de gigantes on-line, renderizando um mapa vetorial na parte superior da camada do navegador, mas, devido a restrições de licenciamento, eles decidiram recusar. Como resultado, criamos um disco virtual e carregamos um despejo de blocos para algumas dezenas de gigabytes, mas tudo o que está à mão não diminui. É verdade que uma vez a cada seis meses você precisa atualizar, geralmente isso coincide com a sobrecarga de cartões.



Para combinar a imagem do bloco e o mapa do vetor, você precisa saber que os blocos, Google, OpenStreetMap, Bing e Yahoo estão representados na projeção Mercator (mais precisamente WEB MERCATOR , que é a projeção na esfera), onde cada camada mais profunda é duas vezes mais detalhada que a anterior.



Os Yandex.Maps usam a projeção do elipsóide Mercator.

Não importa se você pode recalcular as coordenadas geográficas no plano de projeção e vice-versa.

Selecionamos o nível 17 de detalhes como o máximo. O Closer não faz sentido devido a um aumento no armazenamento do número de blocos (cada nível é 4 vezes maior que o anterior), além do baixo conteúdo de informações.

2 ^ 17 * 256 = 33554432 (256 é o tamanho da borda do bloco em pixels).


Agora que temos as ferramentas básicas, podemos prosseguir diretamente para a tarefa de criar a rota ideal. Conectamos os estabelecimentos comerciais à margem mais próxima no gráfico de estradas e, em seguida, iniciamos a busca pelo caminho mais curto. Para fazer isso, usamos uma variação do algoritmo de Dijkstra para sua variação descarregada sequencialmente para cada ponto de visita. Na saída, obtemos uma matriz de adjacência de tamanho (N + 1) * (N + 1) com infinito na diagonal principal (proibição de toque), onde N é o número de pontos de visita sem levar em consideração o ponto de saída.

A matriz resultante armazena a distância mínima ao longo das estradas entre todos os estabelecimentos comerciais, o que é um problema clássico dos vendedores ambulantes . Como a complexidade algorítmica de um problema está exagerada, usamos o método branch e bound para resolvê-lo. Para n <15, é exaustivo; caso contrário, uma estimativa aproximada é conectada em profundidade. A opção certamente não é ideal, mas funciona bastante.

Como resultado, conseguimos uma rota próxima da distância ideal com uma estimativa em km. Se necessário, o operador pode alterar manualmente a rota em favor da prioridade de pontos individuais.

A solução trabalha na organização há cerca de 7 anos, com bastante sucesso, embora não sem falhas, tanto em precisão quanto em conveniência. Os resultados são consistentes com os dados de rastreamento de veículos GPS. Na minha opinião, a introdução da logística permitiu economizar 10 a 12% dos fundos alocados para combustível. O programa foi projetado, lançado e acompanhado por apenas uma pessoa - seu humilde servo.

Minha liderança conservadora não está ansiosa para "brilhar", por isso sugiro um exemplo fictício do caminho da atenção.



Sem visualização, o cálculo é muitas vezes mais rápido e dentro de um assentamento, quase que instantaneamente.

Depois de tantos anos, às vezes, as pessoas ficam ansiosas para entrar no código e copiá-lo com nova experiência para uma plataforma nova e mais moderna, mas até agora não há viabilidade econômica.

Era tudo o que queria lhe contar, espero que tenha sido interessante.
Peço desculpas se não for preciso em algum lugar.