Problema do caixeiro-viajante na logística – planejar o impossível

É do conhecimento geral que, graças ao desenvolvimento das tecnologias da informação (TI), as empresas estão a obter resultados de vendas cada vez melhores, para não falar do fato de poderem funcionar graças a soluções de softwares. Além disso, as pessoas podem tratar cada vez mais assuntos ou trabalhar através da Internet. No entanto, nem todos sabem que mesmo a informática tem os seus limites e não pode dar uma resposta exata a tudo, incluindo chatGPT :).

No domínio das ciências da computação, há anos que existem questões e problemas para os quais ainda não foram propostas soluções eficientes e fundamentais. Um deles é o problema de otimização denominado problema do caixeiro-viajante, que está intimamente associado à indústria TSL (Logística de transporte e expedição). Continue a ler para saber mais sobre ele. Talvez seja o sortudo que vai resolver este problema.

Como é que surgiu o “Problema do Caixeiro Viajante”?

É difícil identificar a pessoa que primeiro anunciou a dificuldade em indicar um conjunto de instruções para resolver o Problema do Caixeiro Viajante (PCV). As primeiras menções a este problema surgem na década de 1830 e as primeiras tentativas de o resolver foram feitas cerca de 100 anos mais tarde, quando se tentava encontrar a melhor rota para um transporte escolar. Deixaremos a análise do problema, baseada em leis e expressões matemáticas complexas, para os cientistas. É por isso que me vou limitar à sua essência, apresentando-o de uma forma facilmente compreensível.

Qual é o problema do PCV?

Vamos supor que há um transportador que começa e acaba o seu trabalho em Boston. Um dia, ele tem de entregar encomendas em endereços em Nova Iorque, Denver, Los Angeles, Austin, Portland e Chicago. O problema do caixeiro-viajante consiste em encontrar o percurso mais curto que permita ao entregador visitar todas estas cidades. O problema não tem de se limitar ao comprimento do percurso, pois pode também centrar-se em encontrar o caminho mais barato ou mais rápido. No nosso exemplo, o número de percursos possíveis é 5040.

Como é que as empresas lidam com o problema do PCV?

Se estivermos à procura do percurso mais curto para várias cidades, encontrar a solução ótima pode demorar segundos ou alguns minutos num computador normal. No entanto, quando se trata, por exemplo, de 52 cidades, são utilizados vários algoritmos e a computação distribuída e paralela para encontrar soluções aproximadas – suficientes para a logística – porque verificar todas as rotas possíveis é praticamente impossível. Provavelmente não se surpreenderá com o fato de a inteligência artificial (IA) desempenha um papel importante.

Aplicações do problema do caixeiro-viajante

O problema do caixeiro-viajante tem muitas aplicações práticas. A principal delas, e a razão para escrever este artigo, é a otimização de rotas para frotas de veículos, navios ou aviões, para minimizar custos e tempo de entrega. Outra aplicação é a planeamento de rotas por robôs em armazéns ou centros de logística. O PCV é também utilizado na criação de redes de telecomunicações para garantir uma qualidade de sinal ótima e minimizar os custos.

Vamos ajudá-lo a otimizar o seu carregamento

Embora não seja possível resolver o problema do caixeiro-viajante e encontrar o itinerário ótimo para qualquer número de cidades, dispomos de um programa para o planeamento do carregamento de carga chamado EasyCargo. Para além de criar um plano otimizado para a disposição das mercadorias (pode agrupá-las por locais de descarga) e a distribuição da carga, permite gerar relatórios em formato Excel ou PDF. Temos até mesmo a disposição o link público para trabalhar em colaboração com colegas sobre os carregamentos.

Além disso, pode integrar o EasyCargo no software da sua empresa ou outros programas, como o FleetUp sistema de telemetria através da nossa API. Pode saber mais sobre os seus pormenores neste link.

Fonte: https://developer-blogs.nvidia.com/wp-content/uploads/2023/01/cuopt-featured.jpg

Na verdade, pode afirmar que, para a indústria TSL, o problema do caixeiro-viajante está lentamente a tornar-se menos preocupante graças ao desenvolvimento da inteligência artificial e do Big Data. Todos os tipos de software de otimização de rotas de entrega oferecer um itinerário que não se afaste significativamente do mais favorável e que o ajuste dinamicamente em tempo real em função das condições das estradas.

Boa sorte em propor um algoritmo capaz de encontrar o itinerário ótimo para qualquer quantidade de cidades em tempo polinomial!