quarta-feira, 6 de fevereiro de 2019

Pesquisadores desenvolvem algoritmos para reduzir custos com transportes



Quem nunca ouviu a expressão caixeiro-viajante? Ela designa pessoas que, no passado, quando não havia facilidade do transporte entre diferentes municípios e até regiões, eram as responsáveis por levar produtos de um lugar a outro, percorrendo distâncias hoje inimagináveis. Esse trabalho passou a ser feito por empresas especializadas, porém, a distribuição logística nos moldes atuais se depara com o Problema de Roteamento de Veículos (PRV), um dos grandes desafios nas áreas de Ciência da Computação, Engenharia de Produção e Pesquisa Operacional.
Pensando nisso, um grupo de pesquisadores brasileiros e estrangeiros, liderados pelo professor Anand Subramanian, da Universidade Federal da Paraíba (UFPB), trabalhou na construção de algoritmos para elaborar um plano de roteamento de veículos que pudesse reduzir custos com transporte de produtos, levando em conta que o preço final de uma mercadoria sofre considerável acréscimo devido aos gastos obtidos através de sua distribuição. Subramanian e sua equipe desenvolveram algoritmos “altamente competitivos” capazes de minimizar esses custos.
Mas, afinal, o que é PRV? Um dos mais estudados problemas na área da Otimização Combinatória (OC), o PRV consiste basicamente em estabelecer e organizar, por meio de algoritmos, rotas ou itinerários eficientes para veículos realizarem entrega ou captação de mercadorias, que partem de um ou mais pontos, para destinos diversos.  Em outras palavras, PRV é uma generalização do clássico Problema do Caixeiro Viajante (PCV), que, de modo simplificado, tentava determinar a menor rota para percorrer várias cidades, sempre retornando à origem (os chamados depósitos).
“Você tem uma frota de veículos e um conjunto de clientes com demanda por entrega ou coleta. Então, a ideia é atender esses clientes minimizando a soma dos custos do deslocamento dos veículos. Mas isso é muito complicado de ser resolvido”, afirma Subramanian, que é bolsista de Produtividade em Pesquisa do Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq). Justamente por sua aplicabilidade e importância, o PRV é um dos problemas de distribuição logística mais conhecidos e estudados por pesquisadores no mundo inteiro, de acordo com o pesquisador.
Para se ter uma ideia do nível do complexidade, Subramanian dá o seguinte exemplo: “Imagine uma situação em que você tem 100 clientes e deseja encontrar a melhor solução para reduzir seus custos. Se, por ventura, você tentar enumerar todas as soluções possíveis, esse número ultrapassa o número estimado de átomos existentes no universo. Mesmo supercomputadores mais potentes levariam anos para enumerar todas as possibilidades de maneira explícita e encontrar a melhor solução”, diz.
O pesquisador acrescenta que, em geral, problemas de otimização combinatória podem ser resolvidos de maneira exata com a utilização de algoritmos baseados em teoremas matemáticos, através dos quais se obtém a melhor solução encontrada – “O que a gente denomina de solução ótima” – explica Subramanian. Outra possibilidade é resolvê-los de forma heurística, em que uma solução de boa qualidade é obtida, “mas sem garantia de otimalidade”, ressalta o pesquisador.
“A desvantagem dos métodos exatos, mesmo garantindo a otimalidade, é que eles possuem uma complexidade exponencial e demandam um alto tempo computacional, enquanto os algoritmos heurísticos rodam mais rápido e são bem mais escaláveis. Por isso, acabam sendo bem mais utilizados na prática”, ressaltou.
O projeto coordenado por Subramanian considerou as duas vertentes, dependendo do problema. O pesquisador explica que o PRV possui inúmeras variantes, geralmente motivadas por situações reais. Por exemplo, em uma das variantes a frota de veículos é heterogênea, ou seja, os veículos não são idênticos. Outro caso é quando o cliente possui janelas de tempo para atendimento, não podendo ser atendido a qualquer momento, ou seja, as visitas estão limitadas a um dado período. É possível ainda combinar essas e outras variantes em um plano de roteamento de veículos, diz Subramanian.