Fazendo a ponte entre TI crescentes demandas de negócios e ferramentas de envelhecimento
O que a heurística, teoria dos grafos e donuts temos em comum? Cada um deles, à sua maneira, está subjacente a uma das partes mais difíceis do processo de logística: planejamento de rotas de entrega.
Todos os dias, milhões de produtos encontram seu caminho de fabricantes para os distribuidores, varejistas e, finalmente, para residências e empresas em todos os lugares.
Certificando-se esses produtos chegar a tempo é uma tarefa gigantesca que tem suas raízes em um enigma matemático de 1800: o problema do caixeiro viajando.
Em sua forma mais simples, o problema assume um vendedor hipotético encarregado de visitar um certo número de lugares em um dia. Como pode o vendedor visitar todos os lugares através do caminho mais curto?
Este problema é um produto da teoria dos grafos - o estudo de nós e linhas -, e é o tipo perfeito da matemática para as redes de logística. Afinal, estes são efetivamente coleções da mesma coisa.
"Se você pensar no que a cadeia de abastecimento parece, você desenhar círculos em papel e rotulá-los", diz Jeff Karrenbauer, presidente e diretor de criação da Insight, que é especializada em soluções de planejamento de logística e operações da cadeia de suprimentos.
"Você desenha linhas entre eles que representam ligações de transporte."
O problema do caixeiro viajar pode ser um divertido quebra-cabeça para resolver em casa com cerca de seis nós. Mas para as empresas de logística que lidam com milhares de círculos e linhas, é muito mais desafiador.
O problema reside no fato de que, como você adicionar lugares para visitar, o número de combinações possíveis aumenta exponencialmente. E a razão para isso encontra-se com o planejador de rotas logística nemesis: o fatorial.
Números estonteantes
O factorial de um número, n, é o produto de todos os números inteiros positivos, igual ou inferior do que a própria, e é denotado como o n! . O factorial de 4 (4!), Por exemplo, é de 4 x 3 x 2 x 1 (24).
É assim que muitas combinações que você teria para um caixeiro-viajante, com quatro lugares para visitar. 5! É 120. 6! É 720.
Agora, pense em um único driver fazendo 25 paradas em um dia. Isso fornece 1.551121 para o poder de 25 (1.551121 ^ 25) combinações diferentes.
Tendo em conta que há cerca de 1 ^ 25 estrelas no universo visível, do condutor entrega média iria ganhar um monte de horas extras a fazer isso no papel - e provavelmente teria de pular café da manhã.
"É uma situação muito especial, porque uma vez que você tenha decidido que cada nó será visitada uma vez, cada nó possui exatamente um predecessor e cada nó tem um sucessor. É o que é chamado de um problema de otimização combinatória ", diz Jim Encadernador, diretor de Gestão da grupo de pesquisa Sistemas Integrados de Manufatura da Universidade de Waterloo no Canadá.
Na vida real, a coisa toda se torna intratável muito antes de você chegar a 25 paradas, explica Danny Bausch, diretor de análise e gerenciamento de produtos da Insight.
"Esse problema não rende bem para otimização. Depois de conseguir acima de cerca de nove locais de parada, o número de combinações explode exponencialmente e rotinas de otimização derreter ", diz ele.
Para aliviar a carga, especialistas em logística deve tentar trazer outro tipo de matemática: análise heurística. Esta é uma maneira de encontrar soluções aproximadas de problemas matemáticos, quando não são simplesmente demasiado muitos insumos potenciais para lidar.
"Em algum momento o cérebro diz que há muitas coisas acontecendo"
Nós encontramos-los em aplicações de computação populares antes, tais como software de anti-vírus, por exemplo, onde muitos arquivos devem ser verificadas de forma rápida, muitas vezes em tempo real, para procurar por bugs maliciosos.
"Em algum momento o cérebro afirma que há muitas coisas acontecendo por isso vou seguir algumas regras de ouro", diz Bausch.
Por exemplo, 25 paradas diferentes podem ser muito difíceis de analisar usando a tecnologia de computação disponível. Mas você pode ser capaz de simplesmente olhar para o mapa de onde as gotas devem ser feitas e dividi-los em mais facilmente gerenciável pedaços, por exemplo para o norte, sul, leste e oeste quadrantes. Cada um desses poderia ser então submetido à sua própria análise do caixeiro viajante.
Afinal de contas, é pouco provável que um motorista iria querer ir directamente a partir do ponto mais ao sul em uma rota diária para o ponto mais setentrional, de modo que é uma das muitas combinações que não faria sentido para calcular.
"Essa é uma heurística manual. Essas regras podem ser colocados juntos como isso ", diz Bausch. "Eles são uma série de passos que o computador compreende bem."
Há um punhado de heurísticas comumente usados quando se trata de problemas matemáticos deste tipo. Um deles é o algoritmo de varredura, que utiliza uma linha que varre o mapa para encontrar possíveis interseções entre os diferentes pontos e chegar a uma melhor ordem de serviço.
Outra é a heurística de troca. "Se a decisão acaba por não ser uma boa seqüência, então você operá-lo com trocas, dizendo 'o comércio parar uma para parada de dois, e mudar de nove para seis'", diz Bausch. "Você pode fazer isso por um longo tempo, também."
No entanto, outra, muito mais complexo algoritmo lida com atribuições quadrática. Ele considera a varredura e trocas juntos eo valor esperado.
Nenhum comentário:
Postar um comentário